Bỏ qua đến nội dung chính
Mục lục

Cây AVL (AVL tree) trong Python: cây tự cân bằng

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 9/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 9 phút
  • Nâng cao
  • Python 3.14
  • Cập nhật

Cây AVL (AVL tree) là cây nhị phân tìm kiếm tự cân bằng: sau mỗi lần chèn, cây xoay lại vài nút để hai cây con của từng nút chênh nhau không quá một tầng. Bạn cần nó khi dữ liệu đến theo thứ tự, như mã khách tăng dần theo ngày đăng ký, vì kiểu dữ liệu đó làm cây nhị phân tìm kiếm thường lệch thành một chuỗi dài.

Cần biết trước: cây nhị phân tìm kiếm.

Hệ số cân bằng của một nút

Chiều cao của một cây là số nút trên đường dài nhất từ gốc xuống lá: cây rỗng cao 0, một nút lá cao 1. Hệ số cân bằng của một nút là chiều cao cây con trái trừ chiều cao cây con phải. Cây AVL đòi hệ số của mọi nút chỉ là -1, 0 hoặc 1.

python
class Nut:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def cao(nut):
    if nut is None:
        return 0
    return 1 + max(cao(nut.trai), cao(nut.phai))

def he_so(nut):
    return cao(nut.trai) - cao(nut.phai)

goc = Nut(104, Nut(102, Nut(101)), Nut(105))
lech = Nut(101, phai=Nut(102, phai=Nut(103)))
print(cao(goc), he_so(goc), he_so(goc.trai), he_so(goc.phai))
print(cao(lech), he_so(lech), he_so(lech.phai))

KẾT QUẢ

3 1 1 0
3 -2 -1

Nút 104 có cây con trái cao 2, cây con phải cao 1, nên hệ số là 1: vẫn cân. Cây lech dựng từ ba mã tăng dần có hệ số gốc -2, nghĩa là bên phải cao hơn bên trái hai tầng, và cần được sửa. Hàm cao() ở đây tính lại chiều cao bằng đệ quy mỗi lần gọi cho ngắn gọn. Cây AVL thật cất sẵn chiều cao trong từng nút để khỏi tính lại. Đổi Nut(105) thành Nut(105, phai=Nut(106)) rồi chạy lại: dòng đầu in 3 0 1 -1.

Phép xoay trái và xoay phải

Phép xoay đổi chỗ một nút với một con của nó mà vẫn giữ quy tắc trái nhỏ, phải lớn. Xoay trái quanh nút x đưa con phải của x lên làm gốc, còn x xuống làm con trái của gốc mới. Ở đây hai phép xoay là phương thức của Nut và trả về gốc mới của cây con.

python
class Nut:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai

    def xoay_trai(self):
        moi = self.phai
        self.phai, moi.trai = moi.trai, self
        return moi

con = Nut(104, Nut(103), Nut(105, phai=Nut(106)))
goc = Nut(102, Nut(101), con).xoay_trai()
print(goc.gia_tri, goc.trai.gia_tri, goc.phai.gia_tri)
print(goc.trai.trai.gia_tri, goc.trai.phai.gia_tri)

KẾT QUẢ

104 102 105
101 103

Trước khi xoay, gốc 102 có hệ số -2. Sau khi xoay, 104 lên gốc và 102 thành con trái của nó. Nút 103 vốn là con trái của 104, giờ chuyển sang làm con phải của 102: nó lớn hơn 102 và nhỏ hơn 104 nên vẫn đúng chỗ. Duyệt giữa trước và sau khi xoay cho cùng một dãy 101 tới 106. Xoay phải là phép đối xứng: con trái lên gốc, nút cũ xuống bên phải.

Bốn kiểu lệch và phép xoay kép

Một nút có hệ số 2 hay -2 rơi vào một trong bốn kiểu, đặt tên theo đường đi từ nút tới phần quá cao. Lệch trái rồi trái thì xoay phải nút đó. Lệch phải rồi phải thì xoay trái. Hai kiểu còn lại khó hơn: con lệch ngược phía với nút. Với kiểu trái rồi phải, một phép xoay đơn không đủ.

Phép xoay kép biến kiểu trái rồi phải thành kiểu trái rồi trái, rồi xử lý như kiểu đơn:

python
class Nut:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
    def xoay_trai(self):
        moi = self.phai
        self.phai, moi.trai = moi.trai, self
        return moi
    def xoay_phai(self):
        moi = self.trai
        self.trai, moi.phai = moi.phai, self
        return moi
goc = Nut(103, Nut(101, phai=Nut(102)))
goc.trai = goc.trai.xoay_trai()
goc = goc.xoay_phai()
print(goc.gia_tri, goc.trai.gia_tri, goc.phai.gia_tri)

KẾT QUẢ

102 101 103

Sau lần xoay đầu, con trái của 103 là 102 có con trái 101, tức một chuỗi lệch trái. Lần xoay thứ hai đưa 102 lên gốc. Kiểu phải rồi trái làm đối xứng: xoay phải con phải, rồi xoay trái nút.

Chèn và vì sao cây AVL luôn thấp

Chèn vào cây AVL bắt đầu như chèn vào cây nhị phân tìm kiếm. Trên đường đệ quy quay về gốc, hàm kiểm hệ số của từng nút đã đi qua và xoay khi nó ra ngoài khoảng -1 tới 1. Mỗi phép xoay chỉ đổi vài con trỏ, nên chèn vẫn tốn khoảng chiều cao của cây, tức O(log n) như bài Big O định nghĩa.

Muốn biết cây AVL thấp tới đâu, hãy đếm số nút ít nhất mà một cây AVL cao h phải có. Cây đó gồm gốc, một cây con cao h - 1 và một cây con cao h - 2, cả hai cũng ít nút nhất có thể.

python
it_nhat = [0, 1]
for h in range(2, 30):
    it_nhat.append(it_nhat[h - 1] + it_nhat[h - 2] + 1)
for h in [3, 5, 10, 20, 29]:
    print(f"cao {h}: ít nhất {it_nhat[h]:,} nút")

KẾT QUẢ

cao 3: ít nhất 4 nút
cao 5: ít nhất 12 nút
cao 10: ít nhất 143 nút
cao 20: ít nhất 17,710 nút
cao 29: ít nhất 1,346,268 nút

Cây cao 29 cần ít nhất 1.346.268 nút. Vì vậy một danh bạ AVL một triệu mã khách cao không quá 28 tầng, và tìm một mã mất tối đa 28 bước. Cây nhị phân tìm kiếm thường nhận một triệu mã tăng dần thì cao đúng một triệu tầng.

Kiểm tra nhanh

  1. Theo cách tính của bài, hệ số cân bằng của nút gốc trong Nut(105, Nut(103, Nut(102), Nut(104)), Nut(106)) bằng bao nhiêu?

    • 2
    • 1
    • -1
  2. Với lech = Nut(101, phai=Nut(102, phai=Nut(103))), gốc mới sau lech.xoay_trai() mang giá trị nào?

    • 101
    • 103
    • 102
  3. Những cây nào cần xoay kép (hai phép xoay) để cân lại?

    • Nut(103, Nut(101, phai=Nut(102)))
    • Nut(103, Nut(102, Nut(101)))
    • Nut(101, phai=Nut(103, Nut(102)))
    • Nut(101, phai=Nut(102, phai=Nut(103)))
  4. Gọi xoay_trai() của bài trên Nut(103, Nut(102, Nut(101))) thì điều gì xảy ra?

    • Gốc mới là 102
    • Python báo lỗi AttributeError
    • Cây giữ nguyên, không có gì xảy ra
Đúng hết lần đầu +15 XP

Bài tập

Cân lại một nút của cây AVL

Viết hàm can_bang(nut) nhận một nút mà hai cây con đã là cây AVL, còn chính nút có thể lệch tới hai tầng sau một lần chèn. Tính hệ số cao(nut.trai) - cao(nut.phai):

  • Lớn hơn 1: con trái có hệ số âm thì xoay trái con trái trước, rồi xoay phải nut.

  • Nhỏ hơn -1: con phải có hệ số dương thì xoay phải con phải trước, rồi xoay trái nut.

  • Còn lại: giữ nguyên nut.

Dùng cao(), xoay_trai(), xoay_phai() có sẵn. Trình chấm còn gọi can_bang() sau mỗi lần chèn để dựng những cây AVL tới 63 nút.

Ví dụ: can_bang(Nut(101, phai=Nut(102, phai=Nut(103)))) trả về nút 102.

Trả về: gốc của cây con sau khi cân, một Nut.

python
class Nut:
    def __init__(self, gia_tri, trai=None, phai=None):
        self.gia_tri, self.trai, self.phai = gia_tri, trai, phai

    def xoay_trai(self):
        moi = self.phai
        self.phai, moi.trai = moi.trai, self
        return moi
    def xoay_phai(self):
        moi = self.trai
        self.trai, moi.phai = moi.phai, self
        return moi

def cao(nut):
    if nut is None:
        return 0
    return 1 + max(cao(nut.trai), cao(nut.phai))

def can_bang(nut):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Hệ số cân bằng của một nút là chiều cao cây con trái trừ chiều cao cây con phải.

  • Cây AVL là cây nhị phân tìm kiếm mà hệ số của từng nút chỉ là -1, 0 hoặc 1.

  • Xoay trái đưa con phải lên gốc, xoay phải đưa con trái lên, và thứ tự duyệt giữa không đổi.

  • Con lệch cùng phía với nút thì xoay đơn, con lệch ngược phía thì xoay kép: xoay con trước, xoay nút sau.

  • Chèn như cây nhị phân tìm kiếm rồi cân lại trên đường về gốc, nên cây chỉ cao khoảng O(log n).

Câu hỏi thường gặp

Cây AVL là gì và vì sao có tên như vậy?

Đó là cây nhị phân tìm kiếm tự giữ hệ số cân bằng của mọi nút trong khoảng -1 tới 1. Tên lấy từ hai tác giả Georgy Adelson-Velsky và Evgenii Landis, công bố cấu trúc này năm 1962 trong bài "An algorithm for the organization of information" (Doklady Akademii Nauk SSSR, tập 146). Đây là kiểu cây tự cân bằng đầu tiên được mô tả.

Python có cây AVL dựng sẵn không?

Thư viện chuẩn không có. Muốn tra nhanh một khóa, bạn dùng dict hay set. Muốn giữ các giá trị theo thứ tự rồi tìm, bạn giữ một list đã sắp xếp và dùng tìm kiếm nhị phân. Tự viết cây AVL hợp khi học, hay khi đề phỏng vấn yêu cầu.

Xóa một nút trong cây AVL làm thế nào?

Xóa như trong cây nhị phân tìm kiếm, rồi trên đường về gốc gọi đúng hàm cân lại cho từng nút đã đi qua. Khác với chèn, một lần xóa có thể cần xoay ở nhiều tầng, vì mỗi lần xoay có thể làm cây con thấp đi một tầng.

Cây AVL khác cây đỏ đen ở đâu?

Cả hai đều là cây nhị phân tìm kiếm tự cân bằng với chiều cao O(log n). Cây AVL giữ cân chặt hơn nên thấp hơn và tìm nhanh hơn một chút. Cây đỏ đen cho phép lệch nhiều hơn, nên khi chèn và xóa thường xoay ít hơn.

Chủ đề

avl tree

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập