Problem of binary sequencing tree: Performance is related to the order of input data, it is best to fold the performance, the worst is the order lookup performance, so it is necessary to build this tree well research. Birth of the AVL (why not BBT, and called AVL, no solution)
definition
Balance factor BF: The depth of the left subtroduction is reduced.
The balance factor of all nodes of AVL is 1,0, and the binary sort number of -1 is called AVL.
Supplement definition:
Problem Node: After the addition of a new node, the first balancing factor no longer conforms to the NVL defined node.
Theory: If the subtree depth of the problem node is the same as the depth before the addition of the node, there will be no problem node above it, and this tree is already an AVL.
Causes of imbalance:
1) The original problem node's BF is 1, now add new nodes on its left sub-tree, make BF = 2
2) The original question node's BF is -1, now add new nodes on its right tree, make BF = -2
1) Discussion
It turns out that now (after adding the node, it has not been adjusted)
Problem Node B Problem Node B
Left tree a right tree C left tree a 1 right tree C
If the original A depth is H 1, the C depth is H, then the depth of B is h 2, and a must be subdivided (h> = 0)
Left tree a
Sub tree a1 seed tree A2
The settings of A1, A2 must have a H (because the depth of A is H 1, A itself, so the maximum depth of its sub-tree is h), the new node will join H
Sub trees, and after adding, its depth becomes h 1 (otherwise the bf is unchanged, the BF of the above node does not have problems)
The other is also H, and the other may be H, or H-1 (the maximum H, it is an avl), but if it is H-1, newly added
The node will make the other sub-tree becomes h 1, the first node that does not satisfy the AVL tree will be A, not a Parent B node.
a) Consider the newly added node in A1, this is the LL problem (left on the left).
Solve is easy: pull B into the right tree, A, A2, the left subtree of B
The new structure is as follows:
a
Sub tree aa1 seed b
Sub tree aa1 seed c
From A, the depth of the tree is H 2, which is the same.
b) Consider the newly added node in A2, this is the LR problem (the right side of the left).
The solution is more complicated, and it needs to be further analyzed:, the depth of the new A2 will be h 1, then A2 can be written in front of the A node in front:
Left tree A2
Sub tree aa1 seed tree aa2
AA1 and AA2 have a depth of H, another H-1 (analysis: the maximum depth is H, so there must be one, and it is caused by new joining nodes
The depth is increased, so the other is H-1)
Pull B into the right tree, A2, the two trees of A2 give a, and B
The new structure is as follows:
A2
Sub tree A tree B
Sub tree A1 AA1 AA2 sub-tree C came in from A2, and the depth of the tree was H 2, which was the same.
2) Similar analysis: When RR, put the B's right tree node, B becomes its left node
At RL, the position of B is removed on the left node of B's right node.
(Finish)
