Cây AVL I -- AVL tree I

Xem bài tiếp theo về AVL tree tại đây.

Trong bài trước, chúng ta đã tìm hiểu sơ bộ về cây nhị phân tìm kiếm, tìm kiếm trên cây và định nghĩa hai loại cây: AVL và cây đỏ đen. Trong bài này ta tìm hiểu cách chèn thêm một khóa vào cây AVL mà vẫn đảm bảo các tính chất của cây AVL sau khi chèn. Bài tiếp theo, chúng ta sẽ tìm hiểu cách xóa một nút khỏi cây AVL.

Một số khái niệm như chiều cao $height(v)$ của một nút $v$, bạn đọc xem lại post trước. Mình chỉ nhắc lại tính chất cân bằng của cây AVL ở đây.

Cây AVL: Mọi nút trong $v$ trong một cây AVL đều thỏa mãn:

$|height(L[v]) - height(R[v])| \leq 1 \qquad (1) $

 
Trong post trước, ta đã chứng minh rằng cây AVL có $n$ nút trong sẽ có chiều cao $O(\log n)$. Ở đây ta vẫn giữ quy ước các nút lá là Null.

Chèn vào cây AVL

Giả sử khóa ta muốn chèn vào trong cây AVL là một khóa mới, i.e, không có khóa nào trong cây có cùng giá trị. Điều này có thể được đảm bảo bằng cách kiểm tra xem khóa đã tồn tại trong cây hay chưa trước khi thực hiện chèn. Sau khi chèn một khóa, ta phải đảm bảo hai điều kiện:

  1. Cây nhị phân sau khi chèn là cây nhị phân tìm kiếm (xem lại định nghĩa tính tìm kiếm tại đây).
  2. Cây nhị phân sau khi chèn vẫn là cây AVL, i.e, phương trình $(1)$ thỏa mãn tại mọi nút của cây.

Để đảm bảo điều kiện (1), ta luôn chèn một khóa mới vào vị trí sao cho nút mới chèn là nút lá của cây. Tạm thời gác lại điều kiện (2), giả mã chèn vào cây như sau:

UnbalancedInsert(node $r$, key $k$):
    if $r = $ Null
        return MakeNode$(k)$
    if $k[r]$ < $k$
        $R[r] \leftarrow $ UnbalancedInsert($R[r], k$)
    else
        $L[r] \leftarrow $ UnbalancedInsert($L[r], k$)
    $height(r) \leftarrow \max(height(L[r]), height(R[r])) + 1$
    return $r$

 

Ví dụ trong Figure 1 dưới đây, ta có một cây AVL với tập khóa $\{2,3,7,9,10,13,14\}$ (Figure 1(a)). Ta chèn thêm khóa 15 vào cây trong Figure 1(a), thu được cây trong Figure 1(b). Dễ dàng kiểm tra được cây trong Figure 1(b) vẫn là cây AVL. Ta chèn tiếp khóa 12 vào Figure 1(b), thu được Figure 1(c). Cây trong Figure 1(c) không còn là cây AVL nữa vì hai nút tô màu đỏ trong cây vi phạm điều kiện trong phương trình $(1)$.
insert-example
Figure 1: (a) một cây AVL. Node có kí hiệu $\{., +, -\}$ lần lượt tương ứng với trường hợp chiều cao con phải bằng chiều cao con trái, chiều cao con phải lớn hơn chiều cao con trái 1 đơn vị và chiều cao con phải nhỏ hơn chiều cao con trái 1 đơn vị. (b) cây thu được sau khi chèn khóa 15. Chú ý sự thay đổi của 3 kí hiệu $\{.,+,-\}$. (c) cây thu được sau khi chèn thêm khóa 12. Hai nút tô màu hồng và có dấu $++$ là nút bị mất cân bằng, chiều cao con phải lớn hơn chiều cao con trái 2 đơn vị tại các nút này.

Phép chèn như trên đảm bảo điều kiện (1) nhưng sau khi chèn, cây mới có thể vi phạm điều kiện cân bằng . Ví dụ trong Figure 1(c), sau khi chèn, các nút $10,7$ đều vi phạm điều kiện cân bằng. Do đó, ta cần một cơ chế để đảm bảo tính cân bằng sau khi chèn. Để hiểu các cơ chế này, trước hết, ta nghiên cứu cấu trúc của các nút bị mất cân bằng. Ta có nhận xét:

Observation 1: Các nút bị mất cân bằng là các nút nằm trên đường đi từ nút mới chèn tới nút gốc.

 
Gọi $X$ là nút mới chèn. Gọi $A$ là nút bị mất cần bằng gần $X$ nhất. Gọi $h$ là chiều cao của nút $A$ trước khi chèn $X$. Không mất tính tổng quát, ta giả sử $X$ được chèn vào cây con phải của $A$. Ta có:

