Python AVL Trees

Tree is a type of Binary Search Tree named after two Soviet inventors Georgy A delson- V elsky and Evgenii L andis who invented the AVL Tree in 1962. AVL trees are self-balancing, which means that the tree height is kept to a minimum so that a very fast runtime is guaranteed for searching, inserting and deleting nodes, with time complexity \(O( \log n)\).

Binary Search Tree and an AVL Tree is that AVL Trees do rotation operations in addition, to keep the tree balance. A Binary Search Tree is in balance when the difference in height between left and right subtrees is less than 2. By keeping balance, the AVL Tree ensures a minimum tree height, which means that search, insert, and delete operations can be done really fast. B G E K F P I M

(unbalanced)

G E K B F I P M

The two trees above are both Binary Search Trees, they have the same nodes, and the same in-order traversal (alphabetical), but the height is very different because the AVL Tree has balanced itself. Step through the building of an AVL Tree in the animation below to see how the balance factors are updated, and how rotation operations are done when required to restore the balance.

C

F

G

D

B

A

Continue reading to learn more about how the balance factor is calculated, how rotation operations are done, and how AVL Trees can be implemented.

To restore balance in an AVL Tree, left or right rotations are done, or a combination of left and right rotations. The previous animation shows one specific left rotation, and one specific right rotation. But in general, left and right rotations are done like in the animation below. X Y

Notice how the subtree changes its parent. Subtrees change parent in this way during rotation to maintain the correct in-order traversal, and to maintain the BST property that the left child is less than the right child, for all nodes in the tree. Also keep in mind that it is not always the root node that become unbalanced and need rotation.

A node's balance factor is the difference in subtree heights. The subtree heights are stored at each node for all nodes in an AVL Tree, and the balance factor is calculated based on its subtree heights to check if the tree has become out of balance. The height of a subtree is the number of edges between the root node of the subtree and the leaf node farthest down in that subtree.

(\(BF\)) for a node (\(X\)) is the difference in height between its right and left subtrees.

0: The node is in balance. more than 0: The node is "right heavy". less than 0: The node is "left heavy". If the balance factor is less than -1, or more than 1, for one or more nodes in the tree, the tree is considered not in balance, and a rotation operation is needed to restore balance. Let's take a closer look at the different rotation operations that an AVL Tree can do to regain balance.

There are four different ways an AVL Tree can be out of balance, and each of these cases require a different rotation operation.

A single right rotation.

A single left rotation.

The unbalanced node is left heavy, and its left child node is right heavy. First do a left rotation on the left child node, then do a right rotation on the unbalanced node.

The unbalanced node is right heavy, and its right child node is left heavy. First do a right rotation on the right child node, then do a left rotation on the unbalanced node. See animations and explanations of these cases below.

The node where the unbalance is discovered is left heavy, and the node's left child node is also left heavy. When this LL case happens, a single right rotation on the unbalanced node is enough to restore balance. Step through the animation below to see the LL case, and how the balance is restored by a single right rotation. -1 Q

P

D

L

C

B

K

A

As you step through the animation above, two LL cases happen: When D is added, the balance factor of Q becomes -2, which means the tree is unbalanced. This is an LL case because both the unbalance node Q and its left child node P are left heavy (negative balance factors). A single right rotation at node Q restores the tree balance. After nodes L, C, and B are added, P's balance factor is -2, which means the tree is out of balance. This is also an LL case because both the unbalanced node P and its left child node D are left heavy. A single right rotation restores the balance.

The second time the LL case happens in the animation above, a right rotation is done, and L goes from being the right child of D to being the left child of P. Rotations are done like that to keep the correct in-order traversal ('B, C, D, L, P, Q' in the animation above). Another reason for changing parent when a rotation is done is to keep the BST property, that the left child is always lower than the node, and that the right child always higher.

A single left rotation at the unbalanced node is enough to restore balance in the RR case. A

B

D

C

E

F

The RR case happens two times in the animation above: When node D is inserted, A becomes unbalanced, and bot A and B are right heavy. A left rotation at node A restores the tree balance. After nodes E, C and F are inserted, node B becomes unbalanced. This is an RR case because both node B and its right child node D are right heavy. A left rotation restores the tree balance.

In this LR case, a left rotation is first done on the left child node, and then a right rotation is done on the original unbalanced node. Step through the animation below to see how the Left-Right case can happen, and how the rotation operations are done to restore balance. -1 Q

E

K

C

F

G

As you are building the AVL Tree in the animation above, the Left-Right case happens 2 times, and rotation operations are required and done to restore balance: When K is inserted, node Q gets unbalanced with a balance factor of -2, so it is left heavy, and its left child E is right heavy, so this is a Left-Right case. After nodes C, F, and G are inserted, node K becomes unbalanced and left heavy, with its left child node E right heavy, so it is a Left-Right case.

In this case we first do a right rotation on the unbalanced node's right child, and then we do a left rotation on the unbalanced node itself. Step through the animation below to see how the Right-Left case can occur, and how rotations are done to restore the balance. A

F

B

G

E

D

After inserting node B, we get a Right-Left case because node A becomes unbalanced and right heavy, and its right child is left heavy. To restore balance, a right rotation is first done on node F, and then a left rotation is done on node A. The next Right-Left case occurs after nodes G, E, and D are added. This is a Right-Left case because B is unbalanced and right heavy, and its right child F is left heavy. To restore balance, a right rotation is first done on node F, and then a left rotation is done on node B.

After inserting or deleting a node in an AVL tree, the tree may become unbalanced. To find out if the tree is unbalanced, we need to update the heights and recalculate the balance factors of all ancestor nodes. This process, known as retracing, is handled through recursion. As the recursive calls propagate back to the root after an insertion or deletion, each ancestor node's height is updated and the balance factor is recalculated. If any ancestor node is found to have a balance factor outside the range of -1 to 1, a rotation is performed at that node to restore the tree's balance. In the simulation below, after inserting node F, the nodes C, E and H are all unbalanced, but since retracing works through recursion, the unbalance at node H is discovered and fixed first, which in this case also fixes the unbalance in nodes E and C. -1 A

B

C

D

E

G

H

F