- Start at leaf node view
- Use information from recursive insertion
- Animation: http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html

Let us assume that the BST is defined with:

- left < node < right

The algorithm uses a balance factor at each node based on the height of that node. So we need to define these terms.

- Height:

- The height of a node is one more than the length of the
longest path from the node to a leaf of the subtree with the
node as the root.

- Thus, the height of a leaf is 1.

- The height of null children is 0.

- Balance Factor:

- The balance factor of a node in a binary tree is the absolute value of the height of the left child minus the height of the right child.
- AVL Balanced:

- A binary search tree is AVL balanced if the balance factor
at every node is no more than 1, meaning either 0 or 1.

You can generate this tree adding nodes in the level order, the first is the original tree, and the second adds the unbalanced node 87.

- 44 24 64 16 32 51 88 14 17 28 42 50 54 81 94 12 48 62 78 85 92 96 73 83 86 95
- 44 24 64 16 32 51 88 14 17 28 42 50 54 81 94 12 48 62 78 85 92 96 73 83 86 95 87

All the nodes in the tree above are balanced.

We will now add 87 to the tree, and from that node up, we recompute the heights and balance factors.

We begin with the node just inserted and go up the tree looking for a node that is not balanced:

- 87 - children are (0, 0), so balanced, go to parent
- 86 - children are (0, 1), so balanced, go to parent
- 85 - children are (1, 2), so balanced, go to parent
- 81 - children are (2, 3), so balanced, go to parent
- 88 - children are (4, 3), so balanced, go to parent
- 64 - children are (3, 5), so NOT balanced,

- so start AVL balancing algorithm at node 64,

- keeping track of child and grandchild nodes in path: (64,
88, 81), and

- we need to keep track of the other children of those nodes,
which we will call T0, T1, T2 and T3.

Here, we have labelled those nodes:

- A (64) - the node where the unbalance was detected
- B (88) - that node's child, which we tracked during the upward path from the inserted node (87)
- C (81) - the unbalanced node's grandchild, also tracked during the upward path from (87)
- T0, T1, T2 and T3 - the other children of nodes A, B and C

- T0 (51) - the other child of A
- T1 (78) - one child of C
- T2 (85) - the other child of C
- T3 (94) - the other child of B
- P (44) - the parent of the unbalanced node.

Algorithm:

- Order A, B and C. In this case:
- A --> C --> B (64 --> 81 --> 88)
- Order T0, T1, T2 and T3. In this case, the order is the same:
- T0 --> T1 --> T2 --> T3
- Reconnect the tree:
- A.parent.right = C, the middle of {A, B, C}
- C.left = A, smallest of {A, B, C}

- C.right = B, largest of {A, B, C}
- A.left = T0, smallest of {T0, T1, T2, T3}
- A.right = T1, next of {T0, T1, T2, T3}
- B.left = T2, next of {T0, T1, T2, T3}
- B.right = T3, largest of {T0, T1, T2, T3}

- From the T's, so we recompute A, B (the children of the middle node), then C (the middle node), and then continue computing heights of parents of C (middle node). Now we see that everything is balanced.