AVL trees are height-balanced trees and very useful if used in place of the binary search trees. I've implemented AVL tree data structure in C++.
AVL Tree can be defined as a height-balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.
Searching in a tree costs in the order of its height.
AVL Tree can reduce the cost of searching by a large factor as compared to the Binary search tree.
1. AVL(arr, size): create any number of AVL trees by passing the array of items and their size.
2. insert(root, item): Insert an item into the tree. After inserting, the tree will auto-balance itself in order to reduce the height of the tree.
3. num_child(root): Returns the number of items in the tree.
4. NodeHeight(node): Returns the height of a node in tree. ex- NodeHeight(root) will return the height of root which is the height of the tree.
5. display(root): Display the items of the tree.
6. search(root, key): Return 1 if key found in the tree and 0 if not found.
7. del(root, key): It searches for the key and deletes it from the tree.
Submitted by Prabhanshu Chauhan (prabhanshu)
Download packets of source code on Coders Packet