Cây AVL (AVL Tree) – Phần 2 (Deletion)

0
959
This entry is part 12 of 16 in the series Cấu trúc dữ liệu
90 / 100

Phần 1

Ở bài này, mình sẽ hướng dẫn các bạn cách để “xóa Node – Deletion” trong cây AVL. Và đây cũng là phần cuối của series AVL Tree. Bởi lẽ bản chất của AVL Tree chính là BST (Binary Search Tree) ở dạng cân bằng, do đó ngoài Insert và Delete ra thì các hàm còn lại như search, findMax, print, … viết hoàn toàn giống với hàm của BST.

1. Kiến thức cần nắm

Như đã nói, cây AVL bản chất là cây tìm kiếm nhị phân – BST ở dạng cân bằng. Vì vậy nếu bạn muốn xóa Node ở cây AVL thì phải nắm rõ kiến thức dưới đây. Còn nếu bạn vẫn còn lơ mơ thì hãy đọc lại cho hiểu nhé.

    1. Cách xóa một Node trong cây BST (Cây tìm kiếm nhị phân)
    2. Các trường hợp cây lệch và cách xử lý (AVL Tree – P1 Insertion)

2. Chuyện gì xảy ra nếu xóa một Node?

Chúng ta sẽ xóa một Node của cây AVL giống y như cây BST. Như vậy, sẽ có 3 trường hợp chính đó là:

  1. Node có 0 con (Node lá): Mình chỉ cần giải phóng bộ nhớ Node đó là xong.
  2. Node chỉ có 1 con: Giải phóng Node đó rồi thay bởi Node con.
  3. Node có 2 con: Tìm Node con nhỏ nhất bên phải hoặc lớn nhất bên trái (gọi là temp) rồi gán giá trị Node này cho Node cần xóa sau đó xóa temp. Temp là Node nhỏ nhất (lớn nhất) nên chỉ có thể có 1 hoặc 0 con => Xóa như 2 TH trên.

Cây AVL (AVL Tree) – Phần 2 (Deletion) 1

Có thể thấy rằng: khi xóa Node 5 thì cây đã không còn cân bằng (lệch phải), như vậy thì đây không phải là cây AVL nữa. Và ngoài ra nếu để ý kĩ thì chiều cao của Node 10 vẫn là (2) trong khi đúng ra phải là (1).

Vậy sau khi xóa Node trên cây AVL ta phải làm 2 việc sau:

    1. Cập nhật lại chiều cao.
    2. Xử lý các trường hợp cây bị lệch.

3. Cập nhật chiều cao

Chúng ta sẽ sử dụng đệ quy để duyệt cây, nhằm tìm ra Node cần xóa. Ví dụ cần xóa Node 21 thì duyệt cây như sau:

Cây AVL (AVL Tree) – Phần 2 (Deletion) 2

Có thể thấy, chỉ có các Node nằm trên đường duyệt (xanh lá) mới bị thay đổi về chiều cao. Vậy làm sao để cập nhật lại chiều cao cho các Node đó?

Rất may là vì khi sử dụng đệ quy (recursive) thì chúng ta đã duyệt qua các Node ấy rồi. Nên sau khi xóa thì chỉ cần cập nhật chiều cao một lần là xong.

 

4. Xử lý các trường hợp cây bị lệch.

Ở bài trước, chúng ta đã biết được 4 trường hợp cây bị lệch. Đó là: Trái trái, Trái phải, Phải phải, Phải trái. Về tổng quan (Trái/Phải) thì có biết được cây lệch về phía nào qua giá trị cân bằng. Còn về chi tiết (trái/phải) thì phải kiểm tra qua Node vừa được thêm vào (Insert). Tuy nhiên, lần này là xóa nên không thể làm như trước.

0. Giá trị cân bằng – Value Balance

Vậy để biết được phần chi tiết như thế nào thì chỉ còn cách tính giá trị cân bằng (Value Balance). Mình sẽ viết một hàm kiểm tra giá trị cân bằng để sử dụng nhiều lần.

 

1. Trường hợp cây lệch Trái – Left case

Gọi Node x, y lần lượt là con trái phải của root. Rõ ràng cây bị lệch sang trái khi:

height(x) – height(y) > 1 hay valueBalance(root) > 1

Bây giờ, hãy kiểm tra chi tiết cây lệch qua hướng nào thông qua Node x để xem là trường hợp Trái trái hay Trái phải (Left left or Left right).

a. valueBalance(x) > 0

Cây AVL (AVL Tree) – Phần 2 (Deletion) 3

Rõ ràng, khi height(x.left) > height(x.right) thì đây chính là trường hợp Trái trái – Left left

b. valueBalance(x) < 0

Cây AVL (AVL Tree) – Phần 2 (Deletion) 4

Hiển nhiên, khi height(x.left) < height(x.right) thì đây chính là trường hợp Trái phải – Left right

c. valueBalance(x) = 0

Cây AVL (AVL Tree) – Phần 2 (Deletion) 5

Có thể thấy: cây con X đã cân bằng (height(x.left) = height(x.right)) do đó ta chỉ cần quay phải (rotate right) Node root là xong.

Vì thế nên trường hợp này được tính vào Trái trái – Left left

d. Kết luận

Trường hợp Trái trái – Left left:

Xảy ra khi: valueBalance(root) > 1 && valueBalance(x) >= 0

Xử lí: quay phải Node root – rightRotate(root)

Trường hợp Trái phải – Left right:

Xảy ra khi: valueBalance(root) > 1 && valueBalance(x) < 0

Xử lí: leftRotate(x) => rightRotate(root)

2. Trường hợp cây lệch Phải – Right case

Hoàn toàn tương tự, các bạn có thể tự vẽ ra ở giấy để hiểu bài hơn nhé. Gọi x và y lần lượt là Node trái và phải của root. Ta có:

Trường hợp Phải phải- Right right:

Xảy ra khi: valueBalance(root) < -1 && valueBalance(y) <= 0

Xử lí: quay trái Node root – leftRotate(root)

Trường hợp Phải trái – Right left:

Xảy ra khi: valueBalance(root) < -1 && valueBalance(y) > 0

Xử lí: rightRotate(y) => leftRotate(root)

5. Code chính – Insert + Delete

Kết quả console

Cảm ơn các bạn đã đọc, mình xin kết thúc series AVL Tree tại đây. Nếu thấy Nếu thấy hay thì hãy chia sẽ nó cho mọi người cùng đọc nhé ! Ngoài ra, bạn nào muốn tham khảo code các ngôn ngữ khác thì hãy truy cập vào Geeks for geeks – AVL Tree – Set 2

Thân mến.

Nothing changes if nothing changes. /* Come from HCMUS */
Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments