Cách Vẽ Cây Cân Băng 2 – Hướng Dẫn Chi Tiết Từ Cơ Bản Đến Nâng Cao

Có thể bạn quan tâm: Cách Vẽ Cán Nhân Anime Đơn Giản: Hướng Dẫn Từng Bước Cho Người Mới Bắt Đầu

1. Giới thiệu tổng quan về cây cân băng 2

Cây cân băng (Balance Tree) là một trong những cấu trúc dữ liệu quan trọng trong lĩnh vực khoa học máy tính, được sử dụng rộng rãi trong việc tối ưu hoá các thao tác tìm kiếm, chèn, xóa trên tập hợp dữ liệu. Khi nói đến “cây cân băng 2”, người ta thường đề cập tới một biến thể của cây cân bằng – Cây AVL (Adelson-Velsky and Landis) hay Cây Red-Black, tùy thuộc vào ngữ cảnh. Tuy nhiên, trong cộng đồng lập trình viên Việt Nam, “cây cân băng 2” thường là cách gọi không chính thức cho Cây AVL phiên bản nâng cao, có khả năng tự cân bằng sau mỗi thao tác chèn hoặc xóa, đồng thời hỗ trợ các thao tác mở rộng như cây segment, cây fenwick…

Bài viết này sẽ hướng dẫn bạn cách vẽ cây cân băng 2 một cách chi tiết, từ việc chuẩn bị công cụ, nắm vững các khái niệm cơ bản, cho tới việc triển khai thực tế bằng ngôn ngữ lập trình C++/Java/Python. Mục tiêu cuối cùng là giúp bạn không chỉ hiểu lý thuyết mà còn có thể tự mình vẽ và kiểm tra cây cân băng 2 trên giấy hoặc trên môi trường IDE.

Lưu ý: Bài viết sẽ chia thành nhiều phần, mỗi phần có ví dụ minh hoạ, hình ảnh mô phỏng (được mô tả bằng ký tự ASCII để bạn dễ sao chép). Bạn nên đọc tuần tự để nắm vững từng bước.

Có thể bạn quan tâm: Cách Vẽ Cánh Tủ Cong: Hướng Dẫn Chi Tiết Từ Cơ Bản Đến Nâng Cao

2. Kiến thức nền tảng cần có trước khi vẽ cây cân băng 2

2.1. Cây nhị phân (Binary Tree)

• Định nghĩa: Cây nhị phân là cấu trúc dữ liệu trong đó mỗi nút (node) có tối đa hai con: con trái (left) và con phải (right).
• Thuật ngữ:
• Root: nút gốc.
• Leaf (lá): nút không có con.
• Depth (độ sâu): số cạnh từ gốc tới một nút.
• Height (chiều cao): độ sâu lớn nhất của cây.

2.2. Cây tìm kiếm nhị phân (Binary Search Tree – BST)

• Đặc điểm: Với mỗi nút x, mọi giá trị trong cây con trái x < x và mọi giá trị trong cây con phải x > x.
• Ưu điểm: Tìm kiếm, chèn, xóa trung bình O(log n) nếu cây cân bằng.
• Nhược điểm: Khi dữ liệu đã được sắp xếp, BST có thể biến thành danh sách liên kết, độ phức tạp O(n).

2.3. Tại sao cần cây cân bằng?

Khi BST mất cân bằng, độ sâu cây tăng, dẫn tới thời gian thực thi các thao tác lên tới O(n). Cây cân băng 2 (AVL) giải quyết vấn đề này bằng cách duy trì độ cao cân bằng (balance factor) cho mỗi nút, và thực hiện rotate (xoay) khi cần thiết.

2.4. Định nghĩa “balance factor”

• Balance Factor (BF) = Height(left subtree) – Height(right subtree)
• Giá trị BF hợp lệ cho cây AVL: -1, 0, +1.
• Khi BF vượt ra ngoài phạm vi này, cây cần được cân bằng lại.

3. Các phép quay (rotation) cơ bản trong cây cân băng 2

Để cân bằng lại cây, chúng ta sử dụng 4 loại quay:

Loại quay	Khi nào dùng	Mô tả ngắn
Right Rotation (RR)	BF > 1 và node.left.BF ≥ 0	Quay phải tại nút mất cân bằng.
Left Rotation (LL)	BF < -1 và node.right.BF ≤ 0	Quay trái tại nút mất cân bằng.
Left-Right Rotation (LR)	BF > 1 và node.left.BF < 0	Đầu tiên quay trái tại con trái, rồi quay phải tại nút.
Right-Left Rotation (RL)	BF < -1 và node.right.BF > 0	Đầu tiên quay phải tại con phải, rồi quay trái tại nút.

3.1. Mô tả chi tiết các phép quay (ASCII)

3.1.1. Right Rotation (RR)

 y x / \ Right Rotate / \ x C ----------------> A y / \ / \ A B B C

3.1.2. Left Rotation (LL)

 x y / \ Left Rotate / \ A y ----------------> x C / \ / \ B C A B

3.1.3. Left-Right (LR)

 z z x / \ Left Rotate / \ Right Rotate / \ y D ----------------> x D ----------------> y z / \ / \ / \ / \
A x y C A B C D / \ / \ B C A B

3.1.4. Right-Left (RL)

 z z x / \ Right Rotate / \ Left Rotate / \
A y ----------------> A x ----------------> z y / \ / \ / \ / \ x D B y A B C D / \ / \
B C C D

Những hình trên sẽ là nền tảng khi bạn vẽ cây cân băng 2 trên giấy hoặc trong code.

4. Bước chuẩn bị trước khi vẽ

4.1. Công cụ cần thiết

Có thể bạn quan tâm: Cách Vẽ Cây Cách Điệu: Hướng Dẫn Từng Bước Để Tạo Nên Những Bức Tranh Độc Đáo Và Sáng Tạo

Công cụ	Mô tả	Lưu ý
Bút chì / bút gel	Vẽ sơ đồ cây	Dùng bút nhẹ để có thể sửa đổi khi rotate
Thước kẻ	Đảm bảo các nhánh thẳng	Độ dài mỗi nhánh nên đồng nhất (ví dụ 2-3 cm)
Giấy kẻ ô	Giúp căn chỉnh vị trí nút	Tùy chọn
Phần mềm (optional)	Draw.io, Lucidchart, Visio, hoặc các IDE có plugin vẽ cây	Giúp lưu trữ và chia sẻ nhanh

4.2. Định dạng nút

• Nút: Viết giá trị trong vòng tròn hoặc hình vuông.
• Chiều cao: Ghi dưới nút (có thể bỏ qua nếu không cần).
• Balance Factor: Ghi kèm (BF) ở góc phải hoặc dưới nút.

Ví dụ: 15 (BF=0) hoặc 150.

4.3. Quy tắc vẽ

1. Cột: Mỗi mức độ (depth) của cây sẽ nằm trên một hàng ngang.
2. Khoảng cách: Giữa các nút cùng mức nên đủ rộng để vẽ các nhánh không chồng chéo.
3. Mũi tên: Dùng đường thẳng hoặc đường cong nhẹ để kết nối cha → con.
4. Ký hiệu quay: Khi thực hiện một phép quay, vẽ lại cây mới và đặt chú thích “RR”, “LL”, “LR”, “RL” ở góc trên.

5. Quy trình vẽ cây cân băng 2 – Từ khởi tạo tới cân bằng

5.1. Bước 1: Vẽ cây BST ban đầu (không cân bằng)

Giả sử chúng ta muốn chèn dãy số: 10, 20, 30, 40, 50, 25.

1. Chèn 10 – là gốc.
2. Chèn 20 – nằm bên phải 10.
3. Chèn 30 – nằm bên phải 20 → cây hiện tại đầy 3 nút thẳng → BF của 10 = -2 (không hợp lệ).

Vẽ sơ đồ:

10 (BF=-2) \ 20 (BF=-1) \ 30 (BF=0)

5.2. Bước 2: Kiểm tra balance factor

• Tính chiều cao của mỗi nút (bắt đầu từ lá lên).
• Đánh dấu BF.

Nút	Height	BF
30	1	0
20	2	-1
10	3	-2

Kết luận: Nút 10 mất cân bằng (BF = -2) → LL Rotation.

5.3. Bước 3: Thực hiện phép quay (LL)

Áp dụng Left Rotation tại nút 10:

 20 / \ 10 30

Sau quay, tính lại BF:

Nút	Height	BF
10	1	0
30	1	0
20	2	0

Cây đã cân bằng.

5.4. Bước 4: Tiếp tục chèn các phần tử còn lại