Observation 2: Trước khi chèn $X$, $height(L[A]) = h-2$ và $height(R[A]) = h-1$.

 
Gọi $B$ là nút con phải của $A$. Theo Observation 2, $B \not= $ Null. Bổ đề sau cho chúng ta biết cấu trúc của cây tại nút $B$.

Lemma 1: Trước khi chèn $X$, $height(L[B]) = height(R[B]) = h-2$.

 
Chứng minh: Giả sử $height(L[B])$ < $height(R[B])$. Nếu $X$ được vào cây con phải của $B$ thì nút $B$ sẽ bị mất cân bằng, trái với giả thiết $A$ là nút mất cân bằng gần $X$ nhất. Nếu $X$ được chèn vào cây con trái của $B$ thì chiều cao của $B$ không thay đổi sau khi chèn $X$. Như vậy, $A$ sẽ không bị mất cân bằng. Trái với giả thiết $A$ bị mất cân bằng.

Trường hợp $height(R[B])$ < $height(L[B])$ chứng minh tương tự.


Xem Figure 2 min họa cấu trúc của cây tại $A$ và nút con phải $B$.
AB-structure
Figure 2: Cấu trúc của cây nhị phân tại $A$ và $B$.

Ta xét hai trường hợp.

TH1: $X$ được chèn vào cây con phải của $B$.

Xem minh họa trong Figure 3(a). Trường hợp này ta thực hiện quay trái (left rotation) tại $A$: ta gán con trái của $B$ làm con phải của $A$ và gán $A$ làm con trái của $B$ và cho nút cha của $A$ trỏ vào $B$. Xem minh họa trong Figure 3(b).
rotate-left
Figure 3: (a) nút $A$ bị mất cân bằng (lệch về bên phải) sau khi chèn $X$ vào cây con phải của $B$. (b) phép quay trái tại $A$ để thự hiện cân bằng. Chú ý chiều cao của $A,B$ và sự thay đổi các kí hiệu $\{.,+,-\}$ sau khi quay.

Ta có:

Observation 3: Phép quay trái đảm bảo tính tìm kiếm của cây nhị phân sau khi quay. Ngoài ra, sau khi quay trái tại $A$, nút $B$ có chiều cao $h$ (bằng chiều cao ban đầu của $A$). Do đó, điều kiện (2) được đảm bảo sau phép quay.

Giả mã:

LeftRotate(node $A$):
    $h \leftarrow height(A)$
    $B \leftarrow R[A], R[A] \leftarrow L[B]$
    $L[B] \leftarrow A$
    $height(A) \leftarrow h-1, height(B) \leftarrow h$
    return $B$

 
Code C:

Node *left_rotate(Node *A){
Node *B = A-&gt;right;
A-&gt;right = B-&gt;left;
B-&gt;left = A;
A-&gt;height = max(height(A-&gt;left), height(A-&gt;right)) + 1;
B-&gt;height = max(height(B-&gt;left), height(B-&gt;right)) + 1;
return B;
}

TH2: $X$ được chèn vào cây con trái của $B$.

Gọi $C$ là nút con trái của $B$. Lập luận tương tự như Lemma 1, ta có:

Lemma 2: Trước khi chèn $X$, $height(L[C]) = height(R[C]) = h-3$.

 
Xem minh họa Lemma 2 trong Figure 4(a). Như vậy, sau khi chèn $X$, cây con trái hoặc phải của $C$ sẽ có chiều cao $h-2$, tùy thuộc $X$ bị chèn vào cây con nào.

Trong trường hợp này, ta thực hiện phép quay kép trái (doubly left rotation) tại $A$ như sau: (a) gán con trái của $C$ làm con phải của $A$, (b) gán con phải của $C$ làm con trái của $B$, (c) gán $A$ làm con trái của $C$ và (d) gán $B$ làm con phải của $C$. Xem minh họa trong Figure 4(b).

double-rotate-left
Figure 4:(a) nút $A$ bị mất cân bằng (lệch về bên phải) sau khi chèn $X$ vào cây con trái của $B$. Trong hình trên, ta giả sử $X$ được chèn vào cây con trái của $C$. Nếu $X$ được chèn vào cây con phải của $C$ thì thao tác quay vẫn không thay đổi. (b) phép quay kép trái tại $A$ để thự hiện cân bằng. Chú ý chiều cao của $A,B, C$ và sự thay đổi các kí hiệu $\{.,+,-\}$ sau khi quay.

