Cây DSA AVL

Cây AVL

Sự khác biệt duy nhất giữa Cây tìm kiếm nhị phân thông thường và Cây AVL là Cây AVL còn thực hiện các thao tác xoay để giữ cân bằng cho cây.

Cây tìm kiếm nhị phân cân bằng khi chênh lệch chiều cao giữa cây con trái và cây con phải nhỏ hơn 2.

Bằng cách giữ cân bằng, Cây AVL đảm bảo chiều cao cây tối thiểu, có nghĩa là các thao tác tìm kiếm, chèn và xóa có thể được thực hiện rất nhanh.

Hai cây trên đều là Cây tìm kiếm nhị phân, chúng có cùng nút và cùng duyệt theo thứ tự (theo bảng chữ cái), nhưng chiều cao rất khác nhau do Cây AVL đã tự cân bằng.

Hãy xem qua quá trình xây dựng Cây AVL trong hình động bên dưới để xem cách cập nhật các hệ số cân bằng và cách thực hiện các thao tác xoay khi được yêu cầu để khôi phục lại số dư.

Tiếp tục đọc để tìm hiểu thêm về cách tính hệ số cân bằng, cách thực hiện các thao tác xoay và cách triển khai Cây AVL.

Xoay trái và phải

Để khôi phục lại sự cân bằng trong Cây AVL, việc xoay trái hoặc phải được thực hiện hoặc kết hợp các phép quay trái và phải.

Hoạt ảnh trước đó hiển thị một góc quay trái cụ thể và một góc quay phải cụ thể.

Nhưng nhìn chung, việc xoay trái và phải được thực hiện như trong hình động bên dưới.

Chú ý cây con thay đổi cây cha của nó như thế nào. Cây con thay đổi cha mẹ theo cách này trong quá trình xoay để duy trì việc duyệt theo thứ tự chính xác và để duy trì thuộc tính BST rằng nút con bên trái nhỏ hơn nút con bên phải cho tất cả các nút trong cây.

Cũng nên nhớ rằng không phải lúc nào nút gốc cũng bị mất cân bằng và cần phải xoay.

Yếu tố cân bằng

Hệ số cân bằng của nút là sự khác biệt về chiều cao của cây con.

Chiều cao của cây con được lưu trữ tại mỗi nút cho tất cả các nút trong Cây AVL và hệ số cân bằng được tính dựa trên chiều cao của cây con của nó để kiểm tra xem cây có bị mất cân bằng hay không.

Chiều cao của cây con là số cạnh giữa nút gốc của cây con và nút lá xa nhất trong cây con đó.

Chúng ta hãy xem xét kỹ hơn các thao tác xoay khác nhau mà Cây AVL có thể thực hiện để lấy lại sự cân bằng.

Bốn trường hợp “mất cân bằng”

Khi hệ số cân bằng của chỉ một nút nhỏ hơn -1 hoặc lớn hơn 1, cây được coi là mất cân bằng và cần phải xoay để khôi phục lại sự cân bằng.

Có bốn cách khác nhau mà Cây AVL có thể mất cân bằng và mỗi trường hợp này yêu cầu một thao tác xoay khác nhau.

Xem hình ảnh động và giải thích về những trường hợp này dưới đây.

Trường hợp trái-trái (LL)

Nút nơi phát hiện sự mất cân bằng sẽ bị nặng và nút con bên trái của nút đó cũng bị nặng.

Khi trường hợp LL này xảy ra, một cú xoay phải duy nhất trên nút không cân bằng là đủ để khôi phục lại sự cân bằng.

Hãy xem qua hình ảnh động bên dưới để xem trường hợp LL và cách khôi phục số dư bằng một lần xoay sang phải.

Khi bạn xem qua hình ảnh động ở trên, có hai trường hợp LL xảy ra:

1. Khi thêm D, hệ số cân bằng của Q trở thành -2, nghĩa là cây không cân bằng. Đây là trường hợp LL vì cả nút mất cân bằng Q và nút con trái P của nó đều bị nặng (hệ số cân bằng âm). Một phép quay phải duy nhất tại nút Q sẽ khôi phục lại sự cân bằng của cây.
2. Sau khi thêm các nút L, C và B, hệ số cân bằng của P là -2, nghĩa là cây mất cân bằng. Đây cũng là trường hợp LL vì cả nút P không cân bằng và nút con trái D của nó đều bị nặng. Một vòng quay bên phải sẽ khôi phục lại sự cân bằng.

Trường hợp phải-phải (RR)

Trường hợp Right-Right xảy ra khi một nút không cân bằng và nặng bên phải, và nút con bên phải cũng nặng bên phải.

Một vòng quay trái tại nút không cân bằng là đủ để khôi phục lại sự cân bằng trong trường hợp RR.

Trường hợp RR xảy ra hai lần trong hoạt ảnh trên:

1. Khi nút D được chèn vào, A trở nên mất cân bằng và bot A và B rất nặng. Xoay trái tại nút A sẽ khôi phục lại sự cân bằng của cây.
2. Sau khi các nút E, C và F được chèn vào, nút B trở nên mất cân bằng. Đây là trường hợp RR vì cả nút B và nút con bên phải D của nó đều nặng bên phải. Xoay trái sẽ khôi phục lại sự cân bằng của cây.

Trường hợp trái-phải (LR)

Trường hợp Trái-Phải là khi nút không cân bằng bị nặng bên trái, nhưng nút con bên trái của nó lại nặng bên phải.

Trong trường hợp LR này, việc xoay trái được thực hiện đầu tiên trên nút con bên trái, sau đó phép xoay phải được thực hiện trên nút không cân bằng ban đầu.

Hãy xem qua hình ảnh động bên dưới để xem trường hợp Trái-Phải có thể xảy ra như thế nào và các thao tác xoay được thực hiện như thế nào để khôi phục lại sự cân bằng.

Khi bạn đang xây dựng Cây AVL trong hoạt ảnh ở trên, trường hợp Trái-Phải xảy ra 2 lần và các thao tác xoay là bắt buộc và được thực hiện để khôi phục lại sự cân bằng:

1. Khi K được chèn vào, nút Q sẽ mất cân bằng với hệ số cân bằng là -2, do đó nó nặng bên trái và con trái E của nó nặng bên phải, vì vậy đây là trường hợp Trái-Phải.
2. Sau khi các nút C, F và G được chèn vào, nút K trở nên mất cân bằng và nặng trái, với nút con trái E phải nặng, do đó đây là trường hợp Trái-Phải.

Trường hợp phải-trái (RL)

Trường hợp Right-Left là khi nút không cân bằng nặng bên phải và nút con bên phải của nó nặng bên trái.

Trong trường hợp này, trước tiên chúng tôi thực hiện xoay phải trên nút con bên phải của nút không cân bằng, sau đó chúng tôi thực hiện xoay trái trên chính nút không cân bằng.

Hãy xem qua hình ảnh động bên dưới để xem trường hợp Phải-Trái có thể xảy ra như thế nào và cách thực hiện các phép quay để khôi phục lại sự cân bằng.

Sau khi chèn nút B, chúng ta nhận được trường hợp Phải-Trái vì nút A trở nên mất cân bằng và nặng bên phải, còn nút con bên phải của nó nặng trái. Để khôi phục lại sự cân bằng, việc xoay phải trước tiên được thực hiện trên nút F, sau đó thực hiện phép quay trái trên nút A.

Trường hợp Phải-Trái tiếp theo xảy ra sau khi các nút G, E và D được thêm vào. Đây là trường hợp Right-Left vì B không cân bằng và nặng bên phải, còn con bên phải F của nó nặng trái. Để khôi phục lại sự cân bằng, việc xoay phải trước tiên được thực hiện trên nút F, sau đó thực hiện phép quay trái trên nút B.

Truy xuất trong cây AVL

Sau khi chèn hoặc xóa một nút trong cây AVL, cây có thể trở nên mất cân bằng. Để tìm hiểu xem cây có mất cân bằng hay không, chúng ta cần cập nhật độ cao và tính toán lại hệ số cân bằng của tất cả các nút tổ tiên.

