Savoundg: 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..."

2018-06-03T18:55:44Z

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..."

New page

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 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 ==
{| class="wikitable"
!
|-
|https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html
|-
|https://en.wikipedia.org/wiki/AVL_tree
|}

AVL Tree - Revision history

Savoundg: 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..."