Complexity Of Dictionary Operations search(), insert() and delete()
n is number of elements in dictionary
Complexity Of Other Operations ascend(), IndexSearch(index), IndexDelete(index)
D is number of buckets
Definition Of Binary Search Tree A binary tree.
Each node has a (key, value) pair.
For every node x, all keys in the left subtree of x are smaller than that in x.
For every node x, all keys in the right subtree of x are greater than that in x.
Example Binary Search Tree
20 10 6 2 8 15 40 30 25 Only keys are shown.
The Operation ascend()
20 10 6 2 8 15 40 30 25 Do an inorder traversal. O(n) time.
The Operation search()
20 10 6 2 8 15 40 30 25 Complexity is O(height) = O(n), where n is number of nodes/elements.
The Operation insert()
20 10 6 2 8 15 40 30 25 Put a pair whose key is 35. 35
The Operation insert()
Put a pair whose key is 7. 20 10 6 2 8 15 40 30 25 35 7
The Operation insert()
20 10 6 2 8 15 40 30 25 Put a pair whose key is 18. 35 7 18
The Operation search()
20 10 6 2 8 15 40 30 25 Complexity of put() is O(height). 35 7 18
The Operation delete()
Three cases:
Element is in a leaf.
Element is in a degree 1 node.
Element is in a degree 2 node.
Comments