Về Chương 4
Cân Bằng Sinh Thái

Tái Cân Bằng BST (Balance a Binary Search Tree)

Từ một cây xiên lệch (O(N)), duỗi ra thành mảng và chống lên thành cây cân bằng (O(logN)).

10
70
20
60
30
50
40
Đang rút mảng...
Cây hiện tại đang bị mất cân bằng (Zig-zag / Skewed). Bắt đầu quá trình Tái Cân Bằng (Rebalance).
Tốc Độ
Thống Kê
Số Bước
0 / 24
Giai Đoạn
Rút Ruột
Tiến Độ

⚖️ Thuật Toán Balance

Một cây BST tồi tệ nhất có dạng như một danh sách liên kết (Skewed Tree), mất đi sức mạnh tìm kiếm O(logN) và chuyển thành O(N).

Để khôi phục, thuật toán tốn O(N) thời gian chuẩn bị:

  • Duyệt Inorder để lấy toàn bộ dữ liệu ra 1 mảng đã sắp xếp.
  • Chọn điểm chính giữa mảng (Mid) làm Gốc mới (Root).
  • Hai nửa mảng còn lại lại tiếp tục được chia đôi đệ quy ghép vào nhánh Trái/Phải.

Kết quả: Cây luôn đạt trạng thái Cân Bằng Hoàn Hảo!