A self balancing BST is one which always tries to maintain it's height as minimum as possible. A clearer definition:
In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions 1
This repo implements the same with the method called AVL Trees (Adelson-Velsky-Landis Trees), invented by Georgy Adelson-Velsky and Evgenii Landis.
Any tree can be brought to balance by a number of rotations. Rotations are mainly of two types:
this x
/ \ left-rotate / \
(T1) x ----------> this (T3)
/ \ / \
(T2) (T3) (T1) (T2)
values(T1) < this < values(T2) < x < values(T3)
this x
/ \ right-rotate / \
x (T3) -----------> (T1) this
/ \ / \
(T1) (T2) (T2) (T3)
values(T1) < x < values(T2) < this < values(T3)
In the above illustrations, T1, T2, T3 are subtrees.
In both cases, the new BST formed can be looked at as a rotation about x
.
The logic behind the successful working of these trees is that each node has a value associated with, called balance factor
. It is given by balance factor = height(left sub-tree) - height(right sub-tree)
. This method tries to make the balance factor of all nodes in the tree to be in the range {-1,0,1}. Height of a null
subtree is treated as 0. Whenever a node is inserted or deleted, it will check if the new balance factor of all nodes in all the subtrees in which the node in question belongs to, still come in the range. If not, it will do a rotation to make the balance factor come back in the range, thus making the tree balanced.
main.cpp
: Contains the driver programAVLTree.cpp
: Contains definition of all functions requiredAVLTree.h
: Contains declaration of classes and functions
Function Name | Arguments | Description | Returned variable |
---|---|---|---|
rightRotate() |
nil |
performs right rotation of associated object of type AVLTreeNode . |
pointer to root of rotated node/subtree |
leftRotate() |
nil |
performs left rotation of associated object of type AVLTreeNode . |
pointer to root of rotated node/subtree |
insertNode() |
|
inserts a new node into the given tree. | pointer to root of modified BST |
deleteNode() |
|
deletes the given value from the given tree, if present | pointer to root of modified BST |
getMinNode() |
pointer to root of BST | finds the node with minimum value in the given BST | pointer to node with minimum value |
modifyNode() |
|
modifies node with value old value to hold value new value | pointer to root of modified BST |
searchNode() |
|
searches for node with given value in the given tree | bool value true if tree contains node with given value. Else false . |
getHeight() |
pointer to node of BST | finds the height of given node in the BST | height of the node |
balanceFactor |
pointer to node of BST | finds the balance factor of the given node | balance factor of the node |
printGraphviz |
|
prints the BST in graphviz format | nil |
- Download / clone this repo with
git clone https://github.com/aklsh/self-balancing-tree
on terminal. This will create a folder namedself-balancing-tree
cd
into the folder- To run in interactive mode, run with
make -s
. - To test for large input sizes, I have provided two
.txt
files in the folderTest Inputs
.sortInput.txt
contains the input for the program in sorted order (numbers used: 1-500).randomInput.txt
contains the input for the program with random numbers.- To run program with either of these inputs, run with
make -s < ./Test\ Inputs/<input file> > output.txt
. - Executing the above command will create a file named
output.txt
in the current directory. - Open it and you will see the BST printed in dot format.
- If you want to visualize it, use an online Graphviz site like:
http://www.webgraphviz.com/
https://dreampuf.github.io/GraphvizOnline/
1: https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree