จะเปรียบเทียบ Search Trees ต่างๆ ตามการดำเนินการ มีหลายแบบ ต่างกันในลักษณะ ต้นไม้ค้นหาพื้นฐานคือ Binary Search Tree (BST) อื่นๆ ได้แก่ AVL Tree, B-Tree, Red-Black Tree, Splay Tree
ตารางเปรียบเทียบ Average Case
| Search Tree | Average Case | ||
|---|---|---|---|
| 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) |
ตารางเปรียบเทียบ Worst Case
| Search Tree | Worst Case | ||
|---|---|---|---|
| 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) |
สรุป: BST มี Worst Case O(n) ส่วน AVL, B-Tree, Red-Black, Splay Tree รักษา O(log n) ใน Worst Case ได้
