Those data structures can not learn from Leetcode — AVL

Another Self-Balancing BST explained step by step

Continuing with advanced DSA topic: Skip list, B Tree Step by Step, Treap, Red-Black Tree

In this post, I will go over the process of building AVL tree.

If you walked through the earlier Red-Black Post, I promise you this one only takes you 5 mins to digest (it’s much simpler) 🙂

Let’s start.

Definition

the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. from wiki

Let’s start with the Insertion process.

Insert: 9

This is the first and only node. nothing to do.

Insert 10

2 nodes on the tree. root node left and right tree height difference is 1, it is still balanced.

Of course, the same as other auto-balance binary search trees, the insertion position is done by binary search.

Insert 11

Oops, the problem happens. the tree is not balanced anymore. right tree height=3 however left tree height=1. left rotation(center node=2) happens (will explain details below). for now, let’s call this as “Case #1”

Insert 12

Still balanced. continue.

Insert 19

“Case #1” happens again. so we just apply the same rotation fix (will explain later).

Insert 13

Now Tree is not balanced anymore. however, if you look carefully, it is still “Case#1”(Left rotation, center=12)

Insert 14

Rotation(left rotate, center node=13; right rotate, center node=14) needs to happen, and this seems to be a new case. let’s call it “Case#2” (left-right rotation)

Insert 5

still balanced. continue.

Insert 1

You can see the imbalanced point happened. which is a new case (Case#3). yes, here we apply right rotation(center node 2) to fix it. (since this is reverse of Case#1)