Skip to content

AVL tree: height-balanced trees in C supporting add, remove, search, update features. A comparison of AVL trees with red-black trees is also done(std::set).

Notifications You must be signed in to change notification settings

anupam-io/avl_tree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

AVL Trees: perfectly balanced, as all things should be

Introduction

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

How is it perfect balanced

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

Comparision with RB trees

I have compared my implementation with the std::set(implemented with red-black trees) for different workloads. Here are the results:

comparison

How to use ?

  • 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);

Contributors

anupam
Anupam Kumar

About

AVL tree: height-balanced trees in C supporting add, remove, search, update features. A comparison of AVL trees with red-black trees is also done(std::set).

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published