Chuyển đến nội dung
MINH VO Ghi chép từ công việc
của một kỹ sư tại Việt Nam
Cơ bản6 phút đọc

Phép xoay AVL qua từng thay đổi liên kết

Theo dõi cây con giữa, cập nhật chiều cao và gán lại gốc trả về để cài đặt phép chèn AVL giữ nguyên mọi nút cùng thứ tự khóa.

Đồ thị vẽ bằng bút chì trên giấy màu be, với các đường màu ô liu nối những đỉnh

Phép xoay AVL thay đổi một vùng nhỏ của cây tìm kiếm nhị phân mà giữ nguyên dãy khóa khi duyệt trung thứ tự. Nó sửa mất cân bằng chiều cao bằng cách đưa một nút con lên trên cha và chuyển cây con nằm giữa hai khóa. Với sinh viên đã hiểu tìm kiếm trên cây, theo dõi cây con được chuyển giúp hiểu cơ chế rõ hơn việc học thuộc các hình mang tên LL, RR, LR và RL.

Quy ước cây rỗng có chiều cao bằng không, lá có chiều cao bằng một. Tại mỗi nút AVL, chiều cao cây con trái và phải chênh nhau nhiều nhất một. Hệ số cân bằng là chiều cao trái trừ chiều cao phải. Chiều cao lưu trong nút phải khớp các con thực tế sau mọi thay đổi cấu trúc.

Xoay phải giữ cho cây con giữa vẫn tới được

Giả sử nút bốn có con trái là hai, còn hai có hai con là một và ba. Bốn không có con phải. Cây con gốc bốn bị lệch trái. Xoay phải đưa hai lên làm gốc, đặt bốn thành con phải của hai và chuyển ba thành con trái của bốn.

Trước phép xoay, dãy trung thứ tự là một, hai, ba, bốn. Sau phép xoay, dãy vẫn như vậy. Ba không thể tiếp tục là con phải của hai vì vị trí ấy cần dành cho bốn; nó cũng không thể sang phải của bốn vì ba nhỏ hơn bốn.

Phép xoay phải đưa nút hai lên trên bốn và chuyển nút ba từ con phải của hai sang con trái của bốn, trong khi một vẫn ở bên trái haiMở ảnh kích thước đầy đủ ↗

Lập luận tương tự áp dụng cho cả cây con. Nếu khóa được đưa lên là y và gốc cũ là x, mọi khóa trong y.right đều nằm giữa y và x. Cây con ấy trở thành x.left. Thứ tự khóa không đổi dù quan hệ cha con thay đổi.

Cập nhật nút thấp hơn trước gốc mới

Các con của gốc cũ đổi trước, nên tính lại chiều cao của nó trước khi tính chiều cao gốc được đưa lên. Chiều cao gốc mới phụ thuộc vào chiều cao đã sửa của gốc cũ, giờ nằm bên dưới.

def height(node):
    return node.height if node else 0


class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right
        self.height = 1 + max(height(left), height(right))


def refresh(node):
    node.height = 1 + max(height(node.left), height(node.right))


def rotate_right(x):
    y = x.left
    x.left = y.right
    y.right = x
    refresh(x)
    refresh(y)
    return y


def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    refresh(x)
    refresh(y)
    return y


def rebalance(node):
    refresh(node)
    balance = height(node.left) - height(node.right)
    if balance > 1:
        if height(node.left.left) < height(node.left.right):
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1:
        if height(node.right.right) < height(node.right.left):
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

root = Node(4, Node(2, Node(1), Node(3)))
root = rebalance(root)
assert root.key == 2 and root.right.key == 4
assert root.right.left.key == 3
assert root.height == 3 and root.right.height == 2

Những hàm hỗ trợ này giả sử đang có cây tìm kiếm nhị phân hợp lệ, các cây con đã cân bằng và lưu đúng chiều cao, còn nút hiện tại mang mức mất cân bằng cục bộ do một thao tác cập nhật AVL tạo ra. Chúng không phải thủ tục sửa một cây lệch tùy ý. Hàm chèn hoặc xóa gọi chúng khi quay lại dọc đường tìm kiếm đã thay đổi.

