Cây nhị phân tìm kiếm (BST) và AVL Tree: Hướng dẫn từ Zero đến Hero
Hướng dẫn toàn diện về Binary Search Tree (BST) và AVL Tree với code Python. Từ BST property, insert/delete operations, đến self-balancing với rotations. Bao gồm interview tips và common LeetCode questions.
Tóm tắt nhanh
- BST (Binary Search Tree): Cấu trúc dữ liệu với quy tắc đơn giản - nhỏ hơn bên trái, lớn hơn bên phải
- Vấn đề: BST thường có thể thoái hóa thành linked list, khiến mọi operation trở thành O(n)
- AVL Tree: Self-balancing BST đầu tiên trong lịch sử (1962), đảm bảo O(log n) cho mọi operation
- Interview tip: Traversals gần như chắc chắn được hỏi, self-balancing cần hiểu WHY hơn là implement chi tiết
Mục lục
- Giới thiệu
- BST Fundamentals: Cái cây "có quy tắc"
- Các Operations cơ bản
- Vấn đề "Cây xiên" - Degenerate Tree
- AVL Tree: Cây tự cân bằng
- Tree Traversals - Duyệt cây
- Interview Tips & Common Questions
- Kết luận
1. Giới thiệu
Cây nhị phân tìm kiếm (Binary Search Tree hay BST) là một trong những cấu trúc dữ liệu quan trọng nhất mà bất kỳ lập trình viên nào cũng cần nắm vững. Năm 1962, hai nhà khoa học máy tính Liên Xô là Georgy Adelson-Velsky và Evgenii Landis đã công bố một phát minh làm thay đổi cách chúng ta nghĩ về cấu trúc dữ liệu cây. Họ đã giải quyết một vấn đề tưởng chừng đơn giản nhưng khiến nhiều programmer đau đầu: làm sao để cây tìm kiếm không bị "nghiêng" về một phía và trở nên vô dụng?
Nếu bạn đang chuẩn bị cho coding interview, có một sự thật cần chấp nhận: câu hỏi về cây nhị phân sẽ xuất hiện. Không phải "nếu" mà là "khi nào". Và việc hiểu sâu về Binary Search Tree cùng người anh em "cân bằng" của nó - AVL Tree - sẽ giúp bạn không chỉ trả lời được câu hỏi, mà còn explain được tại sao mọi thứ hoạt động như vậy.
Trong bài viết này, chúng ta sẽ đi từ khái niệm cơ bản nhất của BST, qua các operations, đến vấn đề "cây xiên" khiến BST thất bại thảm hại, và cuối cùng là cách AVL Tree giải quyết mọi thứ. Không cần thuộc lòng công thức, chỉ cần hiểu nguyên lý.
2. BST Fundamentals: Cái cây "có quy tắc"
2.1 Quy tắc vàng: Nhỏ hơn bên trái, lớn hơn bên phải
Hãy tưởng tượng bạn có một kệ sách được sắp xếp theo tên tác giả từ A đến Z. Khi cần tìm một cuốn sách của tác giả "Nguyễn", bạn không cần duyệt từ đầu kệ. Bạn có thể mở ngay giữa kệ, thấy đang ở "M", vậy "Nguyễn" phải nằm bên phải. Tiếp tục mở giữa phần bên phải, thấy "P", vậy "Nguyễn" nằm bên trái của "P"... Cứ thế, mỗi lần bạn loại bỏ được một nửa kệ sách.
Binary Search Tree hoạt động chính xác như vậy, nhưng với cấu trúc cây:
Hình 1: Cấu trúc Binary Search Tree với root node 8. Các node nhỏ hơn nằm bên trái, lớn hơn nằm bên phải.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
BST Property cực kỳ đơn giản:
- Mọi node trong left subtree có giá trị nhỏ hơn node hiện tại
- Mọi node trong right subtree có giá trị lớn hơn node hiện tại
- Điều này đúng với mọi node trong cây, không chỉ root
Hình minh họa: BST property áp dụng cho MỌI node trong cây, không chỉ root.
Nhìn vào cây trên: node 8 là root. Bên trái có 3, 1, 6, 4, 7 - tất cả đều nhỏ hơn 8. Bên phải có 10, 14, 13 - tất cả đều lớn hơn 8. Và nếu nhìn vào node 3, bên trái có 1 (nhỏ hơn 3), bên phải có 6, 4, 7 (đều lớn hơn 3). Property này đúng với mọi node.
2.2 Recursive nature: Cây con cũng là BST
Đây là insight quan trọng nhất để hiểu và implement BST: mỗi subtree của một BST cũng là một BST hoàn chỉnh. Điều này có nghĩa là khi bạn implement bất kỳ operation nào (search, insert, delete), bạn có thể nghĩ theo cách đệ quy: "Xử lý node hiện tại, rồi đệ quy xuống left/right subtree".
Hãy implement BST cơ bản trong Python:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
Đơn giản vậy thôi. Một node có value và hai pointer đến left/right child. Cây BST chỉ cần giữ reference đến root node.
3. Các Operations cơ bản
3.1 Search - Tìm kiếm O(log n)
Search trong BST là operation đơn giản nhất và cũng thể hiện rõ nhất sức mạnh của cấu trúc này. Thuật toán như sau: so sánh giá trị cần tìm với node hiện tại, nếu nhỏ hơn thì đi sang trái, nếu lớn hơn thì đi sang phải, nếu bằng thì tìm thấy.
def search(self, val):
"""Iterative version - thường được prefer trong interview"""
current = self.root
while current:
if val == current.val:
return current
elif val < current.val:
current = current.left
else:
current = current.right
return None
def search_recursive(self, node, val):
"""Recursive version - code ngắn gọn hơn"""
if not node or node.val == val:
return node
if val < node.val:
return self.search_recursive(node.left, val)
return self.search_recursive(node.right, val)
Mỗi bước so sánh, chúng ta loại bỏ được một nửa cây (giống như binary search trong array). Với một cây cân bằng có n nodes, chiều cao của cây là log(n), nên time complexity là O(log n). Đây chính là lý do BST được ưa chuộng cho các bài toán tìm kiếm.
3.2 Insert - Thêm node mới
Insert về cơ bản là "search đến khi gặp chỗ trống, rồi đặt node mới vào đó". Node mới luôn được thêm như một leaf node (node lá, không có con).
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
current = self.root
while True:
if val < current.val:
if current.left is None:
current.left = TreeNode(val)
return
current = current.left
else: # val >= current.val
if current.right is None:
current.right = TreeNode(val)
return
current = current.right
Ví dụ, insert giá trị 5 vào cây ở trên: 5 < 8 (đi trái) → 5 > 3 (đi phải) → 5 < 6 (đi trái) → 5 > 4 (đi phải) → chỗ trống! Vậy 5 trở thành right child của node 4.
3.3 Delete - Phần khó nhất
Delete là operation phức tạp nhất vì phải xử lý 3 trường hợp khác nhau, và điều quan trọng là sau khi xóa, cây vẫn phải duy trì BST property.
Case 1: Node không có con (leaf node)
Đơn giản nhất - xóa trực tiếp bằng cách set parent's pointer thành None.
Xóa node 4:
8 8
/ \ / \
3 10 → 3 10
/ \ \ / \ \
1 6 14 1 6 14
/ \ / / \ /
4 7 13 X 7 13
Case 2: Node có 1 con
"Bypass" node đó - connect parent trực tiếp với child của node bị xóa.
Xóa node 10 (có 1 con là 14):
8 8
/ \ / \
3 10 → 3 14
/ \ \ / \ /
1 6 14 1 6 13
/
13
Case 3: Node có 2 con - trường hợp tricky
Đây là case khiến nhiều người confused. Giải pháp: tìm in-order successor (node nhỏ nhất trong right subtree) hoặc in-order predecessor (node lớn nhất trong left subtree), copy giá trị của nó vào node cần xóa, rồi xóa node successor/predecessor đó.
Xóa node 3 (có 2 con: 1 và 6):
Bước 1: Tìm in-order successor của 3 → node 4 (min của right subtree)
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
↑
successor
Bước 2: Copy giá trị 4 vào vị trí node 3
8
/ \
4 10 (3 → 4)
/ \ \
1 6 14
/ \ /
4 7 13
↑
cần xóa
Bước 3: Xóa node 4 gốc (đây là leaf, dễ xóa)
8
/ \
4 10
/ \ \
1 6 14
/ \ /
X 7 13
Kết quả: BST property vẫn được bảo toàn!
Tại sao cách này works? Vì in-order successor là node "kế tiếp" trong thứ tự sorted của BST. Nó lớn hơn tất cả nodes trong left subtree của node cần xóa, và nhỏ hơn tất cả nodes còn lại trong right subtree. Vì vậy, khi thay thế, BST property vẫn được bảo toàn.
def delete(self, val):
self.root = self._delete_recursive(self.root, val)
def _delete_recursive(self, node, val):
if not node:
return None
# Tìm node cần xóa
if val < node.val:
node.left = self._delete_recursive(node.left, val)
elif val > node.val:
node.right = self._delete_recursive(node.right, val)
else:
# Tìm thấy node cần xóa
# Case 1 & 2: Không có con hoặc có 1 con
if not node.left:
return node.right
if not node.right:
return node.left
# Case 3: Có 2 con
# Tìm in-order successor (min của right subtree)
successor = self._find_min(node.right)
node.val = successor.val
node.right = self._delete_recursive(node.right, successor.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
4. Vấn đề "Cây xiên" - Degenerate Tree
Bây giờ đến phần plot twist: BST có một vấn đề nghiêm trọng mà nếu không biết, bạn sẽ bị hỏi "Tại sao không dùng BST?" trong interview mà không biết trả lời.
Hãy tưởng tượng bạn insert các giá trị theo thứ tự: 1, 2, 3, 4, 5. Chuyện gì xảy ra?
Insert 1: Insert 2: Insert 3: Insert 4: Insert 5:
1 1 1 1 1
\ \ \ \
2 2 2 2
\ \ \
3 3 3
\ \
4 4
\
5
Cái "cây" này trông giống cái gì? Đúng rồi - một linked list. Và khi BST thoái hóa thành linked list, mọi operation đều trở thành O(n). Search? O(n). Insert? O(n). Delete? O(n). Còn tệ hơn cả một array đã sorted!
Đây không phải là trường hợp hiếm gặp. Trong thực tế, data thường có pattern: timestamps tăng dần, user IDs được assign sequentially, hoặc đơn giản là ai đó insert data đã sorted. Mỗi khi điều này xảy ra, BST của bạn trở nên vô dụng.
So sánh một cách trực quan:
Hình 2: So sánh Balanced Tree O(log n) với Degenerate Tree O(n). Cây cân bằng có hình tam giác, cây thoái hóa như linked list.
Balanced BST (cùng data 1-5): Degenerate BST:
3 1
/ \ \
2 4 2
/ \ \
1 5 3
\
4
\
5
Height: 3 Height: 5
Search 5: 2 bước Search 5: 5 bước
Vấn đề này nghiêm trọng đến mức các nhà khoa học đã dành hàng thập kỷ để tìm giải pháp. Và năm 1962, Adelson-Velsky và Landis đã tìm ra câu trả lời.
5. AVL Tree: Cây tự cân bằng
Hình 3: AVL Tree với Balance Factor (+1, 0, -1) được hiển thị tại mỗi node. Cây luôn duy trì trạng thái cân bằng.
5.1 Balance Factor - Thước đo sự cân bằng
AVL Tree là BST với một constraint bổ sung: mỗi node phải có balance factor trong khoảng -1, 0, hoặc +1.
Balance Factor (BF) = height(left subtree) - height(right subtree)
Hãy nghĩ về nó như một cái cân thăng bằng. Nếu bên trái nặng hơn (BF > 0), nếu bên phải nặng hơn (BF < 0), nếu cân bằng (BF = 0). AVL chỉ cho phép cân lệch tối đa 1 đơn vị.
8 (BF=+1) Cây này là AVL valid
/ \
(BF=0) 3 10 (BF=-1)
/ \ \
1 6 14
/
4
Mỗi node có BF trong {-1, 0, +1}, nên đây là AVL tree hợp lệ.
8 (BF=+2) Cây này KHÔNG PHẢI AVL!
/
3 (BF=+1)
/
1
BF của node 8 = 2 (vi phạm!)
5.2 Tại sao BF <= 1 đảm bảo O(log n)?
Đây là insight quan trọng: khi mọi node có |BF| <= 1, chiều cao của cây với n nodes sẽ luôn nhỏ hơn hoặc bằng 1.44 * log2(n). Không cần chứng minh formal, chỉ cần hiểu rằng AVL tree không cho phép một bên "dài" hơn bên kia quá nhiều, nên cây luôn "mập" thay vì "dài và gầy".
Điều này có nghĩa: dù insert data theo thứ tự nào, dù worst case đến đâu, AVL tree vẫn đảm bảo O(log n) cho search, insert, và delete.
5.3 Rotations - Cách AVL tự cân bằng
Khi một operation (insert hoặc delete) làm |BF| > 1 ở một node nào đó, AVL tree sẽ thực hiện rotation để rebalance. Có 4 loại rotations:
- LL (Left-Left): Cây bị nặng về trái-trái → xoay phải
- RR (Right-Right): Cây bị nặng về phải-phải → xoay trái
- LR (Left-Right): Cây bị nặng về trái-phải → xoay trái rồi xoay phải
- RL (Right-Left): Cây bị nặng về phải-trái → xoay phải rồi xoay trái
Ví dụ đơn giản nhất - LL rotation:
Trước (BF=+2 tại C): Sau khi xoay phải:
C B
/ / \
B → A C
/
A
Rotations là topic khá sâu và xứng đáng có một bài riêng. Nếu bạn muốn hiểu chi tiết cách implement 4 loại rotations với visualization, hãy đọc bài Tree Rotation cho Newbie.
Điều quan trọng cần nhớ cho interview: bạn cần hiểu tại sao cần rotation (để duy trì balance) và biết có 4 loại, nhưng thường không cần implement chi tiết trừ khi interviewer yêu cầu specifically.
6. Tree Traversals - Duyệt cây
Hình 4: Ba loại traversal với thứ tự visit khác nhau - In-order (xanh dương), Pre-order (xanh lá), Post-order (cam).
Traversals là phần "guaranteed to show up" trong interview theo nhiều engineers. Có 3 loại traversal chính, mỗi loại có order khác nhau và ứng dụng riêng.
6.1 In-order Traversal (Left → Root → Right)
def inorder(self, node, result=None):
if result is None:
result = []
if node:
self.inorder(node.left, result)
result.append(node.val)
self.inorder(node.right, result)
return result
Lưu ý: Tránh dùng mutable default argument như
result=[]trong Python - đây là bug phổ biến khiến kết quả bị tích lũy qua các lần gọi hàm.
Đặc điểm magic: In-order traversal của BST cho ra sorted sequence!
Với cây ở đầu bài: in-order cho ra [1, 3, 4, 6, 7, 8, 10, 13, 14] - đúng thứ tự tăng dần.
Ứng dụng quan trọng:
- Validate BST: nếu in-order không sorted → không phải BST
- Convert BST thành sorted array
- Find kth smallest element
6.2 Pre-order Traversal (Root → Left → Right)
def preorder(self, node, result=None):
if result is None:
result = []
if node:
result.append(node.val)
self.preorder(node.left, result)
self.preorder(node.right, result)
return result
Ứng dụng:
- Serialize tree (lưu tree vào file/database)
- Copy/clone tree
- Get prefix expression từ expression tree
6.3 Post-order Traversal (Left → Right → Root)
def postorder(self, node, result=None):
if result is None:
result = []
if node:
self.postorder(node.left, result)
self.postorder(node.right, result)
result.append(node.val)
return result
Ứng dụng:
- Delete tree (xóa children trước khi xóa parent)
- Evaluate expression tree (tính toán expression)
- Calculate size/height của tree
Visualization với cùng một tree
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
In-order: [1, 3, 4, 6, 7, 8, 10, 13, 14] (sorted!)
Pre-order: [8, 3, 1, 6, 4, 7, 10, 14, 13] (root first)
Post-order: [1, 4, 7, 6, 3, 13, 14, 10, 8] (root last)
7. Interview Tips & Common Questions
Những điều interviewer thực sự muốn thấy
Tip 1: Traversals phải thuộc như bản năng
Theo nhiều engineers đã phỏng vấn hàng trăm candidates: "Traversals are basically guaranteed to show up". Bạn cần viết được 3 loại traversal trong vòng 30 giây mà không cần suy nghĩ. Practice đến khi nó trở thành muscle memory.
Tip 2: In-order = Sorted là golden insight
Rất nhiều câu hỏi BST có thể giải bằng cách "in-order traversal rồi xử lý sorted array". Validate BST? In-order phải sorted. Kth smallest? In-order rồi lấy phần tử thứ k. Range sum? In-order rồi sum các phần tử trong range.
Tip 3: Hiểu WHY hơn HOW cho self-balancing trees
Interviewer hiếm khi yêu cầu implement AVL tree từ đầu. Nhưng họ muốn bạn explain được:
- Tại sao cần self-balancing? (Tránh degenerate tree)
- AVL khác gì Red-Black tree? (AVL stricter, better search; Red-Black faster insert/delete)
- Khi nào dùng cái nào? (Read-heavy → AVL, Write-heavy → Red-Black)
Tip 4: Luôn clarify constraints trước khi code
- Có cho phép duplicate values không?
- Range của values là gì? (Integer overflow?)
- Tree có thể empty không?
- Cần return gì khi không tìm thấy?
Common Interview Questions
-
Validate BST - Kiểm tra một binary tree có phải BST không
- Approach 1: In-order traversal phải sorted
- Approach 2: Recursive với min/max bounds
-
Kth Smallest Element - Tìm phần tử nhỏ thứ k
- In-order traversal, đếm đến k
- Hoặc augment BST với subtree size
-
Lowest Common Ancestor (LCA) - Tổ tiên chung gần nhất
- Lợi dụng BST property: nếu cả 2 node < current → LCA ở bên trái
- Nếu cả 2 > current → LCA ở bên phải
- Nếu 1 nhỏ 1 lớn → current chính là LCA
-
Convert Sorted Array to Balanced BST
- Chọn middle element làm root
- Recursive với left half và right half
8. Kết luận
Key Takeaways
-
BST Property cực kỳ đơn giản: left < root < right. Đây là foundation cho mọi thứ khác.
-
In-order traversal của BST = sorted sequence - đây là insight giải được rất nhiều bài interview.
-
Degenerate tree là vấn đề thực tế, không phải edge case lý thuyết. Data sorted, timestamps tăng dần, IDs sequential - tất cả đều có thể khiến BST của bạn thành linked list.
-
AVL Tree là giải pháp đầu tiên (1962), dùng balance factor và rotations để đảm bảo O(log n) mọi lúc.
-
Interview focus: Thuộc traversals, hiểu WHY cần self-balancing, practice các bài classic.
Next Steps
-
Visualize trước, code sau: Sử dụng VisuAlgo để xem BST/AVL hoạt động trực quan. Seeing is believing.
-
Implement từ đầu: Sau khi hiểu concept, tự viết BST class với search, insert, delete, và 3 traversals. Không copy-paste, tự đánh từng dòng.
-
Practice interview questions: LeetCode có rất nhiều bài BST từ Easy đến Hard. Bắt đầu với Validate BST, Kth Smallest, rồi tăng dần độ khó.
Đọc thêm
- Tree Rotation cho Newbie - Deep dive vào 4 loại rotations với step-by-step visualization
- AVL vs Red-Black Tree 2025 - So sánh chi tiết 2 loại self-balancing tree phổ biến nhất
- B-Tree vs AVL trong Database - Tại sao database dùng B-Tree thay vì AVL
Sources:
- VisuAlgo - Interactive BST/AVL Visualization - Tool học trực quan tốt nhất
- Wikipedia - AVL Tree - History và formal definitions
- Interviewing.io - Binary Trees Interview Questions - Interview insights từ real engineers