Chèn 40

• So sánh với gốc 20 → > → sang phải 30 → > → sang phải (null) → đặt 40.
• Vẽ lại:

 20 / \ 10 30 \ 40

• Tính BF:
• 40: BF=0
• 30: Height=2, BF=-1
• 20: Height=3, BF=-1 → vẫn hợp lệ (BF trong -1,1).

Chèn 50

• Đặt dưới 40 → cây:

 20 / \ 10 30 \ 40 \ 50

• BF:
• 50:0
• 40: -1
• 30: -2 → LL tại 30.
• Quay trái 30 → cây mới:

 20 / \ 10 40 / \ 30 50

• Tính lại BF → mọi BF đều trong -1,1.

Chèn 25

• So sánh → 20 → > → sang phải 40 → < → sang trái 30 → < → đặt 25.
• Cây:

 20 / \ 10 40 / \ 30 50 / 25

• BF:
• 25:0
• 30: +1
• 40: 0
• 20: 0 → Cây cân bằng.

5.5. Tổng hợp các bước vẽ

Mỗi lần chèn:
1. Vẽ nút mới tại vị trí thích hợp.
2. Cập nhật chiều cao và BF từ nút mới lên tới gốc.
3. Xác định nút mất cân bằng (nếu có) – luôn là nút gần nhất với gốc có BF ngoài -1,1.
4. Chọn loại quay phù hợp dựa trên BF của nút mất cân bằng và con của nó.
5. Thực hiện quay, vẽ lại cây mới, ghi chú loại quay (RR, LL, LR, RL).

6. Ví dụ chi tiết: Vẽ toàn bộ quá trình chèn dãy số 10, 20, 30, 40, 50, 25

6.1. Khởi tạo

Bước 0: (trống)

6.2. Sau khi chèn 10

10 (BF=0)

6.3. Sau khi chèn 20

 10 (BF=-1) \ 20 (BF=0)

6.4. Sau khi chèn 30 → phát sinh LL

Có thể bạn quan tâm: Cách Vẽ Cây Bị Chặt: Hướng Dẫn Chi Tiết Từ Cơ Bản Đến Nâng Cao

 10 (BF=-2) // trước quay \ 20 (BF=-1) \ 30 (BF=0) // Thực hiện LL tại 10 20 (BF=0) / \
10 30

6.5. Sau khi chèn 40

 20 (BF=-1) / \
10 30 \ 40 (BF=0)

6.6. Sau khi chèn 50 → LL tại 30

 20 (BF=-2) // trước quay / \
10 30 (BF=-2) \ 40 \ 50 // LL tại 30 20 (BF=0) / \
10 40 (BF=0) / \ 30 50

6.7. Sau khi chèn 25 → không cần quay

 20 (BF=0) / \
10 40 / \ 30 50 /
25

Kết quả cuối cùng: Cây cân bằng, chiều cao = 3, mọi BF ∈ {-1,0,1}.

7. Thực hiện vẽ cây cân băng 2 bằng code (Python)

Dưới đây là một cài đặt ngắn gọn của cây AVL, kèm hàm print_tree() in ra dạng ascii để bạn dễ dàng “vẽ” trên console.

class Node: __slots__ = ('key', 'left', 'right', 'height') def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 def height(n): return n.height if n else 0 def update_height(n): n.height = 1 + max(height(n.left), height(n.right)) def balance_factor(n): return height(n.left) - height(n.right) def rotate_right(y): x = y.left T2 = x.right # xoay x.right = y y.left = T2 # cập nhật chiều cao update_height(y) update_height(x) return x def rotate_left(x): y = x.right T2 = y.left # xoay y.left = x x.right = T2 # cập nhật chiều cao update_height(x) update_height(y) return y def insert(root, key): if not root: return Node(key) if key < root.key: root.left = insert(root.left, key) else: root.right = insert(root.right, key) update_height(root) bf = balance_factor(root) # LL if bf > 1 and key < root.left.key: return rotate_right(root) # RR if bf < -1 and key > root.right.key: return rotate_left(root) # LR if bf > 1 and key > root.left.key: root.left = rotate_left(root.left) return rotate_right(root) # RL if bf < -1 and key < root.right.key: root.right = rotate_right(root.right) return rotate_left(root) return root # Hàm in cây dạng ascii
def print_tree(node, prefix="", is_left=True): if node: print_tree(node.right, prefix + ("│ " if is_left else " "), False) print(prefix + ("└── " if is_left else "┌── ") + f"{node.key}{balance_factor(node)}") print_tree(node.left, prefix + (" " if is_left else "│ "), True) # Demo
if __name__ == "__main__": seq = 10, 20, 30, 40, 50, 25 root = None for v in seq: root = insert(root, v) print(f"\nSau khi chèn {v}:") print_tree(root)

