Learning notes of balanced binary tree -- one two pandas

Knowledge record of balanced binary tree .
1. Balance factor . The balance factor of a binary tree is the height difference between the left and right subtrees .HL Is the height of the left binary tree ,HR Is the height of the right binary tree , The equilibrium factor is HL-HR, Note that the balance factor does not take an absolute value .
2. Balanced binary trees . Balanced binary tree means that the absolute value of the height difference between the left and right subtrees of any node in a tree does not exceed 1 The tree of , That is, the absolute value of the balance factor does not exceed one .

Four equilibrium transformations ：
When a new node is inserted into a balanced binary tree, it becomes unbalanced , The newly inserted node is Destroy node A, It breaks the balance of a node , Then the destroyed node is called Damaged nodes B . See what the rotation is from Damaged nodes B set out , towards Destroy node A View the path .
The purpose of the transformation is to restore balance , This makes the search binary tree become balanced because of the imbalance after adding new nodes .

The unified strategy is to destroy nodes 、 Damaged nodes 、 The nodes between them calculate the balance factor （ Just count by yourself ）, Let the node with the balance factor in the middle be the parent node , The youngest as a left child , The eldest as a right child .

RR The transformation is as follows
When destroying nodes A And damaged nodes B The relationship between is ： Destroy node A For the damaged node B Right child's right child , That is to say RR Transformation （ Among them RR It is worth destroying the nodes A And damaged nodes B The relationship between ）.
Look down , As shown in the figure below, in BR Node out add a new node , Whether it's BR The left child is still the right child , It's all thought to be RR rotate , because B yes A The right child ,BR yes B The right child , stay BR Insert under , You can put BR It comes down to breaking nodes .
When the following node is unbalanced and its parent node is unbalanced , We adjust the bottom unbalance node , Because the subtree is balanced , The nodes above are balanced .

LL The transformation is as follows

LR The transformation is as follows
Newly inserted is Jan, cause May Node imbalance ,RL The adjustment is mainly to connect the damaged node to the damaged node and the connecting node between them , Balance refactoring , As shown in the red circle below . Then their children changed accordingly , The child nodes of the original structure from left to right are added to the left and right nodes of the new structure in order , This is to satisfy the condition that the left side is small and the right side is large .

RL The transformation is as follows
The newly added node is Feb, Destroyed Aug Equilibrium state of .

Only make self-study records .