AVL balanced binary tree and its four rotation modes

1.AVL Balanced binary trees ： The absolute value of the height difference between the left subtree and the right subtree of each node in the binary tree is less than or equal to 1.

2. Balance factor = The height of the left subtree - The height of the right subtree .AVL The balance factor of the tree is only -1,0,1.

3. Right rotation LL

Pre rotation feature :

1) node a For unbalanced nodes .

2） node b And nodes c To be on a high path , from a Start with the next two nodes .

3）y1,y2,y3 and y4 Represents a node a, node b, node c A child node or subtree of . It can be for null, Can be a leaf node , It can also be the number of nodes >1 A binary tree of .

4） node b Is the node a Of Left children . node c Is the node b Of Left children .

 

Features after rotation ：

1） node b Become a root node

2） The original root node a Become a node b The right child

3）y3 Become a node a The left child .【 If y3 Not empty , Because before y3 Is the node b The right child , Now the node a Become a node b The right child . because b<y3 Value of root node <a, node a Become a node b Right behind the child , node a No left child . So when y3 Become a node a Behind my left child , Also satisfied b<y3 Value of root node <a.】

4）y1,y2,y4 The relationship with the parent node does not change .

 

4. Left rotation RR

Pre rotation feature :

1） node a For unbalanced nodes .

2） node b And nodes c To be on a high path , from a Start with the next two nodes .

3）y1,y2,y3 and y4 Represents a node a, node b, node c A child node or subtree of . It can be for null, Can be a leaf node , It can also be the number of nodes >1 A binary tree of .

4） node b Is the node a Of Right children . node c Is the node b Of Right children .

Features after rotation ：

1） node b Become a root node

2） The original root node a Become a node b The left child

3）y2 Become a node a The right child .【 If y2 Not empty , Because before y2 Is the node b The left child , Now the node a Become a node b The left child . because a<y2 Value of root node <b, node a Become a node b Behind my left child , node a No right child . So when y2 Become a node a Right behind the child , Also satisfied a<y2 Value of root node <b.】

4）y1,y3,y4 The relationship with the parent node does not change .

5. First left, then right LR

Pre rotation feature :

1) node a For unbalanced nodes .

2） node b And nodes c To be on a high path , from a Start with the next two nodes .

3）y1,y2,y3 and y4 Represents a node a, node b, node c A child node or subtree of . It can be for null, Can be a leaf node , It can also be the number of nodes >1 A binary tree of .

4） node b Is the node a Of Left children . node c Is the node b Of Right children .

 

step1： Left hand operation

step2： Right hand operation

take step1 The results of right-handed operation

6. Right and then left RL

Pre rotation feature :

1) node a For unbalanced nodes .

2） node b And nodes c To be on a high path , from a Start with the next two nodes .

3）y1,y2,y3 and y4 Represents a node a, node b, node c A child node or subtree of . It can be for null, Can be a leaf node , It can also be the number of nodes >1 A binary tree of .

4） node b Is the node a Of Right children . node c Is the node b Of Left children .

step1： Right hand operation

step2： Left hand operation