AVL Tree — Cân bằng tự động
4 case rotation:
Số rotation đã thực hiện: 0 · Số node: 0 · Chiều cao: 0
Chèn từng số. Nếu cân bằng vượt ±1 → tự động rotation.
Số nhỏ bên dưới node: balance factor = height(left) - height(right). Node ĐỎ: balance vượt ±1 trước khi rotation. Node VÀNG: sau rotation.
B-tree vs cây nhị phân: số lần đọc đĩa (README §7.1 / §8.3)
DB lưu dữ liệu trên đĩa/SSD — mỗi tầng cây = 1 lần đọc block (chậm). Cây nhị phân cao log₂(n) tầng;
B-tree gom nhiều khóa/node (1 node = 1 block) nên cao log_fanout(n) → ít tầng hơn nhiều. Kéo thử: