AVL trees(named after inventors Adelson-Velsky and Landis), also known as height-balanced trees are a widely-used data structure when it comes to efficient read, write and search operations.
Similar to a BST(binary search tree), an AVL tree also has basic operations:
- add()
- remove()
- search()
But what makes an AVL tree efficient and fast
- always height balanced
- balance factor on any node is 0 or 1
- always achieves minimum height
- by rotations
At the time of insertions and deletions:
- it finds the first node where one side becomes more heavy than the other
- fix this by RR, RL, LR, LL rotations
- the whole tree is balanced
I have compared my implementation with the std::set(implemented with red-black trees) for different workloads. Here are the results:
- defining an instance of avl tree:
tree* my_tree = new_tree();
- adding an element:
add_t(my_tree, 77);
- removing an element:
remove_t(my_tree, 67);
- searching for an element:
find_t(my_tree, 57);
- deleting the instance of tree:
delete_tree(my_tree);
Anupam Kumar |