Trong bài này chúng ta sẽ làm quen với một cấu trúc dữ liệu sử dụng trong hình học tính toán (computational geometry) tên gọi là cây tìm kiếm ưu tiên (Priority Search Tree - PST). Cây PST được McCreight [1] phát triển vào năm 1985 (cũng là người phát triển thuật toán tuyến tính xây dựng cây hậu tố). Cấu trúc cây PST là sự kết hợp của hàng đợi ưu tiên (Priority Queue) và cây nhị phân tìm kiếm (Binary Search Tree) vào trong cùng một cấu trúc.

Cấu trúc PST có nhiều ứng dụng trong hình học tính toán (xem thêm tại [1]). Một trong những ứng dụng nổi bật là dùng để truy vấn các điểm trong một vùng hình chữ nhật vô hạn một bên. Chúng ta sẽ thảo luận ứng dụng đó ở cuối bài. Để đơn giản cho việc trình bày và ứng dụng cây PST, chúng ta xét bài toán sau:

Ví du tập $P = \{(1,4),(1,5), (3,2), (4,3), (5,6), (7,1), (7,7)\}$ (các điểm màu xanh trong hình dưới đây) và $Q = \{(3,5)\}$ (điểm màu tím trong hình dưới đây). Các điểm nhỏ hơn điểm $(3,5)$ là $(1,5),(1,4), (3,2)$ (là các điểm nằm trong hoặc nằm trên đường bao của vùng màu xanh trong hình dưới đây).

Biểu diễn các nút trong C:

typedef struct point{
int x;
int y;
int id; // the index of the data point in the original array
}point;

typedef struct node{
point p;
int ymid;
struct node *left;
struct node *right;
}node;

Chúng ta có thể dễ dàng thiết kế giải thuật có độ phức tạp $O(mn)$ giải bài toán trên bằng cách với mỗi điểm $q$ trong $Q$, ta duyệt qua tất cả các điểm trong $P$ và in ra những điểm nhỏ hơn $q$. Trong trường hợp tồi nhất khi $p \preceq q$ với mọi $p \in P, q\in Q$ thì thuật toán trên là thuật toán tối ưu. Tuy nhiên trong trường hợp với mỗi $q \in Q$, chỉ có $O(1)$ điểm trong $P$ nhỏ hơn $q$ thì thuật toán trên quá tốn kém.

Sử dụng PST, chúng ta có thể thiết kế giải thuật tốt hơn nhiều khi $m$ lớn. Trọng tâm của bài này là định lý sau:

Như vậy, sử dụng cấu trúc cây PST, ta có thể giải Problem 1 trong thời gian $O(m\log n + \mathrm{OPT})$ trong đó $\mathrm{OPT}$ là số điểm cần phải in ra trong lời giải tối ưu.

Cấu trúc cây PST là kết hợp của cấu trúc (min) Heap nổi tiếng và Binary Search Tree. Nếu bạn đọc đã từng thực thi thuật toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) thì có lẽ đã bắt gặp cấu trúc Heap rồi. Trước hết mình nhắc lại một số khái niệm cơ bản nhất của min-Heap. Min-Heap là một cấu trúc cây nhị phân thỏa mãn các tính chất sau:

1. Tính chất Heap (Heap Property): Mỗi nút có một giá trị (khóa) nhỏ hơn hoặc bằng giá trị khóa của hai nút con.
2. Tính cân bằng mạnh (Strong Balance Property): Mức thứ $i$ không phải là mức cao nhất có $2^i$ nút. Ở đây, nút gốc có mức $0$ và mức của một nút là mức của nút cha $+1$. Các nút của mức cao nhất (các nút lá) được đính vào cây theo thứ tự liên tục từ trái sang phải. Ví dụ trong hình dưới đây nếu ta đặt nút $7$ làm nút con phải của $3$ thì các nút lá không còn liên tục theo thứ tự từ trái sang phải nữa.

Ví du tập các giá trị $\{3,1,1,4,5,7\}$ có cấu trúc Heap biểu diễn minh họa trong hình dưới đây:

Từ tính chất Heap ta có thể chứng minh (bằng quy nạp) được rằng giá trị khóa ở gốc là giá trị nhỏ nhất trong tập các khóa của cây (do đó gọi là min-heap). Từ tính cân bằng mạnh ta có thể suy ra chiều cao của một Heap với $n$ nút tối đa là $\lceil \log(n)\rceil$. Tính cân bằng này gọi là mạnh vì nút ở mức lá phải là liên tục từ trái sang phải. So với các cây nhị phân tìm kiếm thì Heap đơn giản hơn, mềm dẻo hơn và là một cấu trúc cân bằng mà sự cân bằng đó có thể được duy trì khá đơn giản khi thực hiện các thao tác trên heap mà không cần phải có thêm thông tin phụ. Do đó các thao tác với Heap thông thường chỉ mất thời gian $O(\log n)$. Chi tiết thêm về Heap có lẽ mình sẽ blog vào một lúc nào đó, tạm thời bạn đọc tham khảo thêm tại [2].

