ordered dictionaries:
In such a dictionary the structure maintains an order between keys. This will support actions like minKey(), maxKey(), predecessor(), successor().
We can implement it using list and arrays which are not efficient when considering most of the operations like insert, search, delete. So let us find an efficient way to do this.
Binary Search Tree:
A binary Search tree(BST) is a binary tree that keeps its keys in sorted order so that it facilitates fast key based lookups, insertion and deletion. In this BST tree each node has key and element(or value). If there is a tree(or subtree) with parent as k , then all nodes to left of it are less than k and all nodes to the right of it are greater than k. so binary search tree is also defined as a binary tree in which for every internal node the left and right subtree are themselves binary search trees.
Search for a key in binary tree:
When a key k is searched for in the BST , it initially goes to root node then checks if the key k is equal to root node key. If less than root node key then it goes to left sub tree, if it is greater than the root node key it goes to the right sub tree. Then again in the subtree the root node is checked and then this goes on till either
- node is found equal to k
- not found
then the search ends.
Search takes running time of O(height of tree). This is because each time we come to a node and then makes a decision and then progresses to next level.So it touches each level once. If the searched key is in the final level(which is the worst case) the number of levels traversed is the height of the tree.
We know that height of the binary tree containing n nodes is at most n , so search running time is of the order O(log(n).
This idea of searching in BST seems like resembling how we did binary search on a sorted array. Binary search is a search ALGORITHM on a sorted array. Binary search tree is a tree based DATA STRUCTURE which enables fast search. But the search algorithm used in binary search tree is like the search algorithm defined by binary search on sorted array.
The advantage of having this sought of BST instead of just a sorted array is because though search is almost similar the insertion or deletion is costly in array as it involves shifting after the operation. Whereas in a tree it is just node pointer change.
Minimum key in BST:
To find this, start from the root, and keep going left till the left becomes null. Running time O(height of tree)
Maximum key in BST:
To find this, start from the root, and keep going right till the right becomes null. Running time O(height of tree)
Successor:
The successor of x, node with the smallest key greater than x. How to do ?
If the right sub tree is non empty then the minimum key of the right sub tree is the answer. If the right sub tree is empty then look at the parent of that node and then to its grand parent and so on till you reach a node to which the element you are searching for is to the left.(because the left subtree of a node has all nodes lesser than the subtree root node) Running time O(height of tree)
Insertion:
First Search for the position and then put it there . The position is the point upon navigation when the search returns null.
Deletion:
3 cases based on the number of children the node to be deleted has
- No children
Just remove it directly and set the child (left child or right child which ever the node removed is) of parent to null.
running time is O(1)
- If it has exactly one child
make the child(left or right child) of the node to be removed pointed to as the (left or right child) of the parent of the node removed
(better way to visualize is suppose node A is removed see what child is node A to parent of node A (say PA). if node A is left child of PA then it means we are removing PA's left child. As all nodes to left of PA are less than A, get the only child of A and make PA point to it as its left child.
running time is O(1)
- if it has 2 children
if node A is to be deleted and it has 2 children node B(left) and node C(right). node A's parent is PA(PA's left child is A). then when deleting node A.
what should we point PA to ?
find the predecessor of PA . the predecessor now has one node to its left (but not to right, had it had right it would not have been the predecessor). so finding predecessor confirms that everything in the left subtree is less than PA and then predecessor. so delete PA and replace it with predecessor . if B has a left child make the left child of PA point to the left child of B (as its parent).
here worst case running time is O(height)
AVL Tree:
One problem with BST is that the running time was roughly O(height of tree). so it was depending on height of the tree . If height of the tree is huge(say n) then running time will be worse as O(n). So let us make an effort to solve this problem.
AVL tree is one such tree which tries to solve that problem.
AVL Tree is a binary search tree(BST) in which for every internal node(node other than the leaf is called internal node) the height of the children will DIFFER by 1 or 0.
(height of a node is the height of the subtree rooted at that node)
AVL Tree is also called height balanced tree.
Have we solved the problem ? Have we reduced running time for search from worst of O(n) ? Yes ...
Height of AVL Tree having n keys is O(log(n)). log has base 1.63