Observation 4: Phép quay kép trái đảm bảo tính tìm kiếm của cây nhị phân sau khi quay. Ngoài ra, sau khi quay trái tại $A$, nút $C$ có chiều cao $h$ (bằng chiều cao ban đầu của $A$) và $A,B$ đều có chiều cao $h-1$. Do đó, điều kiện (2) được đảm bảo sau phép quay.

Giả mã:

DoubleLeftRotate(node $A$):
    $h \leftarrow height(A)$
    $B \leftarrow R[A], C \leftarrow L[B]$
    $R[A] \leftarrow L[C], L[B] \leftarrow R[C]$
    $L[C] \leftarrow A, R[C] \leftarrow B$
    $height(B) \leftarrow h-1$
    $height(A) \leftarrow h-1$
    $height(C) \leftarrow h$
    return $C$

 

Node * double_left_rotate(Node *A){
Node *B = A-&gt;right;
Node *C = B-&gt;left;
A-&gt;right = C-&gt;left;
B-&gt;left = C-&gt;right;
C-&gt;left = A;
C-&gt;right = B;
B-&gt;height = max(height(B-&gt;left), height(B-&gt;right)) + 1;
A-&gt;height = max(height(A-&gt;left), height(A-&gt;right)) + 1;
C-&gt;height = max(height(C-&gt;left), height(C-&gt;right)) + 1;
return C;
}

Thủ tục chèn đầy đủ như sau:

Insert(node $r$, key $k$):
    if $r = $ Null
        return MakeNode$(k)$
    if $k[r]$ < $k$
        $R[r] \leftarrow $ Insert($R[r], k$)
        if $height(R[r]) = height(L[r])+2$
            $B \leftarrow R[r]$
            if $height(R[B]) = height(L[B]) + 1$
                return LeftRotate$(r)$                     $\ll$ TH1 $ \gg$
            else
                return DoubleLeftRotate$(r)$             $\ll$ TH2 $ \gg$
    else
        $L[r] \leftarrow $ Insert($L[r], k$)
        if $height(L[r]) = height(R[r])+2$
            $B \leftarrow L[r]$
            if $height(L[B]) = height(R[B]) + 1$
                return RightRotate$(r)$
            else
                return DoubleRightRotate$(r)$
    $height(r) \leftarrow \max(height(L[r]), height(R[r]))+1$
    return $r$

 

MakeNode(key $k$):
    node $u \leftarrow$ an empty node
    $k[u] \leftarrow k$
    $L[u] \leftarrow R[u] \leftarrow $ Null
    $height(u) \leftarrow 1$
    return $u$

 

Giả mã của RightRotate DoubleRightRotate coi như bài tập cho bạn đọc. Code đây đủ thủ tục chèn trong C:

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

Node *insert(Node *root, int k, int value){
if(root == null) return create_node(k, value);
if(root-&gt;key &lt; k){
root-&gt;right = insert(root-&gt;right, k, value);
if(height(root-&gt;right) == height(root-&gt;left) + 2){
Node *b = root-&gt;right;
if(height(b-&gt;right) == height(b-&gt;left) + 1){
//printf("we need to do LEFT ROTATION at %d\n", root-&gt;key);
return left_rotate(root);
}else {
//printf("we need to do DOUBLY LEFT ROTATION at %d\n", root-&gt;key);
return double_left_rotate(root);
}
}
}else{	// note: we assume that k is not in the tree
root-&gt;left = insert(root-&gt;left, k, value);
if(height(root-&gt;left) == height(root-&gt;right) + 2){
Node *b = root-&gt;left;
if(height(b-&gt;left) == height(b-&gt;right) + 1){
//printf("we need to do RIGHT ROTATION at %d\n", root-&gt;key);
return right_rotate(root);
} else {
//printf("we need to do DOUBLY RIGHT ROTATION at %d\n", root-&gt;key);
return double_right_rotate(root);
}
}
}
root-&gt;height  = max(height(root-&gt;left), height(root-&gt;right))+1;
return root;
}

Acknowledgement: Cám ơn bạn Nam Nguyen đã chỉ ra một số lỗi sai rất tinh vi trong phiên bản trước của bài vết.

Code đầy đủ: AVL-tree
Tham khảo

[1] G. Adelson-Velsky and E. Landis. An Algorithm for the Organization of Information. Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
[2] D. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997.

Facebook Comments
  1. Duy Pham’s avatar

    Ngay dưới Observation 1 có đề cập đến "Y". Có lẽ đáng ra đó nên là "X".
    Bên cạnh đó, nếu ở Observation 2 bạn ghi cũng ghi là "trước khi chèn X........." thì dễ hiểu hơn.

    Reply

    1. Hung Le’s avatar

      Cám ơn góp ý của Duy! Mình đã sửa theo góp ý của bạn.

      Hùng

      Reply

Reply

Your email address will not be published. Required fields are marked *