AVL Tree in C++

By Prabhanshu Chauhan

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++.

WHAT IS AVL TREE?

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.

WHY AVL 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.

FUNCTIONS INCLUDED:

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.

 

THANK YOU