Balanced binary tree (AVL)

Catalog

The definition of balanced binary tree

Balanced binary tree insertion

LL Balance rotation ( Right single rotation )

RR Balance rotation ( Left single rotation )

LR Balance rotation ( First left then right double rotation )

RL Balance rotation ( First right then left double rotation )

Construction of balanced binary tree

Search of balanced binary tree

---

The definition of balanced binary tree

Q： What is a binary sort tree

A： Binary sort tree or an empty tree , Or a binary tree with the following properties

• 1） If its left subtree is not empty , be The left subtree Values of all nodes on All less than The value of its root
• 2） If its right subtree is not empty , be Right subtree Values of all nodes on All are greater than The value of its root
• 3） Left 、 The right subtree is also a binary sort tree

  ---

Q： What is a balanced binary tree

A： It could be an empty tree , Or a binary sort tree with the following properties ： The absolute value of the depth difference between the left subtree and the right subtree does not exceed 1, And its left and right subtrees are a balanced binary tree .

The height difference between the left subtree and the right subtree of a node is defined as the balance factor of the node , Then the balance factor of the balanced binary tree node can only be -1,0,1.

Balanced binary tree insertion

Whenever you insert... In a binary sort tree ( Or delete ) When a node , First, check whether the nodes on the insertion path are unbalanced due to this operation . If it causes an imbalance , Then find the absolute value of the balance factor on the path closest to the insertion node is greater than 1 The node of A, Then to A Root subtree , On the premise of maintaining the characteristics of sorting tree , Adjust the position relationship of each node , Bring it back to balance .

The first half of the insertion process of balanced binary tree is the same as that of binary sort tree , But after the new node is inserted , If a node on the search path is no longer balanced , Then you need to make corresponding adjustments . The law of adjustment can be summarized as follows 4 In this case ：

---

LL Balance rotation ( Right single rotation )

---

Because at the node A The left child (L) The left subtree (L) A new node is inserted on ,A The equilibrium factor of is 1 to 2 , Lead to A The root of the subtree is out of balance , A right rotation operation is required , take A The left child B Rotate right up instead of A Become the root node , take A The node rotates down to the right to become B The root node of the right subtree of , and B The original right subtree of is used as A The left subtree of the node .

---

RR Balance rotation ( Left single rotation )

---

Because at the node A The right child (R) The right subtree (R) A new node is inserted on ,A The equilibrium factor of is −1 Be reduced to −2, Lead to A The root of the subtree is out of balance , A rotation to the left is required . take A The right child B Rotate left and up instead of A Become the root node , take A The node rotates to the left and down to become B The root node of the left subtree of , and B The original left subtree of is used as A Right subtree of node .

---

LR Balance rotation ( First left then right double rotation )

---

stay A The left child (L) The right subtree (R) Insert new node on ,A The equilibrium factor of is 1 to 2, Lead to A The root of the subtree is out of balance , Two rotations are required , Rotate left first, then right . First the A The left child of the node B The root node of the right subtree of C Rotate upward to the left to lift to B The location of the node , Then put the C Rotate the node to the right and up to A The location of the node .

---

RL Balance rotation ( First right then left double rotation )

---

Because in A The right child (R) The left subtree (L) Insert new node on ,A The equilibrium factor of is −1 Be reduced to −2, Lead to A The root of the subtree is out of balance , Two rotations are required , First right then left . First the A The right child of the node B The root node of the left subtree of C Rotate upward to the right to lift to B The location of the node , Then put the C Rotate the node to the left and up to A The location of the node .

Construction of balanced binary tree

Assume that the keyword sequence is {6,1,2,5,4,3}, The process of generating binary sort tree through this sequence is as follows ：

First step ： Create an empty tree

The second step ： Insert node 6

The third step ： Insert node 1

Step four ： Insert node 2

Step five ：LR rotate

Step six ： Insert node 5

Step seven ： Insert node 4

Step eight ：LL rotate

Step nine ： Insert node 3

Step 10 ：RL rotate

Search of balanced binary tree

The process of searching on a balanced binary tree is the same as that of a binary sort tree . therefore , During the search , The number of keywords compared with the given value does not exceed the depth of the tree . Suppose nh, The depth is h The minimum number of nodes in the balanced tree . obviously ,nh Yes n0=0,n1=1,n2=2, And there are nh=nh−1+nh−2+1. Can prove that , contain n The maximum depth of a balanced binary tree of nodes is O(log2⁡n), Therefore, the average search length of balanced binary tree is O(log2⁡n).