Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Balanced binary trees are also called AVL trees. It has the following properties: is an empty tree or the absolute value of the height difference between the left and right subtrees is not more than 1, and the left and right subtrees are a balanced binary tree. A balanced binary tree is generally an ordered tree with all the properties of a binary tree, and its traversal operation is the same as that of a binary tree.

Time complexity of binary trees

The left-hand graph above is also a binary tree, but if you want to search in this binary tree it’s also O(n)O(n)O(n) average time


A S L = n + 1 2 ASL = \frac{n+1}{2}

If the right hand side is arranged like this then the time complexity changes from O(n)O(n)O(n) to O(h)O(h)O(h) O(h)O(h)O(h) O(h) where the height of the binary tree is h=log⁡(n+1)h = \log(n+1)h=log(n+1), so you have to balance the binary tree.

Calculate the height and balance factors

We know that in the definition of the balance tree design to calculate the height of the node, so let’s first introduce how to calculate the height of the node, okay

  • For a null node, H(ϕ)=−1H(\phi) = -1h (ϕ)=−1, its height is -1
  • For a node tree whose height is 0, H(singlenode)= 0H(single\,node)=0H(Singlenode)=0
  • Except for the empty tree and the special case of only one node, the height of other nodes is calculated as follows

H ( n ) = max ⁡ ( H ( T L ) . H ( T R ) ) + 1 H(n) = \max(H(T_L),H(T_R)) +1

So the formula for calculating the node balance factor is to subtract the absolute value of the left subtree height from the right subtree height


B ( n ) = ∣ H ( T L ) – H ( T R ) ∣ B(n) = |H(T_L) – H(T_R)|

Above are two balanced binary trees to compute the equilibrium factors of their nodes

Rotation transformation

There are four ways to adjust and repair the imbalance problem by rotation, namely, LL LR RR RL. For example, if new nodes are added to the left subtree of the left node, the original balanced tree may become unbalanced. The fix is the Right Rotation, as shown below

After 2 is raised to 3, the method is to turn right, and then adjust each subtree to its location accordingly. If RR adds nodes under the right subtree of the right node, the left Rotion can be used to promote the right child node.

This graph is relatively complicated, that is, adding nodes under the Right subtree of the Left child node may make the balance tree unbalanced. It is necessary to adjust the Left ratation of the 2 nodes to obtain the LL situation, and then rotate the Right ratation to obtain a balance tree.