Uncategorized

You are currently browsing the archive for the Uncategorized category.

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:

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)

 

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.

delete-example
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á 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:

UnbalancedDelete(Node r, Key K):
    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

 

FindMin(Node r):
    if L[r] = Null
        return r
    else
        return FindMin(L[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ó:

Observation 1: Nút bị xóa nằm trong cây con có gốc tại R[A]height(L[A]) = h-1, height(R[A]) = h-3 sau khi xóa.

 

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).

rotate-right
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ã:

RightRotate(node A):
    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

 

Để 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-1B 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

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ã:

DoubleRightRotate(node A):
    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

 
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.

double-right-rotation
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:

Delete(Node r, Key K):
    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)                 \llTH1 \gg
        else
            return DoubleRightRotate(r)                 \llTH2 \gg
    if height(R[r]) = height(L[r]) + 2
        B \leftarrow R[r]
        if height(R[B]) = h-2
            return LeftRotate(r)                 \llTH1 \gg
        else
            return DoubleLeftRotate(r)                 \llTH2 \gg
    return r

 
Code C:
to-do

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ó:

Theorem 1: Phép xóa một nút trong cây AVL có thể thực hiện được trong thời gian O(n), với n là số nút của cây.

 

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.

Tags: , ,

« Older entries