Number of balance operations in an AVL Tree when a sequence of decreasing numbers is inserted

How many balance operations will there be when inserting n numbers (decreasing from n down to 1) into an empty AVL tree?

Example:

AVL tree        number of rotations
--------------- -------------------
8                     0

  8
┌─┘                   0
7                    

    8       7              
  ┌─┘     ┌─┴─┐       1
  7   →   6   8
┌─┘
6

...etc

I know the answer is ~(n-logn), but how to prove this with induction?

Here are some invariants (to be proved) when we have an AVL tree with 𝑛 nodes (𝑛 > 0) that was constructed by adding a sequence of decreasing values:

1. All right subtrees (of any parent node) are perfect. This means all nodes in the tree have a balance factor that is 0, except maybe one or more nodes that are on the path from the root to the leftmost leaf: they may have a balance factor of 0 or −1 (When −1, this indicates their left subtree is one unit higher than their right subtree).

2. The height of the tree is 𝐻_𝑛 = ⌊log₂𝑛⌋. By consequence, if 𝑛 is one less than a power of 2, the tree is a perfect tree and thus all balance factors are zero.

3. The number of rotations is 𝑅_𝑛 = 𝑛−1−𝐻_𝑛

Proof by induction

Base case

These invariants are true when 𝑛 is 1: that tree is perfect, 𝐻_𝑛= 0, and the number of rotations is 𝑛−1−𝐻_𝑛 = 0.

Induction step

We now assume a tree with 𝑛−1 nodes that obeys the invariants, and we then add the 𝑛^th node (with smaller value) to that tree. We can distinguish between two cases:

• 𝑛 is a power of 2:

  The tree was perfect before insertion (invariant 2) and thus all balance factors were zero: the addition will give all the ancestors of the new node a balance factor of −1, and will increase the height 𝐻_𝑛 = 𝐻_𝑛−1 + 1. No rotations will occur. We know that the number of rotations was 𝑅_𝑛−1 = 𝑛−2−𝐻_𝑛−1 and so it follows that 𝑅_𝑛 = 𝑛−1−𝐻_𝑛. The invariants hold.

• 𝑛 is not a power of 2:

  The tree was not perfect and at least one node on the path to the leftmost leaf had a balance factor of −1. After the AVL insertion algorithm has inserted the node, the tree's height temporarily increases, and the algorithm will backtrack upwards the path to decrease the balance factors of the nodes it meets. They all become −1 until a node 𝑋 is encountered that already had a balance factor of −1 and now has it changed to −2. Let's call 𝑋's left child 𝑌, which already had its balance factor updated from 0 to −1. Now 𝑋 needs a simple rotation to the right, whereby 𝑌 takes its place in the tree, and 𝑋 becomes its right child. This rotation will decrease the tree's height again to what it was before and give 𝑌 a balance factor of 0. We know that 𝑋 has a perfect right subtree (invariant 1), and the rotation will give 𝑋 a left child (if any) that is also perfect (as the child used to be a right child of 𝑌 − invariant 1). The balance factor of 𝑋 will become 0, and so it now roots a perfect subtree whose bottom level is the bottom level of the whole tree, so that invariant 1 remains true:

  

  (N is the inserted node)

  The AVL insertion algorithm stops there as there are no more balance factors to update, nor rotations to be performed. As the height remained the same, invariant 2 holds, and as 𝑛 obviously increased with 1, that increase covers for the new rotation and we maintain the third invariant: 𝑅_𝑛 = 𝑛−1−𝐻_𝑛. All the invariants hold.

In conclusion: we have a proof by induction of the invariants. The third invariant is the one of interest:

      𝑅_𝑛 = 𝑛−1−⌊log₂𝑛⌋.