Ở đây chúng ta sẽ xem một số cây tìm kiếm và sự khác biệt của chúng. Có nhiều cây tìm kiếm khác nhau, khác nhau về bản chất. Cây tìm kiếm cơ bản là Cây tìm kiếm nhị phân (Binary Search Tree - BST). Một số cây khác: cây AVL, cây B, cây Đỏ-Đen (Red-Black tree), cây Splay, v.v.
Các cây này có thể so sánh dựa trên thao tác của chúng. Chúng ta sẽ xem độ phức tạp thời gian.
Trường hợp trung bình (Average Case)
| Cây tìm kiếm | Trung bình | ||
|---|---|---|---|
| Insert | Delete | Search | |
| Binary Search Tree | O(log n) | O(log n) | O(log n) |
| AVL tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B Tree | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Splay Tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
Trường hợp xấu nhất (Worst Case)
| Cây tìm kiếm | Xấu nhất | ||
|---|---|---|---|
| Insert | Delete | Search | |
| Binary Search Tree | O(n) | O(n) | O(n) |
| AVL tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B Tree | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Splay Tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |