AVL Tree Summary

An AVL tree is a subtype of binary search tree. Named after it’s inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees.

A BST is a data structure composed of nodes. It has the following guarantees:

  1. Each tree has a root node (at the top).
  2. The root node has zero, one or two child nodes.
  3. Each child node has zero, one or two child nodes, and so on.
  4. Each node has up to two children.
  5. For each node, its left descendants are less than the current node, which is less than the right descendants.

•The height of Binary Search Tree can be as large as n-1 (when the BST is skewed).

•The time needed to perform insertion, deletion, searching or many other operations depend on the tree’s height, this means they can be O(n) in worst case.

•So our goal is to keep the height of a BST to be O (log n), the minimal height of a BST with n nodes

•Such trees are called Balanced Binary Search Tree (i.e. AVL Tree, Red Black Tree) because it will keep the minimal height of a BST .

•Height of a node:

The height of an empty subtree is 0. The height of a leaf is 1.

The height of an internal node is the maximum height of its children plus 1.

•Balance factor: The difference height of its LEFT subtree and its RIGHT subtree.

•The balance factor of all nodes in AVL tree should be at most 1. •

AVL Tree Example

AVL Tree Rotation

AVL Tree Rotation

AVL Tree Insertion

AVL Tree Insertion

AVL Tree Deletion

AVL Tree Deletion

Leave a Reply

Your email address will not be published. Required fields are marked *