Balanced binary trees （AVL Trees ）

A balanced binary tree is a sort of binary tree , The emergence of balanced binary tree is to solve the problem that the search efficiency of binary search tree decreases because of its high height .

Such as ： For arrays a[10]={3,2,1,4,5,6,7,10,9,8}. Construct binary search tree and balanced binary tree respectively .

If you want to find a node 8, The search process of the left binary search tree is ：3->4->5->6->7->10->9->8, To find out 8 Time . The search process of balanced binary tree is ：4->7->9->8, Just search 8 Time , It can be seen that when the height of binary search tree becomes very high, the search efficiency will decrease a lot .

1. Balanced binary trees （AVL Trees ） Definition

Balanced binary tree is a kind of binary search （ Sort ） Trees , The height difference of the left subtree or right subtree of each node is at most equal to 1.

Balanced binary tree is a highly balanced tree Binary search （ Sort ） Trees . We will The value of the height of the left subtree minus the height of the right subtree of a binary tree node is called the balance factor BF, Then the equilibrium factor of all nodes of the balanced binary tree can only be -1,0,1.

example ： Judge whether the following tree is a balanced binary tree

The closest... To the insertion node , And the absolute value of equilibrium factor is greater than 1 A subtree whose nodes are roots , It is called the minimum unbalanced subtree .

Such as ： Insert node 51 after , The nearest equilibrium factor to it exceeds 1 The node of is 58, So from 58 The subtree below is the minimum unbalanced subtree .

2. The realization principle of balanced binary tree

The basic idea of Constructing Binary balanced tree is in the process of constructing binary sort tree , Whenever a node is inserted , Check to see if the tree is out of balance due to insertion , if , Then find the least unbalanced subtree . On the premise of maintaining the characteristics of binary sort tree , Adjust the connection relationship between nodes in the minimum unbalanced subtree , Rotate accordingly , Make it a new balanced subtree .
Let's introduce The rotation of the tree Facilitate follow-up learning .

The rotation of the tree is to level a binary tree , Make the number of left and right nodes evenly distributed . Divided into left and right .

example ： Array a[10]={3,2,1,4,5,6,7,10,9,8} The construction process of balanced binary tree is as follows ：

• Insert node 3 And the nodes 2.

• Insert node 1 after , node 3 Of BF The value has become 2（>0）, therefore Rotate the minimum unbalanced subtree clockwise , Adjust to get the picture on the right .

• Insert node 4.

• Insert node 5 after , node 3 Of BF The value has become -2（<0）, therefore Rotate the minimum unbalanced subtree counterclockwise , Adjust to get the picture on the right .

• Insert node 6 after , node 2 Of BF The value has become -2(<0), therefore Rotate the minimum unbalanced subtree counterclockwise , Attention node 3 It was a node 4 The children of , however In order to meet the characteristics of balanced binary tree , So it becomes a node 2 The children of , Adjust to get the picture on the right .

• Insert node 7 after , node 5 Of BF The value has become -2(<0), therefore Rotate the minimum unbalanced subtree counterclockwise , Adjust to get the picture on the right .

• Insert node 10.

• Insert node 9 after , node 5 Of BF The value has become -2(<0), But at this moment No matter how the minimum unbalanced subtree is rotated, it does not accord with the characteristics of binary sort tree . This is because , node 7 Of BF The value is -2, node 10 The value of is 1, The symbols are not unified . Then we Just turn it into unity , First pair node 9 And the nodes 10 Clockwise rotation Get the middle picture below , Again Rotate the minimum unbalanced subtree counterclockwise , Adjust to get the picture on the right .

• Insert node 10 after , node 6 Of BF The value has become -2(<0), Similar to the above ,9 Nodal BF The value is 1, First pair node 9 Rotate the root node right , according to Binary sort tree criterion ,8 The node was 7 The subtree of , After rotation, it becomes a node 9 The subtree of , As shown in the figure below . then Rotate the minimum unbalanced subtree counterclockwise , Adjust to get the picture on the right .

The so-called balanced binary tree , It's a binary search （ Sort ) Ensure its balance during tree creation , Once an imbalance is found, deal with it immediately ：

• BF Greater than 1 Rotate clockwise for the minimum unbalanced subtree .
• BF Less than -1 Just rotate the minimum unbalanced subtree counterclockwise .
• Minimum unbalanced subtree BF Value and its subtree BF When the symbols are opposite , The symbol of rotation adjustment relative to the subtree is the same as that of the minimum unbalanced subtree , Then rotate the minimum unbalanced subtree .