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

1
3384
This entry is part 11 of 16 in the series Cấu trúc dữ liệu
90 / 100

Cây AVL: Phần 2

Cây AVL (tiếng Anh là AVL Tree, AVL là viết tắt tên của các tác giả phát minh ra nó Adelson-Velsky và Landis). Cây AVL là một cây tìm kiếm nhị phân có khả năng tự cân bằng, điều đó giúp cho cây AVL tối ưu hơn rất nhiều so với cây tìm kiếm nhị phân (vd. Cây tìm kiếm nhị phân của dãy số tăng dần và node gốc là phần tử đầu tiên). Chúng ta hãy cùng đi tìm hiểu về AVL tree (phần 1 – Insertion) trong bài viết này nhé.

1. Tại sao lại sử dụng cây AVL?

Cây AVL chính sự nâng cấp của cây BST (Binary Search Tree) nên nếu bạn chưa biết gì về cây BST thì hãy đọc bài viết cây tìm kiếm nhị phân này trước khi bắt đầu.

Vậy thì BST có điểm yếu gì mà phải nâng cấp, hãy cùng nhìn:

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Có thể thấy rằng, khi ta thêm các phần tử theo thứ tự tăng dần (giảm dần) thì cây không khác gì một Linked List (Danh sách liên kết). Khi đó, độ phức tạp của thuật toán tìm kiếm của cây là O(n) chứ không phải O(log n). Như vậy, ưu điểm của BST so với Linked List coi như cũng không còn.

2. Cây AVL là gì?

Cây AVL là cây nhị phân tìm kiếm cân bằng với “chiều cao” giữa cây con bên trái và cây con bên phải chênh nhau không vượt quá 1. Hay nói cách khác, BST mà cây con bên trái và phải của mọi Node có “chiều cao” chênh lệch không vượt 1 thì chính là cây AVL.

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Để xây dựng được cây AVL thì các bạn nắm rõ các yếu tố sau:

    1. Khái niệm “chiều cao” và cách tính.
    2. Các kỹ thuật quay cây AVL
    3. Các trường hợp cây bị lệch

3. Xây dựng cây AVL

a. Định nghĩa kiểu dữ liệu các Node

b. Chiều cao của mỗi Node và cách tính

Chiều cao của một Node chính là số các node trên một đường dẫn dài nhất từ Node đó đến Node = NULL. Và quy ước Node = NULL có chiều cao bằng 0.

Cây AVL (AVL Tree) - Phần 1 (Insertion)Bạn có thể tính độ cao qua hàm đệ quy như cách dưới đây. Tuy nhiên, mình sẽ không áp dụng vào code chính bởi vì khi dữ liệu đầu vào cực lớn thì việc đệ quy để tính chiều cao một Node bằng cách dựa vào tất cả các Node con là rất mất thời gian.

c. Các kỹ thuật quay cây AVL

Có thể thấy cây BST khi không cân bằng sẽ bị lệch sang phía bên trái hoặc bên phải. Để điều chỉnh lại ta cần phải quay cây sang phía ngược lại.

i. Kỹ thuật quay phải – áp dụng khi cây bị lệch trái

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Gọi Node x, y lần lượt là các con trái, phải của root. Bây giờ, ta chỉ cần chú ý đến 3 Node: root, x, x.right.

Con trái của root không còn là x nữa mà là x.right hay  root.left = x.right

X sẽ lên làm Node cha với con phải là root hay x.right = root

Về chiều cao, có thể thấy chỉ có 2 Node bị thay đổi chiều cao đó là root và x. Vì root là con của x nên phải tính chiều cao của root trước.

root.height = 1 + max(root.left, root.right)

x.height = 1 + max(x.left, x.right)

ii. Kỹ thuật quay trái – áp dụng khi cây bị lệch phải

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Hoàn toàn tương tự, gọi x y lần lượt là các con trái phải của root. Và ta chỉ cần quan tâm 3 Node: root, y, y.left

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

1. Trường hợp “Trái trái” – Left left

Cây AVL (AVL Tree) - Phần 1 (Insertion)Gọi Node X và Y lần lượt là con trái và con phải của root. Có thể thấy rằng chênh lệch về độ cao giữa X và Y là 3 – 1 = 2 nghiêng về cho x. Điều này nói lên rằng: cây bị lệch sang bên trái.

Tiếp tục, hãy nhìn vào Node màu đỏ vừa mới được thêm vào. Ta có thể thấy: Node đỏ nằm bên trái của Node X hay giá trị Node đỏ < giá trị Node X. Vì vậy nên trường hợp này mới có tên là “Trái trái“.

Tóm lại:

Xảy ra khi: height(X) – height(Y) > 1 và value(Đỏ) < value(X)

Xử lý: quay phải Node root – rotateRight(root)

2. Trường hợp “Trái phải” – Left right

Cây AVL (AVL Tree) - Phần 1 (Insertion)Gọi Node X và Y lần lượt là con của root. Có thể thấy: cây đã bị lệch sang bên trái – khá giống với trường hợp trước. Tuy nhiên điểm khác chính là Node đỏ được thêm vào. Lần này Node đỏ nằm bên phải so với Node X.

Có thể tưởng tượng rằng: khi nhìn tổng quan cây, thì cây bị lệch sang bên trái; còn khi nhìn chi tiết bên trái, thì lại thấy cây nghiêng về bên phải một xíu.

Xử lý: Vì cây con X bị nghiêng sang phải nên chỉ cần quay trái X thì sẽ được trường hợp “Trái trái” như trước. Rồi sau đó quay phải root như trường hợp 1.

Tóm lại:

Xảy ra khi: height(X) – height(Y) > 1 và value(Đỏ) > value(X)

Xử lý: rotateLeft(X) -> rotateRight(root)

3. Trường hợp “Phải phải” – Right right

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Hoàn toàn tương tự “Trái trái” – Left left

Xảy ra khi: height(X) – height(Y) < -1 và value(Đỏ) > value(Y)

Xử lý: rotateLeft(root)

4. Trường hợp “Phải trái” – Right left

Cây AVL (AVL Tree) - Phần 1 (Insertion)

Hoàn toàn tương tự “Trái phải” – Left right

Xảy ra khi: height(X) – height(Y) < -1 và value(Đỏ) < value(Y)

Xử lý: rotateRight(Y) -> rotateLeft(root)

5. Code chính – Insert

Kết quả console

Cảm ơn các bạn đã đọc bài viết của mình. 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.

Tham khảo các cấu trúc dữ liệu khác trong series Cấu trúc dữ liệu.

Thân mến.

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