Quá trình này, được gọi là truy vết, được xử lý thông qua đệ quy. Khi các lệnh gọi đệ quy truyền trở lại gốc sau khi chèn hoặc xóa, chiều cao của mỗi nút tổ tiên sẽ được cập nhật và hệ số cân bằng được tính toán lại. Nếu bất kỳ nút tổ tiên nào được phát hiện có hệ số cân bằng nằm ngoài phạm vi từ -1 đến 1, một phép quay sẽ được thực hiện tại nút đó để khôi phục lại sự cân bằng của cây.

Trong mô phỏng bên dưới, sau khi chèn nút F, các nút C, E và H đều không cân bằng, nhưng do quá trình truy tìm hoạt động thông qua đệ quy nên sự mất cân bằng tại nút H được phát hiện và sửa trước tiên, trong trường hợp này cũng sửa được sự mất cân bằng trong các nút E và C.

Sau khi nút F được chèn vào, mã sẽ truy xuất, tính toán các hệ số cân bằng khi nó truyền ngược lên nút gốc. Khi đạt đến nút H và hệ số cân bằng -2 được tính toán, việc xoay phải được thực hiện. Chỉ sau khi quá trình xoay này hoàn tất, mã sẽ tiếp tục truy xuất, tính toán các hệ số cân bằng hơn nữa trên các nút tổ tiên E và C.

Do xoay vòng nên hệ số cân bằng cho nút E và C vẫn giữ nguyên như trước khi chèn nút F.

Triển khai nút chèn AVL

Mã này dựa trên việc triển khai BST ở trang trước để chèn các nút.

Chỉ có một thuộc tính mới cho mỗi nút trong cây AVL so với BST, đó là chiều cao, nhưng có nhiều hàm mới và dòng mã bổ sung cần thiết cho việc triển khai Cây AVL do cách Cây AVL tự cân bằng lại.

Việc triển khai bên dưới xây dựng cây AVL dựa trên danh sách các ký tự, để tạo Cây AVL trong mô phỏng ở trên. Nút cuối cùng được chèn 'F', cũng kích hoạt xoay phải, giống như trong mô phỏng ở trên.

 class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    print('Rotate right on node',y.data)
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    return x

def leftRotate(x):
    print('Rotate left on node',x.data)
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

    if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Left Left
    if balance > 1 and data < node.left.data:
        return rightRotate(node)

    # Right Right
    if balance < -1 and data > node.right.data:
        return leftRotate(node)

    # Left Right
    if balance > 1 and data > node.left.data:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Left
    if balance < -1 and data < node.right.data:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)

Thực hiện nút xóa AVL

Khi xóa một nút không phải là nút lá, Cây AVL yêu cầu hàm minValueNode() để tìm nút tiếp theo của nút trong quá trình truyền tải theo thứ tự. Điều này giống như khi xóa một nút trong Cây tìm kiếm nhị phân, như đã giải thích ở trang trước.

Để xóa một nút trong Cây AVL, cần có cùng một mã để khôi phục lại số dư như mã để chèn một nút.

 def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete(node, data):
    if not node:
        return node

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        if node.left is None:
            temp = node.right
            node = None
            return temp
        elif node.right is None:
            temp = node.left
            node = None
            return temp

        temp = minValueNode(node.right)
        node.data = temp.data
        node.right = delete(node.right, temp.data)

    if node is None:
        return node

    # Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

    # Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

    # Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

Độ phức tạp về thời gian của cây AVL

Hãy xem Cây tìm kiếm nhị phân không cân bằng bên dưới. Tìm kiếm "M" có nghĩa là tất cả các nút ngoại trừ 1 phải được so sánh. Nhưng việc tìm kiếm “M” trong Cây AVL bên dưới chỉ yêu cầu chúng ta truy cập 4 nút.

Vì vậy, trong trường hợp xấu nhất, các thuật toán như tìm kiếm, chèn, xóa phải chạy hết chiều cao của cây. Điều này có nghĩa là việc giữ chiều cao (\(h \)) của cây ở mức thấp, giống như cách chúng ta sử dụng Cây AVL, sẽ mang lại cho chúng ta thời gian chạy thấp hơn.

Xem phần so sánh độ phức tạp về thời gian giữa Cây tìm kiếm nhị phân và Cây AVL bên dưới và mức độ phức tạp về thời gian liên quan đến chiều cao (\(h\)) của cây và số lượng nút (\(n\)) trong cây.

