Trong bài này mình sẽ giới thiệu về cấu trúc dữ liệu splay tree (do không tìm được thuật ngữ Tiếng Việt nên mình giữ nguyên thuật ngữ tiếng anh). Splay Tree được giới thiệu bởi Sleator và Tarjan vào năm 1985 [1]. Cấu trúc Splay Tree thuộc về lớp các cây tìm kiếm nhị phân tự cân bằng (Self-Adjusting Binary Search Tree - BST), có nghĩa là nó sẽ tự điều chỉnh cấu trúc của nó mỗi khi có một thao tác thực hiên trên cây. So với cây cân bằng AVL Tree và Red Black Tree (mình sẽ blog về cây này vào một ngày đẹp trời nào đó), Splay Tree có một số ưu điểm sau [2]:

• Dễ thực thi hơn cây AVL Tree và cây Red Black Tree. Cái này các bạn nên code thử để tự so sánh.
• Cần ít bộ nhớ hơn vì chúng ta không cần phải lưu thêm các thông tin phụ để đảm bảo cân bằng.
• Hiệu quả hơn nhiều nếu như phân phối truy nhập các khóa là không đồng nhất (skew). Cụ thể, nếu một khóa được truy nhập liện tục nhiều lần thì lần truy nhập đầu tiên mất thời gian ( khấu trừ) $O(\log (n))$ còn các lần sau đó là $O(1)$.

Tuy nhiên, điểm yếu của Splay Tree là chiều cao của cây có thể $O(n)$ và một số thao tác có thể rất tốn kém (nhưng trung bình sẽ là $O(\log n)$). Ok, tóm lại Splay Tree tốt hơn về một số mặt. Bây giờ chúng ta sẽ tìm hiểu cụ thể hơn.

Cây Splay Tree là một cây nhị phân tự cân bằng. Các thao tác cơ bản bao gồm:

• Tìm kiếm (Search): Tìm và trả lại giá trị của một nút có khóa $K$ cho trước trong cây.
• Chèn (Insertion): Chèn thêm một nút có khóa $K$ và giá trị $V$ vào cây Slay.
• Xóa (Insertion): Xóa nút có khóa $K$ ra khỏi cây.

Ngoài 3 thao tác trên, cây Splay Tree cung cấp thêm thao tác Splay. Một nút được splay sẽ được đưa lên làm gốc của cây splay tree thông qua một loạt các thao tác quay cây (tree rotations) mô tả dưới đây. Trọng tâm của bài viết là định lý sau:

Trong giả các giả mã dưới đây, mình sẽ sử dụng cấu trúc dữ liệu Node cho mỗi nút của cây. Cấu trúc này bao gồm các trường sau:

• key trường này là khóa của một nút.
• value trường này sẽ chứa thông tin được lưu trữ trong một nút của cây.
• left trường này là con trỏ tới nút con trái của nút hiện tại.
• right trường này là con trỏ tới nút con phải của nút hiện tại.
• parent trường này là con trỏ tới nút cha của nút hiện tại. Với nút gốc, trường này có giá trị Null.

Biểu diễn trong C:

typedef struct Node{
int key;
int value;
struct Node *left, *right, *parent;
} Node;

Remark: Có một phiên bản thực thi khác của cây Splay Tree mà không cần trường parent, do đó tiết kiệm được thêm bộ nhớ và thời gian (để cập nhật trường parent sau mỗi thao tác). Tất nhiên là thực thi cũng sẽ phức tạp hơn một chút. Bạn đọc tham khảo cách thực thi này bằng Java tại [4].

Nhắc lại về phép quay trái quay phải

Cũng như AVL và Red Black Tree, cây Splay Tree cũng sử dụng các thao tác quay để làm cho cây trở nên cân bằng. Hai thao tác quay cơ bản là quay phải và quay trái. Hai thao tác này được minh họa trong hình dưới đây:

Từ cây bên trái, để thu được cây ở hình bên phải, ta thực hiện quay phải tại $y$. Tương tự như vậy, từ cây bên phải, để thu được cây ở hình bên trái, ta thực hiện quay trái tại $x$. Chú ý cây con màu đỏ của $x$ và của $y$ trong hai hình đổi chỗ khi thực hiện quay. Gọi $w$ là cha của$ $y$ và $z$ là con phải của $x$. Để quay phải, ta làm theo các bước sau:

1. Cập nhật con trỏ con (trái hoặc phải tùy theo $y$ là con trái hay phải của $w$) của $w$ trỏ vào $x$.
2. Cập nhật con trỏ cha của $z$ trỏ vào $y$.
3. Cập nhật con trỏ con trái của $y$ trỏ vào $z$.
4. Cập nhật con trỏ cha của $x$ trỏ vào $w$.
5. Cập nhật con trỏ con phải của $x$ trỏ vào $y$.
6. Cập nhật con trỏ cha của $y$ trỏ vào $x$.

Giả mã quay phải tại $y$ như sau:

Code C:

// right rotation at y
void right_rotate(Node *y){
Node* x = y->left;
Node* w = y->parent;
Node* z = x->right;
if(w != null){
if(w->left!= null && w->left->key == y->key){
w->left = x;
}else {
w->right = x;
}
}
if(z != null)z->parent = y;
y->left = z;
x->parent = w;
x->right = y;
y->parent = x;
}

Quay trái ta làm tương tự như quay phải, cập nhật các con trỏ. Giả mã quay trái tại $x$ như sau:

 
Code C:

// left rotation at x
void left_rotate(Node *x){
Node* y = x->right;
Node *w = x->parent;
Node *z = y->left;
if(w != null){
if(w->left != null && w->left->key == x->key){
w->left = y;
}else {
w->right = y;
}
}
if(z != null) z->parent = x;
x->right = z;
y->left = x;
y->parent = w;
x->parent = y;
}

Remark Khi thực thi bằng code, các bạn chú ý check null. Để giả mã sáng sủa, mình bỏ qua các bước check null.

Ta dễ thấy:

Ngoài ra, khác với AVL Tree, Splay Tree còn sử dụng hai phép: Zig-Zag và Roller-Coaster

Zig-Zag và Roller-Coaster

Zig-Zag
Phép Zig-Zag có hai dạng là Zig-Zag trái và Zig-Zag phải. Hai phép zig-zag trái và phải tại $z$ được minh họa trong hình dưới đây:

Trong cả hai phép, nút $x$ sẽ được đưa lên làm gốc thay cho $z$. Phép zig-zag trái gồm hai phép: quay trái tại $y$, sau đó quay phải tại $z$. Phép zig-zag phải gồm hai phép: quay phải tại $y$, sau đó quay trái tại $z$. Chú ý sự thay đổi cha của các cây con được tô màu của $x$.

Giả mã của phép zig-zag trái tại $z$:

 
Code C:

// left zig-zag at z

void left_zig_zag(Node *z){
Node *y = z->left;
left_rotate(y);
right_rotate(z);
}

Giả mã của phép zig-zag phải tại $z$:

 
Code C:

// right zig-zag at z

void right_zig_zag(Node *z){
Node *y = z->right;
right_rotate(y);
left_rotate(z);
}

Roller-Coaster

Tương tự như zig-zag, có hai phép Roller-Coaster là phải và trái, được minh họa trong hình dưới đây:

Phép roller-coaster phải tại $z$ gồm hai phép: quay rollaer-coaster phải tại $z$, sau đó quay phải tại $y$. Phép roller-coaster trái tại $x$ gồm hai phép: quay trái tại $y$, sau đó quay trái tại $x$. Chú ý sự thay đổi cha của các cây con được tô màu của $x$.

Giả mã của phép roller-coaster phải tại $z$:

 
Code C:

// right roller-coaster at z
void right_roller_coaster(Node *z){
Node *y = z->left;
right_rotate(z);
right_rotate(y);
}

