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

IncorrectInsert(node r, key k):
    if r = Null
        return MakeNode(k)
    if k[r] < k
        R[r] \leftarrow IncorrectInsert(R[r], k)
    else
        L[r] \leftarrow IncorrectInsert(L[r], k)
    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 Y 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: height(L[A]) = h-2height(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 AB.

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 height(B) \leftarrow h-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[A]
    R[A] \leftarrow L[C], L[B] \leftarrow R[C]
    L[C] \leftarrow A, R[C] \leftarrow B
    height(A) \leftarrow h-1
    height(C) \leftarrow h
    return C

 
Ta không cập nhật chiều cao của B trong giả mã trên vì chiều cao của B không thay đổi. 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:
to-do:code

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.

« Older entries