Introduction

A binary search tree keeps values ordered: every node's left subtree holds smaller values and its right subtree holds larger ones. That ordering makes search fast, but only if the tree stays roughly balanced. Insert values in sorted order into a plain binary search tree and it degrades into a straight line, turning every search into a slow, linear scan.

An AVL Tree fixes this by keeping itself balanced automatically. After every insert or delete, it checks whether any node has become lopsided and, if so, performs a small local fix called a rotation to restore balance. No matter how you build it, an AVL Tree never degrades into a line.

In this course you will build an AVL Tree from scratch in your preferred language: nodes with a tracked height, balance checks, the four rotation cases, and a self-balancing insert and delete. Then you will use your finished class to solve a set of practice challenges.