Hiện tại tôi đang triển khai BST trong Java cho dự án đại học của mình. Như chúng ta đã biết, BST khá tốt khi tìm kiếm một đơn vị đơn là O (log n) trong một cây cân bằng.Lấy khoảng thời gian của cây tìm kiếm nhị phân nhanh như mảng đã sắp xếp
Nhưng cách thực hiện tìm kiếm giữa giá trị a và b? (Một < b)
Hãy nói rằng tôi có cây này
│ ┌── 125
│ ┌── 122
│ │ └── 120
│ ┌── 117
│ │ │ ┌── 113
│ │ └── 112
│ │ └── 108
│ ┌── 86
│ │ │ ┌── 85
│ │ └── 72
└── 59
│ ┌── 56
│ ┌── 52
│ ┌── 47
│ │ │ ┌── 43
│ │ └── 39
│ │ │ ┌── 38
│ │ └── 36
└── 28
│ ┌── 18
│ ┌── 15
└── 2
└── 1
Tôi muốn tạo ra một phương pháp range(a,b) trở về giá trị giữa a và b toàn diện. (Lưu ý: a và b là không cần thiết trong cây!)
Ví dụ: range(53,112) sẽ trở lại 56,59,72,85,86,108,112
Đây là mã giả của tôi
/* recursive method */
range(a,b)
range(a,b,root);
/* helper method */
range(a,b,node)
if (a <= node.value <= b)
if (node.left != null) and (node.value != a)
range(a,b,node.left)
print node.value
if (node.right != null) and (node.value != b)
range(a,b,node.right)
else if node.value < a
if (node.right != null)
range(a,b,node.right)
else // node.value > b
if (node.left != null)
range(a,b,node.left)
Nhưng tôi nghĩ rằng phương pháp của tôi là chậm hơn.
Ví dụ: trong một mảng được sắp xếp, chúng tôi phải thực hiện tìm kiếm nhị phân trên a và b và nhận chỉ mục tương ứng của chúng. Sau đó, chúng tôi lặp lại từ chỉ mục của a thành chỉ mục của b.
Có đúng là BST sẽ thực hiện chậm hơn trong việc tìm kiếm nhiều giá trị không? Có thể cải thiện thuật toán của tôi nhanh như một mảng được sắp xếp không?