Bạn muốn xem những bài viết hay và ngắn, đừng quên checkout và like facebook page: https://www.facebook.com/thietkegiaithuat/
Bài viết mới: phép xóa một nút khỏi cây AVL.

Bài viết mới: phép chèn trong cây cây AVL.

Bài viết mới: Giới thiệu về cây nhị phân cân bằng.

Bài viết mới: Quy hoạch động trên cây.

Bài viết mới: Mảng mở rộng và ứng dung trong thực thi ngăn xếp/hàng đợi.

Bài viết mới: Danh sách liên kết đơn và các biến thể.

Bài viết mới: Một số bài toán NP-complete khi đầu vào là các số nguyên lớn.

Bài viết mới: Một số bài toán NP-complete trên đồ thị.

Bài viết mới: NP-complete. Bài viết bao gồm lời giải cho bài toán domino-tiling dựa trên bài toán cặp ghép hoàn hảo.

Bài viết mới: P vs NP, bài toán triệu đô của viện Clay.

Bài viết mới: Thuật toán Kosaraju tìm thành phần liên thông mạnh trong đồ thị có hướng.

Bài viết mới: Thuật toán Stoer-Wagner tìm lát cắt cực tiểu trong đồ thị.

Bài viết mới: Một số ứng dụng của bài toán luồng cực đại: cặp ghép cực đại, làm tròn ma trận và phân vùng ảnh.

Bài viết mới: Một số biến thể của bài toán luồng cực đại: luồng với nhiều đỉnh phát-thu, luồng với định mức cạnh và luồng cực đại có chi phí nhỏ nhất.

Bài viết mới: Thuật toán Edmonds-Karp.
Bài viết mới: Thuật toán FordFulkerson. Đây là bài viết đầu tiên trong chuỗi bài về luồng trong mạng.

Bài viết mới: Lý thuyết phổ đồ thị IV Phổ của ma trận kề và bài toán tô màu. Bài thứ 4 trong loạt bài về lý thuyết phổ.
Bài viết mới: Lý thuyết phổ đồ thị III. Bài thứ 3 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị II. Bài thứ 2 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị I. Bài đầu tiên trong loạt bài về lý thuyết phổ.

Bài viết mới: Thuật toán KKT, thuật toán cuối cùng trong loạt bài cây khung nhỏ nhất

Bài viết mới trên facebook: Phát triển giải thuật cho hệ thống gợi ý cho dữ liệu lớn. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán User Hashing và cách chọn Collision Resistant Hash Functions. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Tìm một phần tử trong ma trận và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Puzzle màu mắt dân trên đảo và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: thuật toán Boruvka tìm cây khung nhỏ nhất. Xem tại đây.

Bài viết mới trên facebook: xóa các dòng giống nhau trong file và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm phần tử trội. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: lời giải bài toán tìm một số nguyên không xuất hiện trong file. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: Thuật toán Prim tìm cây khung nhỏ nhất: Xem tại đây.

Mình sẽ start một series các posts nhỏ về giải thuật cho Big-Data trên facebook. Mình có lẽ sẽ repost lại một số bài viết trên facebook tại đây nhưng facebook vẫn là kênh chính để chúng ta thảo luận các topics kiểu này. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm 3 điểm nằm trên cùng một đường thẳng. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: hiểu đúng về độ phức tạp. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới Thuật toán Kruskal cho bài toán cây khung nhỏ nhất.

Bài viết mới trên facebook: bình chọn thuật toán tìm cây khung nhỏ nhất mà bạn yêu thích. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: lời giải bài bug bug bug Xem tại đây.

Bài viết mới: Cơ sở toán học của băm địa chỉ mở và băm hoàn hảo: Xem tại đây.

Bài viết mới trên facebook: tìm bugs. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: bài toán mở cửa và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/.

Bài viết mới: Cơ sở toán học của xích ngăn cách trong phép băm: Xem tại đây.

Bài viết mới trên facebook: lời giải bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán thả trứng và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Một chút về dynamic memory allocation: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: ArrayList trong Java. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Nghịch lí ngày sinh và ứng dụng trong bài toán phân tích thành
nhân tử.

Bài toán mới: Balls into Bins đã được upload lên facebook page. Check out!!!

Mình vừa up một bài toán khá hay về ứng dụng của Heap nhị phân lên trang facebook. Check it out!!!!

Mình vừa tạo một facebook page: https://www.facebook.com/thietkegiaithuat/. Mình sẽ dùng page này để cập nhật những bài viết mới nhất. Ngoài ra, mình cũng sẽ cập nhật những nghiên cứu mới nhất về giải thuật và cấu trúc dữ liệu thông qua page này. Những bài viết trong blog sẽ chỉ là những bài viết về kiến thức cơ bản. Like ngay nếu bạn quan tâm.

tsp

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