Việc trả về gốc cây con mới là một phần của giao diện hàm. Bên gọi phải gán nó vào liên kết tương ứng của cha hoặc vào gốc toàn cây. Bỏ qua giá trị trả về có thể khiến bên gọi vẫn nhìn thấy gốc cũ, trong khi nút được đưa lên và một phần cấu trúc không còn tới được từ tham chiếu ấy.

Trường hợp xoay kép phải sửa nút con trước

Với thứ tự chèn ba, một, hai, gốc lệch trái nhưng con trái lại lệch phải. Xoay phải trực tiếp vẫn để lại hình dạng mất cân bằng. Trước hết xoay trái cây con trái để đưa hai lên trên một, sau đó xoay phải tại gốc. Kết quả có hai ở gốc, một bên trái và ba bên phải.

Trường hợp đối xứng là chèn một, ba, hai. Ta xoay phải cây con phải rồi xoay trái tại gốc. Với các mẫu thẳng ba, hai, một và một, hai, ba, chỉ cần một phép xoay ngoài. Bốn trường hợp quen thuộc này đều được suy ra từ phía cao hơn tại nút và tại con của nó.

Bài giảng AVL của Cornell trình bày yêu cầu cân bằng cùng các cách sửa. Phần phép xoay trong Open Data Structures giải thích vì sao phép xoay giữ thứ tự tìm kiếm, độc lập với cơ chế cân bằng quyết định lúc nào dùng nó.

Thay đổi cục bộ giúp chặn chiều cao toàn cây

Một phép xoay thay đổi số lượng hằng số liên kết và trường chiều cao. Tìm vị trí cập nhật và đi lại qua các tổ tiên vẫn tốn thời gian tỷ lệ với chiều cao cây. Cân bằng AVL chặn chiều cao theo logarithm vì cây con hợp lệ đủ cao phải chứa đủ nhiều nút ở cả hai nhánh.

Gọi N(h) là số nút nhỏ nhất của cây AVL có chiều cao h. Trong trường hợp ít nút nhất, hai con có chiều cao h - 1 và h - 2. Vì thế N(h) = 1 + N(h - 1) + N(h - 2), với các trường hợp cơ sở là cây rỗng và lá. Tốc độ tăng kiểu Fibonacci khiến chiều cao là O(log n). Bảo đảm cân bằng này cung cấp cận tìm kiếm mà cây tìm kiếm nhị phân thông thường không có.

Phép xóa có thể giảm chiều cao cây con và cần sửa tại nhiều tổ tiên. Các phép so sánh chiều cao con trong hàm có xử lý trường hợp hai chiều cao bằng nhau, vốn quan trọng khi xóa. Nếu cài đặt lưu con trỏ cha, kích thước cây con hoặc thông tin bổ sung khác, nó cũng phải cập nhật chúng; chỉ sửa chiều cao là chưa đủ.

Hãy kiểm tra cả bốn hình dạng chèn ba khóa, rồi thử phép xoay bốn khóa trong hình để phát hiện việc làm mất cây con giữa. Sau khi sửa, kiểm tra dãy trung thứ tự, mọi hệ số cân bằng và mọi chiều cao lưu sẵn. Chỉ đúng khóa ở gốc không chứng minh các hậu duệ còn đủ hoặc lần cập nhật sau sẽ đọc đúng thông tin.

Nối lại mỗi cây con đã đổi trong phép chèn

Một hàm chèn ngắn cho thấy các phép xoay tham gia thao tác cập nhật đầy đủ như thế nào. Đi xuống theo quy tắc tìm kiếm nhị phân, tạo một lá nếu khóa chưa có, rồi cân bằng lại trên đường quay lên. Mỗi lời gọi đệ quy trả về gốc của cây con sau khi sửa, nên cha gán kết quả vào chính liên kết con đã đi theo lúc xuống.

def avl_insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = avl_insert(node.left, key)
    elif key > node.key:
        node.right = avl_insert(node.right, key)
    else:
        return node
    return rebalance(node)