Kết quả console (rút gọn):

Sau khi chèn 10:
└── 100 Sau khi chèn 20:
└── 20-1 └── 100 Sau khi chèn 30:
└── 200 └── 100 ┌── 300 ...

Bạn có thể chạy đoạn code trên, sao chép output và vẽ lại trên giấy nếu muốn.

8. Các lỗi thường gặp khi vẽ cây cân băng 2 và cách khắc phục

Lỗi	Nguyên nhân	Cách khắc phục
BF sai	Quên cập nhật chiều cao sau khi chèn hoặc xoay.	Luôn gọi update_height(node) ngay sau mỗi thay đổi con.
Quay sai loại	Dựa chỉ vào BF của nút mất cân bằng mà không xét BF của con.	Kiểm tra cả hai BF: của nút và của con trực tiếp để xác định LL, RR, LR, RL.
Nút trùng	Không xử lý trường hợp key == node.key.	Quyết định: bỏ qua, hoặc lưu count, tùy yêu cầu.
Vẽ chồng nhánh	Khoảng cách giữa các nút quá gần.	Dùng thước kẻ, đặt khoảng cách tối thiểu 2-3 cm cho mỗi mức.
Không cân bằng sau xóa	Quên kiểm tra cân bằng trong quá trình quay ngược lên gốc.	Sau khi xóa, thực hiện rebalance cho mỗi ancestor (các nút trên đường đi lên).

9. Mở rộng: Vẽ cây cân băng 2 cho các thuật toán nâng cao

9.1. Cây AVL cho dãy số ngẫu nhiên lớn

Khi dữ liệu lên tới hàng triệu phần tử, việc vẽ bằng tay không khả thi, nhưng nguyên tắc vẫn giữ nguyên. Bạn có thể:

• Sử dụng phần mềm như Graphviz (dot language) để tự động sinh hình ảnh.
• Ghi log các bước quay trong quá trình chèn, sau đó dùng script tạo diagram.

9.2. Cây AVL trong các bài toán thực tế

• Cơ sở dữ liệu: Indexing, tìm kiếm nhanh.
• Hệ thống tệp: B-tree (phiên bản mở rộng) dựa trên nguyên tắc cân bằng.
• Trò chơi: Quản lý leaderboard, xếp hạng người chơi.

9.3. Kết hợp AVL với các cấu trúc khác

• Segment Tree + AVL: Để hỗ trợ truy vấn đoạn nhanh đồng thời giữ cân bằng.
• Fenwick Tree + AVL: Khi cần cập nhật tần suất và truy vấn thứ tự.

10. Tổng kết

• Cây cân băng 2 (AVL) là một công cụ mạnh mẽ giúp duy trì độ sâu tối thiểu, đảm bảo các thao tác trên cây luôn ở mức O(log n).
• Việc vẽ cây không chỉ giúp bạn hình dung cấu trúc mà còn là cách tốt nhất để kiểm tra tính đúng đắn của thuật toán cân bằng.
• Các bước cơ bản: chèn → cập nhật chiều cao → tính BF → xác định nút mất cân bằng → chọn loại quay → thực hiện quay → vẽ lại.
• Khi nắm vững quay trái, quay phải, LR, RL, bạn có thể tự tin vẽ bất kỳ cây AVL nào, dù là trên giấy hay trong môi trường lập trình.
• Đừng quên kiểm tra lại BF sau mỗi thao tác; nếu mọi BF đều trong -1, 1 thì cây đã cân bằng hoàn toàn.

Hy vọng bài viết này đã cung cấp cho bạn một hướng dẫn toàn diện để vẽ cây cân băng 2 từ A đến Z. Hãy thực hành với các dãy số khác nhau, ghi lại từng bước quay và cảm nhận sức mạnh của cây AVL trong việc duy trì cân bằng!

Chúc bạn thành công và luôn “cân bằng” trong mọi thuật toán!