Giao diện
Balanced BST Operations
🎯 Mục tiêu
Luyện tập cài đặt cây AVL với các phép chèn, xóa kèm xoay cân bằng, kiểm tra tính chất BST và duyệt cây theo thứ tự.
Mô tả bài tập
Cây BST thông thường có thể suy biến O(n), cây AVL tự cân bằng đảm bảo O(log n) cho mọi truy vấn.
Yêu cầu
Bài 1: Cấu trúc Node và các phép xoay
Cài đặt node AVL và các phép xoay: left rotation, right rotation.
python
class AVLNode:
def __init__(self, key: int):
self.key = key
self.left = self.right = None
self.height = 1
def get_height(node: AVLNode) -> int:
pass
def get_balance(node: AVLNode) -> int:
pass
def rotate_right(y: AVLNode) -> AVLNode:
pass
def rotate_left(x: AVLNode) -> AVLNode:
passBài 2: Chèn vào cây AVL
Cài đặt hàm chèn một khóa vào cây AVL với tự động cân bằng.
python
def avl_insert(root: AVLNode, key: int) -> AVLNode:
"""Chèn key vào cây AVL, trả về gốc mới."""
pass
root = None
for key in [10, 20, 30, 40, 50, 25]:
root = avl_insert(root, key)
assert abs(get_balance(root)) <= 1Bài 3: Kiểm tra tính chất BST
Viết hàm kiểm tra xem một cây nhị phân có phải BST hợp lệ hay không.
python
def is_valid_bst(root: AVLNode) -> bool:
"""Kiểm tra cây có thỏa mãn tính chất BST không."""
pass
root = None
for key in [5, 3, 7, 1, 4]:
root = avl_insert(root, key)
assert is_valid_bst(root) == TrueBài 4: Duyệt cây In-order (đệ quy và iterative)
python
def inorder_recursive(root: AVLNode) -> list[int]:
pass
def inorder_iterative(root: AVLNode) -> list[int]:
pass
root = None
for key in [5, 3, 7, 1, 4, 6, 8]:
root = avl_insert(root, key)
assert inorder_recursive(root) == [1, 3, 4, 5, 6, 7, 8]Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Xoay | O(1) | O(1) |
| 2 - Chèn AVL | O(log n) | O(log n) stack |
| 3 - Kiểm tra BST | O(n) | O(n) |
| 4 - In-order duyệt | O(n) | O(n) hoặc O(h) |
Gợi ý
Gợi ý Bài 1
Xoay phải tại y: con trái x trở thành gốc mới, cây con phải của x trở thành con trái của y.
Gợi ý Bài 2
4 trường hợp mất cân bằng: LL → xoay phải, RR → xoay trái, LR → xoay trái con trái rồi xoay phải, RL → xoay phải con phải rồi xoay trái.
Gợi ý Bài 3
Duyệt in-order của BST cho dãy tăng dần, hoặc dùng đệ quy với tham số (node, min_val, max_val).
Lời giải tham khảo
Xem lời giải
python
def get_height(node):
return node.height if node else 0
def get_balance(node):
return get_height(node.left) - get_height(node.right) if node else 0
def rotate_right(y):
x = y.left; t2 = x.right; x.right = y; y.left = t2
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right)); return x
def rotate_left(x):
y = x.right; t2 = y.left; y.left = x; x.right = t2
x.height = 1 + max(get_height(x.left), get_height(x.right))
y.height = 1 + max(get_height(y.left), get_height(y.right)); return y
def avl_insert(root, key):
if not root: return AVLNode(key)
if key < root.key: root.left = avl_insert(root.left, key)
elif key > root.key: root.right = avl_insert(root.right, key)
else: return root
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
if balance > 1 and key < root.left.key: return rotate_right(root)
if balance < -1 and key > root.right.key: return rotate_left(root)
if balance > 1 and key > root.left.key: root.left = rotate_left(root.left); return rotate_right(root)
if balance < -1 and key < root.right.key: root.right = rotate_right(root.right); return rotate_left(root)
return root
def is_valid_bst(root):
def check(node, lo, hi):
if not node: return True
if node.key <= lo or node.key >= hi: return False
return check(node.left, lo, node.key) and check(node.right, node.key, hi)
return check(root, float('-inf'), float('inf'))
def inorder_iterative(root):
result, stack, cur = [], [], root
while cur or stack:
while cur: stack.append(cur); cur = cur.left
cur = stack.pop(); result.append(cur.key); cur = cur.right
return result