• BST không tự cân bằng. Điều này có nghĩa là BST có thể rất mất cân bằng, gần giống như một chuỗi dài, trong đó chiều cao gần bằng số lượng nút. Điều này làm cho các hoạt động như tìm kiếm, xóa và chèn nút bị chậm, với độ phức tạp về thời gian \(O(h) = O(n)\).
• Tuy nhiên, cây AVL có khả năng tự cân bằng. Điều đó có nghĩa là chiều cao của cây được giữ ở mức tối thiểu để các hoạt động như tìm kiếm, xóa và chèn nút nhanh hơn nhiều, với độ phức tạp về thời gian \(O(h) = O( \log n)\).

\(O( \log n)\) Giải thích

Thực tế là độ phức tạp về thời gian là \(O(h) = O( \log n)\) để tìm kiếm, chèn và xóa trên Cây AVL có chiều cao \(h\) và các nút \(n\) có thể được giải thích như thế này:

Hãy tưởng tượng một Cây nhị phân hoàn hảo trong đó tất cả các nút đều có hai nút con ngoại trừ ở mức thấp nhất, như Cây AVL bên dưới.

Số nút ở mỗi cấp trong Cây AVL như vậy là:

\[1, 2, 4, 8, 16, 32, ..\]

Điều này giống như:

\[2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ..\]

Để có được số nút \(n\) trong Cây nhị phân hoàn hảo có chiều cao \(h=3\), chúng ta có thể cộng số nút ở mỗi cấp với nhau:

\[n_3=2^0 + 2^1 + 2^2 + 2^3 = 15\]

Điều này thực sự giống như:

\[n_3=2^4 - 1 = 15\]

Và đây thực sự là trường hợp của những cây lớn hơn! Ví dụ: nếu chúng ta muốn lấy số nút \(n \) trong một cây có chiều cao \(h=5 \) thì chúng ta sẽ tìm số lượng nút như thế này:

\[n_5=2^6 - 1 = 63\]

Vì vậy, nói chung, mối quan hệ giữa chiều cao \(h \) của Cây nhị phân hoàn hảo và số nút trong đó \(n \), có thể được biểu thị như sau:

\[n_h = 2^{h+1} - 1\]

Chúng tôi biết rằng độ phức tạp về thời gian để tìm kiếm, xóa hoặc chèn một nút trong cây AVL là \(O(h) \), nhưng chúng tôi muốn lập luận rằng độ phức tạp về thời gian thực sự là \(O(\log(n)) \), vì vậy chúng ta cần tìm chiều cao \(h\) được mô tả bằng số nút \(n\):

\[ \begin{equation} \begin{aligned} n & = 2^{h+1}-1 \\ n+1 & = 2^{h+1} \\ \log_2(n+1) & = \ log_2(2^{h+1}) \\ h & = \log_2(n+1) - 1 \\ \\ O(h) & = O(\log{n}) \end{aligned} \end{ phương trình} \]

Dòng cuối cùng ở trên có nguồn gốc như thế nào có thể không rõ ràng, nhưng đối với Cây nhị phân có nhiều nút (lớn \(n\)), các thuật ngữ "+1" và "-1" không quan trọng khi chúng ta xem xét độ phức tạp về thời gian . Để biết thêm chi tiết về cách tính độ phức tạp thời gian bằng ký hiệu Big O, hãy xem trang này .

Phép toán trên cho thấy độ phức tạp về thời gian của các thao tác tìm kiếm, xóa và chèn trên Cây AVL \(O(h) \), thực tế có thể được biểu thị dưới dạng \(O(\log{n}) \), rất nhanh , nhanh hơn rất nhiều so với độ phức tạp về thời gian của BST là \(O(n) \).

Bài tập DSA

Kiểm tra bản thân bằng các bài tập

Bài tập:

Mỗi nút trong Cây AVL bên dưới được hiển thị cùng với hệ số cân bằng của nó:

Yếu tố cân bằng là gì?

Hệ số cân bằng là 
sự khác biệt giữa mỗi nút 
cây con trái và phải .

Cung cấp câu trả lời "

Bắt đầu bài tập