Trong bài này chúng ta sẽ tìm hiểu cách thực hiện xóa một nút khỏi cây AVL. Bài này tiếp nối bài trước về phép chèn một nút vào cây AVL; mình khuyến khích bạn đọc xem lại các kí hiệu đã dùng trong bài trước. Ta nhắc lại tính chất sau của cây AVL:
$|height(L[v]) - height(R[v])| \leq 1 \qquad (1) $
Tạm thời bỏ qua các điều kiện cân bằng của cậy, ta tập trung vào xóa một nút mà đảm bảo cây nhị phân sau khi xóa vẫn là cây nhị phân tìm kiếm. Sau đó ta sẽ tìm hiểu cách cân bằng lại cây. Giả sử nút ta muốn xóa là nút $X$ có con trái hoặc con phải là Null. Trong trường hợp này, ta chỉ việc thay thế $X$ bởi nút con (duy nhất) khác Null của nó và xóa $X$ ra khỏi cây. Không khó để thấy rằng cây thu được vẫn là cây nhị phân tìm kiếm.
Tuy nhiên, nếu $X$ có cả hai con đều khác Null, ta có thể quy về trường hợp một trong hai nút con bằng Null như sau. Gọi $Y$ là nút có khóa nhỏ nhất trong cây con phải của $X$. Ta thay thế $X$ bằng $Y$ và sau đó xóa $Y$ ra khỏi cây. Ở đây, thay thế có nghĩa là ta gán lại khóa và dữ liệu của nút $X$ bằng khóa và dữ liệu của nút $Y$. Theo cách ta chọn $Y$, không khó để thấy rằng cây thu được vẫn là cây nhị phân tìm kiếm. Xem minh họa trong Figure 5.
Figure 5: (a) Xóa nút có khóa 19 (nút màu đỏ) ra khỏi cây AVL. Do 19 có hai nút con đều khác Null, ta sẽ thay thế nút 20 (nút màu xanh) vào vị trí của nút 19. (b) Cây thu được sau khi xóa 19. Chú ý sự thay đổi của các kí hiệu $., -, +$. Ý nghĩa của các kí hiệu này ta đã giải thích trong bài trước. Nút 20 bị mất cân bằng sau khi xóa (lệch trái).
Giả mã của thủ tục xóa:
if $k[r]$ < $K$
$R[r] \leftarrow $ UnbalancedDelete($R[r]$, $K$)
else if $k[r]$ > $K$
$L[r] \leftarrow $ UnbalancedDelete($L[r]$, $K$)
else
if $L[r] =$ Null
return $R[r]$
else if $R[r] =$ Null
return $L[r]$
else
$y \leftarrow$ FindMin($R[r]$)
$k[r] \leftarrow k[y]$
$R[r] \leftarrow$ UnbalancedDelete($R[r], k[y]$)
$height[r] \leftarrow $ Max($height(R[r]), height(L[r])$) $+1$
return $r$
Trong giả mã trên, ta giả sử luôn tồn tại một nút có khóa $K$ trong cây.
Cân bằng cây sau khi xóa
Để thực hiện cân bằng sau khi xóa, trước hết chúng ta phải xem xét cấu trúc của cây tại nút bị mất cân bằng. Gọi $A$ là nút gần lá nhất mà tại đó cây AVL bị mất cân bằng. Ta sẽ lặp lại các phân tích như trong bài trước để xác định cấu trúc của cây con có gốc $A$. Mình sẽ không phân tích các cấu trúc một cách tỉ mỉ như bài trước nữa, mà sẽ chỉ ra cụ thể các cấu trúc này. Phần chứng minh (không thay đổi nhiều so với bài trước) coi như bài tập cho bạn đọc.
Gọi $h$ là chiều cao của $A$ trước khi ta xóa một nút ra khỏi cây AVL. Không khó để thấy nút ta xóa khỏi cây cũng là nút con cháu (desancendt) của $A$. Chú ý, nút ta xóa khỏi cây luôn có con phải hoặc con trái là Null.
Không giảm tính tổng quát, ta giả sử cây con trái của $A$ có chiều cao lớn hơn cây con phải của $A$. Ta có:
Gọi $B = L[A]$. Để cây bằng, ta sẽ thực hiện các phép quay phải, trái, kép như ta đã thực hiện trong bài trước. Để biết khi nào thực hiện phép quay nào, ta cần phải phân tích kĩ hơn cấu trúc của cây con gốc tại $B$. Ta xét các trường hợp sau:
TH1: Cây con trái của $B$ có chiều cao $h-2$
Xem minh họa trong Figure 6(a). Ta sẽ thực hiện phép quay phải (right rotation) tại $A$. Xem minh họa trong Figure 6(b).
Figure 6: (a) Trường hợp cây con trái có chiều cao $h-2$. (b) Cây thu được sau khi thực hiện quay phải tại $A$. Các nút mà ta không đánh dấu bằng các kí hiệu $.,-,+$ có tính cân bằng chưa xác định vì ta chưa biết chiều cao của tất cả các cây con của nó.
Giả mã:
$h \leftarrow height(A)$
$B \leftarrow L[A], L[A] \leftarrow R[B]$
$R[B] \leftarrow A$
$height(A) \leftarrow \max(height(L[A]), height(R[A])) + 1$
$height(B) \leftarrow \max(height(L[B]), height(R[B])) + 1$
return $B$
Code C:
Node *right_rotate(Node *A){
Node *B = A->left;
A->left = B->right;
B->right = A;
A->height = max(height(A->left), height(A->right)) + 1;
B->height = max(height(B->left), height(B->right)) + 1;
return B;
}
Để tìm hiểu tính cân bằng của cây sau khi quay, ta xét hai trường hợp con:
TH1.1: $R[B]$ có chiều cao $h-2$. Trong trường hợp này, sau khi quay, $A$ có chiều cao $h-1$ và $B$ có chiều cao $h$. Chiều cao của $B$ bằng chiều cao trước khi thực hiện phép xóa của $A$. Do đó, tính cân bằng của cây AVL đã được phục hồi. Xem minh họa trong Figure 6(b).
TH1.2: $R[B]$ có chiều cao $h-3$. Sau khi quay, $A$ có chiều cao $h-2$ và do đó, $B$ có chiều cao $h-1$. Chiều cao của $B$ nhỏ hơn chiều cao trước khi thực hiện phép xóa của $A$ một đơn vị. Do đó, sau khi quay, cây AVL có thể bị mất cân bằng tại nút tổ tiên (ancestor) nào đó của $B$. Để phục hồi lại cân bằng, ta phải đệ quy trên nút tổ tiên của $B$ để thực hiện quay. Trong trường hợp xấu nhất, ta phải thực hiện quay đến $O(\log n)$ lần. Xem minh họa trong Figure 6(b).
TH2: Cây con trái của $B$ có chiều cao $h-3$
Vì $B$ có chiều cao $h-1$, con phải của $B$ có chiều cao $h-2$. Gọi $C = R[B]$. Ta có $height(C) = h-2$. Ta thực hiện phép quay kép phải (doubly right rotation) tại $A$. Xem minh họa trong Figure 7.
Giả mã:
$h \leftarrow height(A)$
$B \leftarrow L[A], C \leftarrow R[B]$
$L[A] \leftarrow R[C], R[B] \leftarrow L[C]$
$R[C] \leftarrow A, L[C] \leftarrow B$
$height(A) \leftarrow \max(height(L[A]), height(R[A])) + 1$
$height(B) \leftarrow \max(height(L[B]), height(R[B])) + 1$
$height(C) \leftarrow \max(height(L[C]), height(R[C])) + 1$
return $C$
Code C:
Node * double_right_rotate(Node *A){
Node *B = A->left;
Node *C = B->right;
A->left = C->right;
B->right = C->left;
C->right = A;
C->left = B;
B->height = max(height(B->left), height(B->right)) + 1;
A->height = max(height(A->left), height(A->right)) + 1;
C->height = max(height(C->left), height(C->right)) + 1;
return C;
}
Sau khi quay, không khó để chứng minh rằng:
$height(B) = height(A) = h-2, height(C) = h-1 \qquad (2)$
Vì sau khi quay chiều cao của $C$ nhỏ hơn chiều cao trước khi thực hiện phép xóa của $A$ một đơn vị, mất cân bằng có thể xảy ra tại nút tổ tiên của $C$. Trong trường hợp này, ta phải thực hiện đệ quy trên các nút tổ tiên của $C$. Trong trường hợp xấu nhất, ta phải quay $O(\log n)$ lần để khôi phục tính cân bằng của cây.
Figure 7: (a) Trường hợp cây con trái của $B$ có chiều cao $h-3$. (b) Cây thu được sau khi ta quay kép phải tại $A$. Chú ý sự thay đổi của các kí hiệu $., -, +, --$. Cây sau khi quay kép có chiều cao nhỏ hơn cây trước khi quay $1$ đơn vị, do đó, vẫn có khả năng mất cân bằng xảy ra tại nút tổ tiên.
Giả mã đầy đủ của thủ tục xóa và cân bằng lại cây AVL:
if $k[r]$ < $K$
$R[r] \leftarrow $ Delete($R[r]$, $K$)
else if $k[r]$ > $K$
$L[r] \leftarrow $ Delete($L[r]$, $K$)
else
if $L[r] =$ Null
return $R[r]$
else if $R[r] =$ Null
return $L[r]$
else
$y \leftarrow$ FindMin($R[r]$)
$k[r] \leftarrow k[y]$
$R[r] \leftarrow$ Delete($R[r], k[y]$)
$height[r] \leftarrow $ Max($height(R[r]), height(L[r])$) $+1$
$h \leftarrow height(r)$
if $height(L[r]) = height(R[r]) + 2$
$B \leftarrow L[r]$
if $height(L[B]) = h-2$
return RightRotate($r$) $\ll$TH1 $\gg$
else
return DoubleRightRotate($r$) $\ll$TH2 $\gg$
if $height(R[r]) = height(L[r]) + 2$
$B \leftarrow R[r]$
if $height(R[B]) = h-2$
return LeftRotate($r$) $\ll$TH1 $\gg$
else
return DoubleLeftRotate($r$) $\ll$TH2 $\gg$
return $r$
Code C:
typedef struct Node{
int key;
int value;
struct Node *left, *right;
int height;
} Node;
Node *delete(Node *root, int k){
if(root->key < k){
root->right = delete(root->right, k);
}else if(root->key > k){
root->left = delete(root->left, k);
} else {
if(root->left == null) return root->right;
else if(root->right == null) return root->left;
else {
Node *y = find_min(root->right);
root->key = y->key;
root->value = y->value;
root->right = delete(root->right, y->key);
}
}
root->height = max(height(root->left), height(root->right))+1;
int h = height(root);
if(height(root->left) == height(root->right) + 2){
Node *b = root->left;
if(height(b->left) == h-2){
//printf("we need to do RIGHT ROTATION at %d\n", root->key);
return right_rotate(root);
} else {
//printf("we need to do DOUBLY RIGHT ROTATION at %d\n", root->key);
return double_right_rotate(root);
}
}
if(height(root->right) == height(root->left) + 2){
Node *b = root->right;
if(height(b->right) == h-2){
return left_rotate(root);
} else {
return double_left_rotate(root);
}
}
return root;
}
Node *find_min(Node *root){
if(root->left == null) return root;
else return find_min(root->left);
}
Code đầy đủ: AVL-tree
Do mỗi phép quay đơn hoặc kép ta có thể thực hiện được trong thời gian $O(1)$, tổng thời gian để cây bằng lại cây là $O(\log n)$. Ta có:
Bài tập 1: Áp dụng phép quay để cân bằng lại cây trong Figure 5(b).
Bài tập 2: Sửa đổi lại cây ví dụ trong Figure 5(a) sao cho sau khi quay, cây vẫn bị mất cân bằng.
Bài tập 3: Tìm một cấu trúc cây AVL có $n$ nút sao cho khi xóa một nút khỏi cây, ta phải sử dụng $\Omega(\log n)$ phép quay để khôi phục lại sự cân bằng của cây AVL.
Tham khảo
[1] R. Sedgewick and K. Wayne. Algorithms. Addison-Wesley Professional, 2011.
[2] D. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997.
Recent Comments