Một cây nhị phân PST biểu diễn tập điểm $P$ là một cây thỏa mãn tính chất sau:

1. Mỗi nút của cây biểu diễn một điểm trong $P$.
2. Tính chất Heap Tọa độ $x$ của nút cha nhỏ hơn hoặc bằng tọa độ $x$ của hai nút con.
3. Tính cân bằng yếu Mức thứ $i$ không phải là mức cao nhất có $2^i$ nút.
4. Tính chia đôi Mỗi nút $v$ có một giái trị $y_{v}$, được gọi là điểm chia, trong đó mỗi điểm $p$ thuộc nút nằm trong cây con trái gốc tại $v$ thỏa mãn $y_p \leq y_v$ và mỗi điểm $p'$ thuộc nút nằm trong cây con phải gốc tại $v$ thỏa mãn $y_v \leq y_{p'}$. Giá trị này ở các nút lá là tung độ của điểm trong $P$ biểu diễn bởi nút đó.

Chú ý trong tính chia đôi, ta cho phép cả cây con trái và con phải của $v$ có các điểm tung độ bằng $y_v$. Điều này là cần thiết để đảm bảo tính cân bằng. Ví dụ nếu ta chỉ cho cây con trái có điểm có tọa độ $y_v$ và con phải có tọa độ $> y_v$ thì không thể đảm bảo tính cân bằng trong trường hợp tất cả các điểm trong $P$ có cùng tung độ.

Ví dụ cây PST với tập $P$ như trên được biểu diễn ở hình sau. Các cặp giá trị ở phần background màu xanh của mỗi nút là một điểm biểu diễn bởi nút đó. Giá trị ở phần dưới là điểm chia $y_v$.

Ta có thể quan sát thấy việc tìm kiếm theo tọa độ $x$ của các điểm được "tích hợp" vào cây thông qua tính chất Heap và tìm kiếm theo tọa độ $y$ của các điểm được "tích hợp" thông qua tính chia đôi. Tính cân bằng đảm bảo chiều cao của cây là $\lceil \log n\rceil$. Với các tính chất đó, ta có thể nhận thấy rằng PST là một cấu trúc phù hợp để tìm kiếm hai chiều với độ phức tạp của mỗi thao tác tìm kiếm là $O(\log n)$. Dễ thấy cấu trúc cây PST có bộ nhớ là $O(n)$.

Truy vấn với cây PST

Giả sử chúng ta đã xây dựng được cây PST, kí hiệu là $T$, biểu diễn tập điểm $P$, ta sẽ thực hiện truy vấn với mỗi điểm $q \in Q$. Để in ra các điểm nhỏ hơn $q$, ta sẽ so sánh $q$ với cây $T$, bắt đầu từ nút gốc. Gọi $v$ là một nút trong $T$ mà ta đang so sánh với $q$:

1. So sánh điểm $p_v$ lưu ở nút $v$ và in ra nếu $p_v \preceq q$.
2. Nếu $y_v \geq y_q$ thì ta sẽ in ra tất cả các nút trong cây con trái của $v$ có hoành độ nhỏ hơn $x_q$. Do cấu trúc cây là một min-Heap theo hoành độ, ta sẽ chỉ mất $O(k^v_q)$ phép so sánh để in ra các nút đó trong đó $k^v_q$ là số điểm nhỏ hơn $q$ nằm trong cây con trái của nút $v$ (thủ tục Report dưới đây sẽ thực hiện thao tác này). Sau đó, ta tiếp tục so sánh đệ quy $q$ với nút con phải của $v$.
3. Nếu $y_q < y_v$, các nút trong cây con phải của $v$ sẽ có tung độ lớn hơn $y_q$ theo tính chất chia đôi. Do đó, ta chỉ cần gọi đệ quy so sánh $q$ với nút con trái của $v$.

Giả mã của thủ tục truy vấn như sau:

 
Code C:

void query(node *root, point q){
if(root == null) return;
if(root->p.x <= q.x && root->p.y <= q.y){
print_point(root->p);
}
if(root->ymid <= q.x){
report(root->left, q);
query(root->right, q);
}else{
query(root->left, q);
}

}

void report(node *root, point q){
if(root == null) return;
if(root->p.x <= q.x){
print_point(root->p);
report(root->left, q);
report(root->right, q);
}
}

Từ phân tích ở trên, ta suy ra:

Phần tiếp theo chúng ta sẽ tìm hiểu cách xây dựng cây PST trong thời gian $O(n \log n)$

Xây dựng cây tìm kiếm ưu tiên

