# What is an AVL tree?

- An AVL tree is a self-balancing data structure that adheres to the same guidelines as a Binary Search Tree. However, the AVL tree has additional properties:
- Height of left and right subtree can differ no greater than 1

- BalanceFactor(X) = Height(RightSubtree(x) - Height(LeftSubtree(X))

# Rotations:

Let x be our offending node.

If the tree is left-heavy If the left child of x is right-heavy perform a LR @ x’s left child. perform a RR @ x else perform a RR @ x

If the tree is right-heavy If the right child of x is left-heavy perform a RR @ x’s right child perform a LR @ x else perform a LR @ x

## Code Implementation:

# Insertion:

- Insert BST Style.
- Fix bad balance-factors as we go.

# Deletion:

- Delete node BST Style.
- Perform rotations to fix bad balance-factors.

# Searching:

- Search for the value BST Style.

# Runtime considerations

Insertion: O(log n)