for insertion_order in ([3, 2, 1], [1, 2, 3], [3, 1, 2], [1, 3, 2]):
    tree = None
    for key in insertion_order:
        tree = avl_insert(tree, key)
    assert tree.key == 2
    assert tree.left.key == 1 and tree.right.key == 3
    assert tree.height == 2

old_root = Node(30, Node(10, None, Node(20)))
new_root = rebalance(old_root)
assert new_root.key == 20 and new_root.right is old_root
assert old_root.key == 30 and old_root.left is None and old_root.right is None

Phép gán vào tree trong vòng lặp là thiết yếu tại gốc toàn cây, giống như các phép gán liên kết con bên trong hàm. Trong ví dụ ba mươi, mười, hai mươi, đối tượng gốc cũ vẫn tồn tại dưới dạng con phải của hai mươi. Nếu bỏ qua giá trị trả về, bên gọi vẫn trỏ tới ba mươi và chỉ nhìn thấy lá đó, không còn truy cập được mười và hai mươi từ vị trí tưởng là gốc cây.

Sửa lệch trái phải bắt đầu từ gốc ba mươi, con trái mười và con phải của mười là hai mươi; xoay trong cây con đưa hai mươi lên dưới ba mươi, rồi xoay tại gốc tạo hai mươi với hai con mười và ba mươiMở ảnh kích thước đầy đủ ↗

Trạng thái trung gian có ý nghĩa cụ thể. Trước tiên, phép xoay trái trong cây con trả về hai mươi, và nó phải thay liên kết trái của ba mươi. Chỉ sau đó phép xoay phải tại ba mươi mới đưa đúng nút con đã cập nhật lên trên. Dùng tham chiếu con cũ cho phép xoay ngoài thực hiện một biến đổi khác và có thể làm đứt liên kết tới các nút. Hãy coi gốc trả về là một phần của thay đổi cấu trúc.

Chính sách chèn giữ một bản duy nhất cho mỗi khóa nguyên. Gặp khóa trùng sẽ trả nút hiện có mà không cấp phát lá mới. Hàm sửa trực tiếp các nút đang có; nó không tạo cấu trúc bất biến lưu giữ phiên bản cây trước đó. Các tham chiếu bên ngoài vẫn trỏ tới cùng đối tượng nút, nhưng đối tượng có thể đổi cha sau phép xoay.

Bắt đầu từ một cây AVL hợp lệ, cập nhật đệ quy ở con thiết lập tiền điều kiện cho rebalance: các cây con có chiều cao đúng và thỏa quy tắc cân bằng. Một lần chèn chỉ làm chiều cao con bị thay đổi tăng nhiều nhất một, nên mất cân bằng ở cha là cục bộ và thuộc những trường hợp đã xét. Lập luận ấy không cho phép đưa một cây lệch sẵn tùy ý vào hàm rồi kỳ vọng mọi lỗi cũ sẽ biến mất.

Với bất biến chiều cao được duy trì, phép chèn đi qua O(log n) tổ tiên và làm lượng công việc xoay, cập nhật chiều cao hằng số tại mỗi tổ tiên. Cài đặt đệ quy còn dùng O(log n) lời gọi đang hoạt động; chèn một khóa mới cấp phát thêm đúng một nút. Đó là các phần đóng góp bộ nhớ khác nhau. Phép xóa cần logic tìm kiếm, loại bỏ và sửa ngược lên riêng; ví dụ chèn này không cài đặt phép xóa.

Để luyện tập, chèn một dãy khóa phân biệt và ghi lại danh tính mỗi nút được tạo. Sau từng lần chèn, tính lại chiều cao độc lập từ các con, kiểm tra mọi hệ số cân bằng và xác nhận dãy trung thứ tự. Sau đó chèn khóa trùng, kiểm tra cả số nút lẫn danh tính các nút hiện có đều không đổi. Những phép kiểm tra ấy phát hiện hình dạng gốc trông đúng nhưng bên dưới đã mất hậu duệ hoặc còn chiều cao cũ.

Nguồn tham khảo & đọc thêm

  1. Cornell CS312, AVL trees
  2. Open Data Structures, Binary search tree rotations
← Về trang bài viết

Hình minh họa

100%