Data Structures & Algorithms Notes Page

Reference GeeksForGeeks Topic Regarding AVL Trees for Extra Notes

Motivation

• Insert, Delete, and Search in a BST is O(h)
• But h (The Height) can be as high as n - 1

How To Balance The Tree

• The tree can’t violate the BST Property:
  • Assume a height of an empty tree is = -1

Example 1:

• The tree becomes unbalanced if the difference between the heights of the 2 sub-trees of a node is > 1