Thursday, 27 June 2013

Trees and their Complexities




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)