Cây nhị phân tìm kiếm (binary search tree) trong Python
Bài 8/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 10 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 13
Cây nhị phân tìm kiếm (binary search tree, viết tắt BST) là cây nhị phân mà mỗi nút lớn hơn mọi giá trị ở cây con trái và nhỏ hơn mọi giá trị ở cây con phải. Nhờ quy tắc đó, muốn tìm một mã khách trong danh bạ, bạn chỉ rẽ trái hay rẽ phải ở mỗi nút thay vì dò lần lượt từng người.
Cần biết trước: cây nhị phân và độ phức tạp Big O.
Quy tắc trái nhỏ, phải lớn
Danh bạ dưới đây cất sáu mã khách từ 101 tới 106. Mỗi nút là một object Nut có giá trị và hai con, con nào chưa có thì là None. Hàm duyet_giua() là phép duyệt giữa (trái, nút, phải) của bài cây nhị phân, trả về list các giá trị.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def duyet_giua(nut):
if nut is None:
return []
trai = duyet_giua(nut.trai)
return trai + [nut.gia_tri] + duyet_giua(nut.phai)
goc = Nut(104, Nut(102, Nut(101), Nut(103)), Nut(106, Nut(105)))
print(duyet_giua(goc))
print(goc.trai.phai.gia_tri, goc.phai.trai.gia_tri)KẾT QUẢ
[101, 102, 103, 104, 105, 106]
103 105Cây con trái của gốc 104 chứa 101, 102, 103, đều nhỏ hơn nó, cây con phải chứa 105, 106, đều lớn hơn. Quy tắc đúng ở từng nút nên duyệt giữa cho thứ tự tăng dần. Đổi Nut(103) thành Nut(107) rồi chạy lại: dòng đầu in [101, 102, 107, 104, 105, 106]. Cây vẫn là cây nhị phân, nhưng 107 nằm bên trái 104 nên cây không còn là cây nhị phân tìm kiếm.
Chèn một giá trị vào cây
Để chèn x, bạn đi từ gốc xuống: x nhỏ hơn giá trị của nút thì sang trái, lớn hơn thì sang phải, cho tới khi gặp chỗ trống None và đặt nút mới vào đó. Hàm chen() viết bằng đệ quy và trả về nút gốc của cây con vừa xử lý, để nút cha gán lại con của mình.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def chen(nut, x):
if nut is None:
return Nut(x)
if x < nut.gia_tri:
nut.trai = chen(nut.trai, x)
elif x > nut.gia_tri:
nut.phai = chen(nut.phai, x)
return nut
goc = None
for ma in [104, 102, 106, 101, 103, 105]:
goc = chen(goc, ma)
print(goc.gia_tri, goc.trai.gia_tri, goc.phai.gia_tri)KẾT QUẢ
104 102 106104 vào trước nên làm gốc, 102 nhỏ hơn nên thành con trái. Giá trị đã có không rơi vào nhánh nào nên bị bỏ qua, danh bạ không có hai mã trùng. Mỗi lần chèn đi đúng một đường từ gốc xuống, nên số bước bằng chiều cao của cây.
Tìm một giá trị và đếm số bước
Tìm cũng đi một đường từ gốc xuống như chèn. Hàm dưới đây dùng vòng lặp while thay cho đệ quy và đếm số nút đã so.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def tim(nut, x):
buoc = 0
while nut is not None:
buoc += 1
if x == nut.gia_tri:
return True, buoc
nut = nut.trai if x < nut.gia_tri else nut.phai
return False, buoc
goc = Nut(104, Nut(102, Nut(101), Nut(103)), Nut(106, Nut(105)))
print(tim(goc, 105), tim(goc, 107))KẾT QUẢ
(True, 3) (False, 2)Tìm 105 đi qua 104, 106 rồi tới 105: ba bước. Tìm 107 gặp None bên phải 106, nên trả về False sau hai bước mà không xem bốn nút còn lại. Mỗi bước bỏ đi cả một cây con, vì vậy cây cân có n nút chỉ cần khoảng log₂ n bước, tức O(log n).
Khi cây bị lệch
Hình dạng của cây phụ thuộc vào thứ tự chèn. Chèn sáu mã theo thứ tự tăng dần thì nút mới nào cũng lớn hơn các nút cũ và rơi sang phải, cây thành một chuỗi giống danh sách liên kết. Ví dụ dựng thẳng chuỗi đó.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def tim(nut, x):
buoc = 0
while nut is not None:
buoc += 1
if x == nut.gia_tri:
return True, buoc
nut = nut.trai if x < nut.gia_tri else nut.phai
return False, buoc
lech = None
for ma in [106, 105, 104, 103, 102, 101]:
lech = Nut(ma, phai=lech)
print(lech.gia_tri, tim(lech, 106), tim(lech, 107))KẾT QUẢ
101 (True, 6) (False, 6)Gốc giờ là 101, và tìm 106 phải đi qua cả sáu nút. Cây lệch có n nút cần tới n bước, tức O(n), không nhanh hơn dò từng phần tử của một list. Cây sâu cũng làm hàm đệ quy dễ chạm giới hạn mặc định khoảng 1000 tầng của Python, nên các ví dụ của bài giữ cây nhỏ. Bài cây AVL chỉ cách giữ cây luôn cân sau mỗi lần chèn.
Xóa một nút
Xóa khó hơn chèn vì nút cần xóa có thể nằm giữa cây. Nút lá thì chỉ cần cắt đi. Nút có một con thì con đó lên thay chỗ. Hàm dưới đây mới lo hai trường hợp này: nut.trai or nut.phai trả về con đang có, hoặc None khi nút là lá.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
def xoa(nut, x):
if nut is None:
return None
if x < nut.gia_tri:
nut.trai = xoa(nut.trai, x)
elif x > nut.gia_tri:
nut.phai = xoa(nut.phai, x)
else:
return nut.trai or nut.phai
return nut
goc = xoa(Nut(104, Nut(102, Nut(101)), Nut(106)), 102)
print(goc.trai.gia_tri, goc.trai.trai)KẾT QUẢ
101 None102 chỉ có con trái 101, nên sau khi xóa, 101 thành con trái của gốc. Trường hợp thứ ba là nút có hai con: không con nào lên thay được mà giữ đúng quy tắc. Cách thường dùng là lấy giá trị nhỏ nhất của cây con phải, tức nút tận cùng bên trái của cây con phải, chép vào nút cần xóa, rồi xóa giá trị đó ở chỗ cũ.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri, self.trai, self.phai = gia_tri, trai, phai
goc = Nut(104, Nut(102, Nut(101), Nut(103)), Nut(106, Nut(105)))
ke = goc.phai
while ke.trai is not None:
ke = ke.trai
print("Thay 104 bằng", ke.gia_tri)
goc.gia_tri = ke.gia_tri
goc.phai.trai = None
print(goc.gia_tri, goc.trai.gia_tri, goc.phai.gia_tri)KẾT QUẢ
Thay 104 bằng 105
105 102 106105 lớn hơn các giá trị bên trái và nhỏ hơn các giá trị còn lại bên phải, nên đứng ở gốc vẫn đúng quy tắc. Ở đây 105 là lá nên cắt thẳng được. Hàm đầy đủ xóa nó bằng chính hàm xóa gọi trên cây con phải, vì nút nhỏ nhất bên phải có thể còn một con phải.
Kiểm tra nhanh
Chèn lần lượt
104,102,106,105vào cây rỗng bằng hàmchen()của bài. Nút105nằm ở đâu?- Con phải của
102 - Con trái của
106 - Con phải của
106
- Con phải của
Trong ví dụ cây lệch,
tim(lech, 101)trả về gì?(True, 1)(True, 6)(False, 6)
Xóa
104khỏi câyNut(104, Nut(102), Nut(106, Nut(105)))theo cách của bài. Gốc mới mang giá trị nào?102106105
Những câu nào đúng về cây nhị phân tìm kiếm trong bài?
- Gọi
chen(goc, 104)khigoclàNonemà không gán lại thìgocvẫn làNone. - Duyệt giữa cho các giá trị theo đúng thứ tự đã chèn vào.
- Hàm tìm đệ quy không kiểm tra
NonebáoAttributeErrorkhi giá trị không có trong cây. - Chèn các giá trị theo thứ tự tăng dần cho ra cây thấp nhất.
- Gọi
Bài tập
Xóa một mã khách khỏi danh bạ
Viết hàm xoa(nut, x) xóa giá trị x khỏi cây nhị phân tìm kiếm có gốc nut, theo ba trường hợp:
Nút lá: bỏ nút đó.
Nút một con: con đó lên thay chỗ.
Nút hai con: chép vào nút giá trị nhỏ nhất của cây con phải, rồi xóa giá trị đó khỏi cây con phải.
x không có trong cây thì cây giữ nguyên. Cây trong bài có tối đa 30 nút, nên đệ quy không chạm giới hạn.
Ví dụ: xóa 103 khỏi cây chèn từ [104, 102, 106, 101, 103, 105] trả về chính nút gốc 104.
Trả về: gốc của cây sau khi xóa, một Nut, hoặc None khi cây không còn nút nào.
class Nut:
def __init__(self, gia_tri, trai=None, phai=None):
self.gia_tri = gia_tri
self.trai = trai
self.phai = phai
def xoa(nut, x):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Cây nhị phân tìm kiếm giữ quy tắc: cây con trái nhỏ hơn nút, cây con phải lớn hơn nút, ở mọi nút.
Duyệt giữa một cây nhị phân tìm kiếm cho các giá trị theo thứ tự tăng dần.
Chèn và tìm đi một đường từ gốc xuống, rẽ trái hay phải theo phép so sánh, nên số bước bằng chiều cao cây.
Cây cân cần khoảng O(log n) bước, cây lệch (chèn theo thứ tự tăng dần) cần O(n).
Xóa có ba trường hợp: nút lá, nút một con, nút hai con thay bằng giá trị nhỏ nhất của cây con phải.
Hàm đệ quy phải gán lại kết quả (
goc = chen(goc, x)) và kiểm traNonetrước khi đọc thuộc tính.
Câu hỏi thường gặp
Thư viện chuẩn có sẵn cây BST cho Python không?
Không có. Khi chỉ cần tra xem một mã có hay không, dict và set đã nhanh hơn cây. Khi cần giữ các giá trị theo thứ tự, bạn có thể giữ một list đã sắp xếp và dùng tìm kiếm nhị phân. Tự viết cây hợp để học và để hiểu các cấu trúc như cây AVL.
Cây nhị phân tìm kiếm trong Python khác cây nhị phân thường ở đâu?
Cây nhị phân chỉ đòi mỗi nút có tối đa hai con. Cây nhị phân tìm kiếm thêm quy tắc về giá trị: trái nhỏ, phải lớn. Nhờ quy tắc đó, việc tìm chỉ đi một đường từ gốc xuống. Ba cách duyệt của cây nhị phân vẫn dùng được, và duyệt giữa cho thứ tự tăng dần.
Xóa nút có hai con thì lấy giá trị nhỏ nhất bên phải hay lớn nhất bên trái?
Cả hai đều giữ đúng quy tắc của cây. Giá trị lớn nhất của cây con trái cũng lớn hơn mọi giá trị còn lại bên trái và nhỏ hơn mọi giá trị bên phải. Bài này và bài tập chọn giá trị nhỏ nhất bên phải. Trong một chương trình, bạn chỉ cần giữ một cách cho thống nhất.
Khi nào cây nhị phân tìm kiếm chậm như dò từng phần tử?
Khi cây bị lệch, thường do chèn dữ liệu đã có thứ tự, như mã khách tăng dần theo ngày đăng ký. Mỗi lần tìm khi đó đi qua gần hết các nút. Cây tự cân bằng như cây AVL xoay lại các nút sau mỗi lần chèn để chiều cao luôn ở mức O(log 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.