Binary search tree
|
AVL tree |
Red–black tree |
||||
Average
|
Worst case
|
Average
|
Worst case
|
Average
|
Worst case
|
|
Space
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
Search
|
O(log n)
|
O(n)
|
O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
Insert
|
O(log n)
|
O(n)
|
O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
Delete
|
O(log n)
|
O(n)
|
O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
Splay tree
|
B-Tree
|
Binary Heap
|
||||
Average
|
Worst case
|
Average
|
Worst case
|
Average
|
Worst case
|
|
Space
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
Search
|
O(log n)
|
amortized O(log n)
|
O(log n)
|
O(log n)
|
N/A Operation
|
N/A Operation
|
Insert
|
O(log n)
|
amortized O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
Delete
|
O(log n)
|
amortized O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
O(log n)
|
No comments:
Post a Comment