Giả mã của phép roller-coaster trái tại $x$:

 
Code C:

// right roller-coaster at z

void right_roller_coaster(Node *z){
Node *y = z->left;
right_rotate(z);
right_rotate(y);
}

Phần tiếp theo chúng ta sẽ thực hiện phép Splay. Các thao tác chèn, xóa, tìm kiếm đều sử dụng phép Splay như là một thủ tục con.

Phép Splay

Như đã nói ở trên, phép splay một nút sẽ thực hiện đưa một nút con lên làm nút gốc của cây Splay Tree. Phép Splay được thực hiện thông qua một loạt các phép quay, zig-zag và roller-coaster phụ thuộc vào cấu trúc của cây tại nút đó. Ưu tiên thực hiện zig-zag và roller-coaster trước. Phép quay nếu có thực hiện thì sẽ chỉ thực hiện một lần và là lần cuối khi đưa $x$ lên làm gốc. Ví dụ ta muốn splay nút $x$ của cây trái nhất trong hình sau (hình được lấy từ [3]):

Ta có các bước sau:

• Bước 1: Cấu trúc của cây tại nút $x$ là dạng roller-coaster trái, do đó ta thực hiện roller-coaster trái tại bước đầu tiên.
• Bước 2: Cấu trúc của cây tại nút $x$ là dạng zig-zag trái, do đó ta thực hiện zig-zag trái tại bước 2.
• Bước 3: Cấu trúc của cây tại nút $x$ là dạng zig-zag phải, do đó ta thực hiện zig-zag phải tại bước 3.
• Bước 4: Cấu trúc của cây tại nút $x$ là dạng quay trái (do không có cấu trúc roller-coaster hay zig-zag), do đó ta thực hiện quay phải tại bước 4. Sau bước này, $x$ đã là nút gốc của cây. Do đó, thao tác splay nút $x$ kết thúc.

Giả mã của phép Splay như sau:

 
Code C:

// splay

void splay(Node *x){
if(x->parent == null) return;
Node *y = x->parent;
if(y->parent == null){ // y is the root
if(y->left != null && y->left->key == x->key){
right_rotate(y);
} else {
left_rotate(y);
}
} else {
Node *z = y->parent;
if(z->left != null &&z->left->key  == y->key){
if(y->left != null && y->left->key == x->key){
right_roller_coaster(z);
}else {
left_zig_zag(z);
}
} else {
if(y->right != null && y->right->key == x->key){
left_roller_coaster(z);
}else {
right_zig_zag(z);
}
}
}
splay(x);
}

Ta sẽ chứng minh bổ đề dưới đây ở phần phân tích cuối bài.

Bây giờ ta có thể thực hiện được các thao tác cơ bản.

Các thao tác cơ bản

Tìm kiếm

Khi thực thi splay, thông thường đầu vào là một khóa $K$ và chúng ta phải tìm nút $x$ có khóa $K$ đó và splay $x$ thành gốc của cây Splay Tree.

Để tìm kiếm một nút có khóa $K$, ta sẽ tìm kiếm nút $x$ có khóa $K$ trong cây như tìm kếm trên Binary Search Tree. Nếu ta tìm thấy $x$ có khóa $K$ thì ta sẽ Spaly $x$. Nếu nút $x$ đó không tồn tại, ta sẽ splay nút cuối cùng trên đường đi tìm kiếm khóa $K$. Ví dụ với hình vẽ ở phần Splay, nếu đầu vào là khóa có giá trị $p$ thì ta sẽ splay nút $n$ vì khi ta tìm kiếm từ gốc đến $n$ thì ta sẽ thấy khóa $p$ sẽ không có ở trông cây và $n$ là nút cuối cùng trên đường đi tìm kiếm đó. Giả mã như sau ($root$ ở đây là nút gốc của Splay Tree):

 
Code C:

// find a key K
int find(int K){
Node *x = find_without_splay(root,K);
splay(x);
root = x;
if(root->key == K) return TRUE;
else return FALSE;
}

Thủ tục FindWithoutSplay tìm kiếm khóa $K$ và trả lại nút $x$ như mô tả ở trên. Chú ý là khóa của $x$ có thể không bằng $K$ trong trường hợp $K$ không có trong cây Splay. Giả mã của thủ tục này như sau:

 
Code C:

// find without splay a key K
Node *find_without_splay(Node *r, int K){
if (r->key == K) return r;
else if (r->key < K){
if(r->right == null) return r;
else return find_without_splay(r->right,K);
} else {
if(r->left == null) return r;
else return find_without_splay(r->left,K);
}
}

Remark Do mỗi khi tìm kiếm một nút $x$, ta splay nút đó lên làm gốc. Do đó, các thao tác tìm kiếm tiếp theo đó sẽ ít tốn kém hơn.

Bổ đề sau là hệ quả trực tiếp của Lemma 2:

Chèn

Để chèn một nút có khóa $K$, trước hết ta sẽ chèn khóa vào cây như chèn cây nhị phân và sau đó splay nút vừa chèn.

 
Code C:

//insert a (key,value) pair

void insert(int K, int V){
Node *x = insert_without_splay(root,K,V);
splay(x);
root = x;
}

//insert a (key,value) pair without splay

Node *insert_without_splay(Node *r, int K, int V){
if (r->key == K){
r->value = V;
return r;
}
else if (r->key < K){
if(r->right == null) {
Node*x = create_node(K,V);
r->right = x;
x->parent = r;
return x;
}
else return insert_without_splay(r->right,K,V);
} else {
if(r->left == null) {
Node*x = create_node(K,V);
r->left = x;
x->parent = r;
return x;
}
else return insert_without_splay(r->left,K,V);
}
}

Bổ đề sau là hệ quả trực tiếp của Lemma 2:

Xóa

Để xóa một nút có khóa $K$, ta làm theo các bước sau:

1. Ta sẽ tìm kiếm Node $x$ có khóa $K$ trong cây và Splay nút $x$ đó lên gốc
2. Xóa $x$ ra khỏi cây.
3. Ta tìm Node $w$ là node phải nhất (right most) của cây con trái của $x$. Sau đó gán cây con phải của $x$ làm cây con phải của $w$
Các bước trên được thể hiện trong hình sau. Hình được lấy từ [3].


Giả mã của thủ tục như sau:

Delete(Key $K$):
    if Find$(root,K) = $ False         [[after find, the root is $x$ as described]]
        return
    Node $y \leftarrow \mathrm{left}(root)$
    $\mathrm{parent}(y) \leftarrow $ Null
    if $\mathrm{right}(y) \not= $ Null
        Node $w \leftarrow \mathrm{right}(y)$
        while $\mathrm{right}(w) \not= $ Null
        $w \leftarrow \mathrm{right}(w)$
        Splay$(w)$
        $\mathrm{right}(w) \leftarrow \mathrm{right}(root)$
        $\mathrm{parent}(\mathrm{right}(root)) \leftarrow w$
        $root \leftarrow w$             [[set $w$ as the root of the splay tree]]
    else
        $\mathrm{right}(y) \leftarrow \mathrm{right}(root)$
        $\mathrm{parent}(\mathrm{right}(root))\leftarrow y$
        $root \leftarrow y$             [[set $y$ as the root of the splay tree]]


 

Code C:

// delete a node with key K
void delete(int K){
if(find(K) == FALSE) return;
Node *y = root->left;
y->parent = null;
if(y->right != null){
Node *w = y->right;
while(w->right != null) w = w->right;
splay(w);
w->right = root->right;
if(root->right != null) root->right->parent = w;
root = w;
}else {
y->right = root->right;
if(root->right != null) root->right->parent = y;
root = y;
}
}

Bổ đề sau là hệ quả trực tiếp của Lemma 2:

Lemma 5: Thao tác Delete có thời gian khấu trừ là $O(\log n)$.

 

Phân tích và chứng minh

Trong phần này chúng ta sẽ chứng minh Lemma 2. Theorem 1 là hệ quả trực tiếp của các Lemma 1,2,3,4. Để chứng minh Lemma 2, chúng ta sẽ dùng phương pháp hàm thế năng trong phân tích khấu trừ (mình sẽ chi tiết thêm về phương pháp này vào ngày đẹp trời nào đó, các bạn tham khảo thêm tại [5]). Mình sẽ tóm tắt ngắn gọn phương pháp này tại đây.

Chúng ta sẽ sử dụng một hàm $\Phi$ gọi là thế năng (potential function). Gọi $c_i$ là chi phí thực của thao tác thứ $i$. Ta sẽ gán cho thao tác này một chi phí khác gọi là chi phí khấu trừ (amortized cost) $a_i$. Quan hệ giữa chi phí khấu trừ và chi phí thực như sau:

$a_i = c_i + \Phi_i - \Phi_{i-1} \qquad (1)$

 
Trong đó lượng $\Phi_i - \Phi_{i-1}$ là năng lượng thay đổi sau khi thực hiện chi phí thứ $i$. Hàm thế năng $\Phi$ được gọi là hợp lệ nếu $\Phi_i - \Phi_0 \geq 0$ với mọi $i \geq 0$. Từ $(1)$, ta suy ra:

$ \sum_{i}a_i = \sum_{i} c_i + \Phi_m - \Phi_{0} \geq \sum_{i} c_i \qquad (2)$

Do đó, tổng chi phí thực $\sum_{i} c_i$ luôn nhỏ hơn tổng chi phí khấu trừ $\sum_{i} a_i$.

Chứng minh Lemma 2

Ta sẽ sử dụng hàm thế năng:

$\Phi = \sum_{v \in T} r(v) = \sum_{v \in T} \lfloor \log(s(v))\rfloor \qquad (3)$

 
trong đó $s(v)$ là số lượng node của cây con gốc tại $v$ và $r(v) = \lfloor \log(s(v))\rfloor$ được gọi là hạng (rank) của $v$. Dễ thấy $r(v) \leq \log (n)$ nếu cây có $n$ node.

Ta gọi mỗi phép quay trái, phải là một phép quay đơn (single rotation) và mỗi phép zig-zag hay roller-coaster là một phép quay kép (double rotation). Ta sẽ tìm giá trị khấu trừ của mỗi phép quay đơn và kép. Dễ thấy rằng giá trị khấu trừ của phép Splay chính là tổng giá trị khấu trừ của mỗi phép quay đơn và kép này. Ta sẽ chứng minh bổ đề sau:

Lemma 5 (Access Lemma): Giá trị khấu trừ của mỗi phép quay đơn để splay node $v$ là $1 + 3(r'(v) - r(v))$ và giá trị khấu trừ của mỗi phép quay kép để splay node $v$ là $ 3(r'(v) - r(v))$

 
trong đó $r'(v)$ là hạng của $v$ sau phép quay đơn hay kép. Ở dưới ta sẽ chứng minh bổ đề này. Bây giờ ta sẽ sử dụng bổ để này để chứng minh Lemma 2.

Dễ thấy giá trị khấu trừ của phép splay sẽ là tổng giá trị khấu trừ của mỗi bước quay đơn hay kép khi ta splay $v$. Do ta chỉ sử dụng tối đa một phép quay đơn (là phép quay đơn cuối cùng) và còn lại là các phép quay kép, ta sẽ có tổng chi phí khấu trừ cho toàn bộ phép Splay là $1 + 3(r'(v) - r(v))$ (do các hạng tử trung gian triệt tiêu nhau). Ở đây $r(v)$ là hạng ban đầu và $r'(v)$ là hạng của $v$ sau phép Splay. Do $r(v) \geq 0$ và $r'(v) \leq \log(n)$, ta có chi phí khấu trừ cho mỗi phép Splay là $O(\log n)$. Từ đó ta suy ra Lemma 2.

Chứng minh Access Lemma Trước hết chú ý ở đây $\log$ là hàm concave (hình như dịch là lõm), do đó với mọi $x,y$ dương, ta có:

$\frac{\log(x) + \log(y)}{2} \leq \log(\frac{x+y}{2})\qquad (4)$

 
Ta sẽ chứng minh bằng cách phân tích từng trường hợp riêng biết.

1. Phép quay đơn

Để ý với phép quay đơn, chỉ có $x$ và $y$ là thay đổi hạng. Do đó, chi phí khấu trừ là:

$\begin{array} {lcl} 1 + \Phi' - \Phi & = & 1 + r'(x) + r'(y) - r(x) - r(y) \\ & = & 1 + r'(x) - r(x) \leq 1 + 3(r'(x) - r(x)) \end{array}$
Từ dòng trên xuống dòng dưới là do $r'(y) \geq r(y)$.

2. Phép zig-zag

Để ý với phép zig-zag, chỉ có $x,y$ và $z$ là thay đổi hạng. Do đó, chi phí khấu trừ là:

$\begin{array} {lcl} 2 + \Phi' - \Phi & = & 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z)\\ & = & 2 + r'(y) + r'(z) - 2r(x) \\ &= & 2 + (r'(y) - r'(x)) + (r'(z) - r'(x)) + 2(r'(x) - r(x))\\ &= & 2 + \log \frac{s'(y)}{s'(x)} + \log \frac{s'(z)}{s'(x)} + 2(r'(x) - r(x)) \\ & \leq & 2 + 2 \log \frac{s'(x)/2}{s'(x)} + 2(r'(x) - r(x)) = 2 (r'(x) - r(x)) \leq 3(r'(x) - r(x))\end{array} $

Từ dòng thứ nhất xuống xuống dòng dưới là do $r(x) \geq r(y)$ và $r'(x) = r(z)$. Bất đẳng thức từ dòng thứ 5 là do áp dụng $(4)$ và $s'(y) + s'(z) \leq s'(x)$.

3. Phép roller-coaster chứng minh tương tự như phép zig-zag và coi như bài tập cho bạn đọc.

Remark Giả sử mỗi nút của cây có một trong số $w(v)$. Ta có thể thay đổi một chút chứng minh ở trên với hạng $r(v) = \log W(v)$ trong đó $W(v)$ là tổng trọng số của các nút con trong cây con gốc tại $v$, ta cũng thu được kết quả tương tự. Ví dụ trong trường hợp mỗi nút $v$ có tần số truy cập là $t(v)$, bằng cách đặt $w(v) = t(v)$ ta thu được Lemma sau:

Lemma 6 (Static Optimality Thoerem): Chi phí khấu trừ truy nhập mỗi nút $v$ là $O(\log T - \log t(v))$, trong đó $T = \sum_{v}t(v)$.

 

Có thể thấy nếu $t(v) = t(u)$ với mọi $u,v$ (tần số truy nhập khóa là đều), thì chi phí khấu trừ là $O(\log n)$. Trong trường hợp $v$ được truy nhập nhiều hơn, ví dụ $t(v) = \frac{T}{2}$, thì có thể thấy chi phí truy nhập của $v$ là $O(1)$

Code đầy đủ của bài viết: Splay-Tree.

Tham Khảo

[1] Sleator, Daniel Dominic, and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM) 32.3 (1985): 652-686. Paper here.
[2] Ravi Teja Cheruku, Splay Tree Lecture Note, Indiana State University, 2011.
[3] Jeff Erickson, Scapegoat Tree and Splay Tree Lecture Note, UIUC, 2013.
[4] Robert Sedgewick and Kevin Wayn. Splay Tree implementation in Java. Princeton, 2015.
[5] Jeff Erickson, Amortized Analysis Lecture Note, UIUC, 2009.