Balanced binary tree [AVL tree] - insert, delete

1、 Average search length （ Tree height ）:

 

2、 The equilibrium factor of the node = Left subtree height - The right tree is tall

The equilibrium factor of a balanced binary tree node can only be 0,1 or -1

 

2、 Insert

        2.1  The object of each adjustment is “ Minimum unbalanced subtree ”

 

        2.2  Adjust the minimum unbalanced subtree A

                ①LL【A Left child right up spin 】： stay A The left child's insertion in the left subtree leads to imbalance

                ②RR【A The right child rotates upward on the left 】： stay A Insertion into the right subtree of the right child leads to imbalance

 

 

                ③LR【A The left child's right child first turns left and then right 】：

                                 stay A The insertion in the right subtree of the left child leads to imbalance

 

                ④RL【A The left child of the right child rotates right and then left 】：

                                 stay A The insertion of the right child into the left subtree leads to imbalance

【 notes 】 Each rotation will cause the child to become a father , Father becomes a child

【 notes 】 Only a left child can turn right up

            Only the right child can rotate up to the left

 

 

 

3、 Delete