AVL Tree

From Wiki :-)
Revision as of 18:55, 3 June 2018 by Savoundg (talk | contribs) (Created page with "An AVL Tree is self-balancing height-balanced Binary Search Tree. AVL stands for the inventors of this tree: '''A'''delson-'''V'''elskii and '''L'''andis. Search, insertion a...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

An AVL Tree is self-balancing height-balanced Binary Search Tree. AVL stands for the inventors of this tree: Adelson-Velskii and Landis. Search, insertion and deletion are in O(log n) time in both average and worst cases. AVL Tree is better than Red-Black Tree for search operation because it is more strictly balanced.

AVL Tree approximately balances itself. Each node contains the attribute balance factor that indicates if the the sub-tree (whose node is considered as the root) is:

  • left-heavy: if the height of the left sub-tree is greater than the height of the right sub-tree.
  • balanced: if the height of the left and right sub-trees are the same.
  • right-heavy: if the height of the right sub-tree is greater than the height of the left sub-tree.

If an insertion unbalance the tree, a rotation should be done to correct the balance.

Property: Every given pair of sub-trees heights differ by at most 1.

Resources

https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html
https://en.wikipedia.org/wiki/AVL_tree
Retrieved from "https://wiki.georges.savound.com/index.php?title=AVL_Tree&oldid=708"