Cấu trúc (Tree) là một cấu trúc dữ liệu phi tuyến tính (non-linear), mô phỏng quan hệ phân cấp như cây gia phả, cấu trúc thư mục trên ổ đĩa, hay DOM trong HTML.

---

1. Cây Nhị Phân Tìm Kiếm (Binary Search Tree - BST)

Một được gọi là BST nếu với mọi nút (Node):

• Mọi nút trên con trái đều có giá trị nhỏ hơn nút hiện tại.
• Mọi nút trên con phải đều có giá trị lớn hơn nút hiện tại.

Kết quả duyệt giữa trên cây tìm kiếm nhị phân

Khi duyệt BST theo thứ tự Inorder (Trái $\to$ Gốc $\to$ Phải), bạn luôn thu được một dãy số tăng dần khi các khóa phân biệt! Ví dụ cây trên: $1\to 3\to 4\to 6$ và $7\to 8\to 10\to 13\to 14$.

---

2. Các Phép Duyệt Cây (Tree Traversals)

Cách duyệt	Thứ tự đi	Ứng dụng phổ biến
Tiền thứ tự (Preorder)	Gốc $\to$ Trái $\to$ Phải	Sao chép , biểu diễn tiền tố (Ba Lan)
Trung thứ tự (Inorder)	Trái $\to$ Gốc $\to$ Phải	Xuất dữ liệu BST theo thứ tự tăng dần
Hậu thứ tự (Postorder)	Trái $\to$ Phải $\to$ Gốc	Giải phóng/xóa bộ nhớ từ dưới lên
Theo mức (Level-order)	Từng tầng từ trên xuống (BFS)	Tìm đường đi ngắn nhất hoặc in theo tầng

---

3. Thao tác Xóa trên BST (Thường Xuất hiện trong Đề thi UET)

Xóa một nút trên BST chia làm 3 trường hợp:

1. Trường hợp 1 (Nút lá): Không có con $\to$ Xóa trực tiếp nút đó.
2. Trường hợp 2 (Nút có 1 con): Nối thẳng con của nó vào cha của nó rồi xóa nút.
3. Trường hợp 3 (Nút có 2 con):
   • Tìm phần tử nhỏ nhất bên con phải (Inorder Successor) hoặc phần tử lớn nhất bên cây con trái.
   • Sao chép giá trị đó đè lên nút cần xóa.
   • Xóa nút thay thế đó (lúc này nút thay thế chỉ rơi vào Trường hợp 1 hoặc 2).

---

4. Hiện tượng Suy biến & Cây Cân bằng (AVL Tree)

Nếu bạn chèn một dãy số đã sắp xếp sẵn gồm 1, 2, 3, 4, 5 vào BST thông thường:

• sẽ biến thành một danh sách liên kết thẳng đứng (chiều cao $h=n$).
• Tốc độ tìm kiếm bị tụt từ $\mathcal{O}(\log n)$ xuống $\mathcal{O}(n)$.

Để khắc phục, người ta phát minh ra cân bằng (AVL Tree / Red-Black Tree):

• Tự động xoay (Left Rotation, Right Rotation) khi hệ số cân bằng (chênh lệch chiều cao 2 nhánh) $>1$ hoặc $<-1$.
• Giữ chiều cao luôn đạt mức $\mathcal{O}(\log n)$.

---

5. Hệ thống bài tập tự luyện

Toàn bộ hệ thống bài tập thực hành chuyên sâu của bài học này đã được tích hợp đầy đủ tại tab Bài tập ở đầu trang. Sau khi đọc xong phần lý thuyết, bạn hãy bấm chuyển sang tab Bài tập để bắt đầu luyện tập.

Chuyển sang Tab Bài tập

Bấm vào tab Bài tập trên thanh điều hướng bài giảng ở đầu trang để mở các bài tập thực chiến có hướng dẫn chi tiết và kiểm chứng tự động.

6. Nguồn tham khảo & Đọc thêm

• VisuAlgo - BST & AVL Tree Simulator - Thử chèn, xóa và quan sát tự động xoay cân bằng.
• Thomas H. Cormen et al., Introduction to Algorithms, Chương 12 (Binary Search Trees) và Chương 13 (Red-Black Trees).