Bài toán Upper Bound và Lower Bound trên cây nhị phân tìm kiếm

     Cây nhị phân tìm kiếm là một cấu trúc dữ liệu phổ biến được dùng để lưu trữ thông tin một cách có tổ chức, mọi thông tin trên cây đều tuân thủ quy luật nhất định, từ đó, việc quản lý và tìm kiếm dữ liệu được tối ưu hơn. Các thao tác trên cây thường rất đa dạng và đơn giản, nhưng không phải thao tác nào cũng đơn giản, ví dụ như thuật toán tìm Upper bound và Lower bound, nó đòi hỏi bạn phải biết cách dùng đệ quy khéo léo(à quên giới thiệu về Upper và lower bound, cứ hiểu đơn giản như sau, Cho một dãy số, tìm trong dãy các số lower bound của x (số lớn nhất mà nhỏ hơn x) và upper bound của x (số nhỏ nhất mà lớn hơn x)), để làm được bài này thì có rất nhiều cách, chẳng hạn sử dụng mảng để lưu trữ có sắp xếp, sau đó duyệt tuyến tính hoặc dùng BinarySearch để tìm kiếm, hoặc dùng danh sách liên kết đơn, kép, vòng,..tùy các bạn. Nhưng có lẽ tốt hơn hết là dùng cây nhị phân tìm kiếm, việc thêm vào và tìm kiếm sẽ nhanh hơn nhiều. Giả sử bài toán được "biến tấu" như sau:

Cho một dãy số, tìm trong dãy các số lower bound của x (số lớn nhất mà nhỏ hơn x) và upper bound của x (số nhỏ nhất mà lớn hơn x)

INPUT

Mỗi dòng của input chứa hai con số a và b. Số a có giá trị là 1 hoặc 2 hoặc 3. Số b giá trị b không quá 1 tỷ.

Dòng: 1 565481 có nghĩa là thêm 565481 vào dãy số

Dòng: 2 87126 nghĩa là tìm lowerbound của 87126

Dòng: 3 48769 nghĩa là tìm upperbound của số 48769

Input sẽ kết thúc bằng dòng chỉ chứa một số 0.

OUTPUT

Ứng với mỗi yêu cầu tìm kiếm xuất ra trên một dòng lowerbound hoặc upperbound tìm được, nếu không tồn tại upperbound hoặc lowerbound xuất ra chuỗi “NULL”

Sau đây là code mẫu của mình, ngôn ngữ được dùng là C++.
template code:

#include<iostream>

using namespace std;

1. struct Node
2. {
3.     int x;
4.     Node*Left;
5.     Node*Right;
6.     Node(){ this->Left = this->Right = NULL; }
7. };
8. struct Tree
9. {
10.     Node*Root;
11.     Tree(){ this->Root = NULL; }
12. };
13. void add(Node*&R, int&x)
14. {
15.     if (!R)
16.     {
17.         Node*P = new Node;
18.         P->x = x;
19.         R = P;
20.         return;
21.     }
22.     else
23.     {
24.         if (R->x == x) return;
25.         if (R->x > x) add(R->Left, x);
26.         else add(R->Right, x);
27.     }
28. }
29. int min(int a, int b)
30. {
31.     if (a > b) return b;
32.     return a;
33. }
34. int searchBeNhatLonHonX(Node*&R, int&x, int&t)//truyen vao t mot so rat lon
35. {
36.     if (!R) return 1999999999;
37.     int a = R->x - x;
38.     if (a > 0)
39.     {
40.         t = min(a, t);
41.         return min(t, searchBeNhatLonHonX(R->Left, x, t));
42.     }
43.     return min(t, searchBeNhatLonHonX(R->Right, x, t));
44. }
45. int max(int a, int b)
46. {
47.     if (a < b) return b;
48.     return a;
49. }
50. int searchLonNhatBeHonX(Node*&R, int&x, int&t)//truyen vao t mot so rat be
51. {
52.     if (!R) return -1999999999;
53.     int a = R->x - x;
54.     if (a < 0)
55.     {
56.         t = max(a, t);    
57.         return max(t, searchLonNhatBeHonX(R->Right, x, t));
58.     }
59.     return max(t, searchLonNhatBeHonX(R->Left, x, t));
60. }
61. int main()
62. {
63.     std::ios::sync_with_stdio(false);
64.     cout.tie(NULL);
65.     cin.tie(NULL);
66.     Tree A;
67.     int a = 3;
68.     int b;
69.     int d;
70.     int t;
71.     while (a)
72.     {
73.         cin >> a;
74.         if (a == 1)
75.         {
76.             cin >> b;
77.             add(A.Root, b);
78.         }
79.         else
80.         {
81.             if (a == 2)
82.             {
83.                 cin >> b;
84.                 t = -1999999999;
85.                 d = searchLonNhatBeHonX(A.Root, b,t);
86.                 if (d != -1999999999)
87.                     cout << d + b << "\n";
88.                 else
89.                 {
90.                     cout << "NULL\n";
91.                 }
92.             }
93.             else
94.             {
95.                 if (a == 3)
96.                 {
97.                     cin >> b;
98.                     t = 1999999999;
99.                     d = searchBeNhatLonHonX(A.Root, b,t);
100.                     if (d != 1999999999)
101.                         cout << d + b << "\n";
102.                     else
103.                     {
104.                         cout << "NULL\n";
105.                     }
106.                 }
107.                 else break;
108.             }
109.         }
110.     }
111.     return 0;
112. }