AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
An Example Tree that is an AVL Tree:
The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.
An Example Tree that is NOT an AVL Tree:
The above tree is not AVL because differences between heights of left and right subtrees for 8 and 18 is greater than 1.
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this video lecture for proof).
The supported operations are:
- void insert(const ValueType & key, Node **ptr, Node *parent = NULL)
- void erase(const ValueType & key, Node **ptr>
- Node * rotateleft(Node * ptr)
- void rightBig(Node **vertex)
- int getDepth(Node *ptr)
- void updatDepth(Node *ptr)
- int getBalance(Node *ptr)
- void makeBalancePlus(Node **ptr)
- void makeBalanceMinus(Node **ptr)
- Node * Set :: balance(Node * ptr)
The program code was written in the C ++ programming language, therefore, to compile the code, you must install g++. GNU C++ Compiler ( g++ ) is a compiler in Linux which is used to compile C++ programs.
sudo apt-get update
sudo apt-get install g++
make set
If you want to enter your oun set of input numbers, run the program as follows:./set