Gọi $P = \{P[1], P[2] ,\ldots, P[n]\}$ là tập các điểm trong $P$. Ta sẽ xây dựng cây PST một cách đệ quy như sau:

1. Tìm điểm $P[i] \in P$ sao cho hoành độ $P[i]$ là nhỏ nhất (nếu có vài điểm có cùng hoành độ nhỏ nhất thì chọn một điểm tùy ý trong số đó). Tạo một node $v$ chứa $P[i]$. Gọi $y_v$ là giá trị tung độ sao cho một nửa số điểm trong $P \setminus \{P[i]\}$, gọi là $P_L$, nhỏ hơn hoặc bằng $y_v$ và nửa còn lại, gọi là $P_R$, lớn hơn hoặc bằng $y_v$. Gán $y_v$ là điểm chia của nút $v$.
2. Gọi đệ quy xây dựng cây PST cho $P_L$ và $P_R$. Gọi nút gốc tương ứng của hai cây con là $u_l$ và $u_r$. Gán $u_l$ là con trái của $v$ và $u_r$ là con phải của $v$.

Ví dụ với tập $P = \{(1,4),(1,5), (3,2), (4,3), (5,6), (7,1), (7,7)\}$, các bước xây dựng cây PST được mô tả trong hình sau:

Giả mã của thuật toán:

Thủ tục LinearSelection chọn ra điểm chia $y_v$ như mô tả ở bước 1 trong thời gian $O(n)$. Thủ tục này mình đã blog trước đây, các bạn xem lại tại bài viết chọn median.

Phân tích thuật toán: Ta thấy chọn điểm với hoành độ nhỏ nhất có thể thực hiện trong $O(n)$ bằng cách duyệt qua tất cả các phần tử trong mảng. Chọn $y_v$ cũng có thể thực hiện trong $O(n)$ như đã nói ở trên. Chia $P$ ra thành 2 phần $P_L$ và $P_R$ mất $O(n)$. Gọi $T(n)$ là thời gian xây dựng cây PST. Do $P_L$ và $P_R$ xấp xỉ $n/2$, ta suy ra công thức đệ quy:

$T(n) = 2T(n/2) + O(n) \qquad (1)$

Giải công thức truy hồi trên ta được $T(n) = O(n \log n)$. Do đó:

Từ Lemma 1 và Lemma 2, ta dễ dàng suy ra Theorem 1.

Remark: Thực thi theo đúng thuật toán trên cũng khá mất thời gian do phải thực thi thuật toán chọn median trong thời gian $O(n)$. Trong bước chọn median, để đơn giản, ta có thể sắp xếp các điểm theo $y$, sau đó thực hiện chọn. Thời gian của bước sắp xếp là $O(n \log n)$ và do đó thời gian của thuật toán là:

$T(n) = 2T(n/2) + O(n\log n) \qquad (2)$

Từ đó suy ra $T(n) = O(n\log^2 n)$. Không quá tệ!!!!

Tuy nhiên, ta có thể cải tiến ý tưởng này thành $O(n\log n)$ như sau: Sắp xếp các điểm trong $P$ theo tọa độ $y$ ngay từ ban đầu với thời gian $O(n\log n)$. Khi đó, việc chọn median có thể thực hiện trong thời gian $O(n)$ vì các điểm trong $P$ là đã sắp xếp theo $y$. Do đó, thuật toán xây dựng cây PST sẽ như sau:

void simple_pst_construction(point *A){
qsort(A,N,sizeof(*A), comp_Y);
//	print_array(A,N);
root = recursive_pst_const(A,0, N-1);
}

node *recursive_pst_const(point *A, int l, int h){
if(h < l) return null;
else if(h== l) return create_node(A[l], A[l].y);
else if(h-l == 1){
node *u = create_node(A[l], A[l].y);
node *v = create_node(A[h], A[h].y);
if(u->p.x < v->p.x){
u->right = v; // remember here u->y < v->y
return u;
}else {
v->left = u;
return v;
}
}else {
int k = -1;
int min  = INFTY;
int i = l;
// find the point of minimum x-coordinate
for(; i <= h; i++){
if(A[i].x < min){
min = A[i].x;
k = i;
}
}
// put A[k] to the end of the array
point tmp = A[k];
int j = k+1;
for(; j <= h; j++){
A[j-1] = A[j];
}
A[h] = tmp;
// call recursive-pst-construction
int m = (l + h-1) >>1;
node *v = create_node(A[h], A[m].y);
v->left = recursive_pst_const(A, l, m);
v->right  = recursive_pst_const(A,m+1, h-1);
return v;

}
}

node *create_node(point p, int yv){
node *v = (node *)malloc(sizeof(node));
v->p = p;
v->ymid = yv;
v->left = null;
v->right = null;
}
// the compare function for quick sort
int comp_Y(const void *a, const void *b){
point *pa = (point *)a;
point *pb = (point *)b;
return pa->y - pb->y;
}