Cây AVL (AVL tree) trong Python: cây tự cân bằng
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
Trong bài này · 12
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.
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 -1Nú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.
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 103Trướ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:
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 103Sau 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ể.
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útCâ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
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?21-1
Với
lech = Nut(101, phai=Nut(102, phai=Nut(103))), gốc mới saulech.xoay_trai()mang giá trị nào?101103102
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)))
Gọi
xoay_trai()của bài trênNut(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
- Gốc mới là
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ảinut.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áinut.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.
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àyTó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,0hoặc1.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ủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.