AVL tree (balanced search tree)

AVL Introduction to tree

AVL The tree is made up of GM Adelson - Velsky and EM Landis On 1962 Invented in . In memory of its inventor , This tree structure is named AVL.

AVL A tree can be defined as a highly balanced binary search tree , Each node is associated with a balance factor , The balance factor is calculated by subtracting the height of its right subtree from the subtree of its left subtree .

If the balance factor of each node is -1 To 1 Between , The tree is said to be balanced , otherwise , Trees will be unbalanced and need to be balanced .

Equilibrium coefficient (k)= Height ( Left (k)) - Height ( Right (k))

If the balance factor of any node is 1, It means that the left subtree is one level higher than the right subtree . If the balance factor of any node is 0, It means that the left subtree and the right subtree contain the same height . If the balance factor of any node is -1, It means that the left subtree is one level lower than the right subtree .

AVL The tree is shown in the figure below . You can see , The balance factor associated with each node is between -1 and +1 Between . therefore , It is AVL An example of a tree .

complexity

Algorithm	On average	The worst
Space	O(n)	O(n)
lookup	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

AVL Tree insert elements

AVL The insertion in the tree is executed in the same way as in the binary search tree . The new node is added as a leaf node to AVL In the tree . however , It may lead to violations AVL Tree properties , So trees may need to be balanced .

You can balance the tree by applying rotation . Only when the balance factor of any node is disturbed when a new node is inserted , Otherwise, there is no need to rotate .

Depending on the type of insertion , Rotation is divided into four categories .

LL Right hand

The new node is inserted into the left subtree of the left subtree of the key node

LL Right hand rotation steps

• T Turn right to become L The right of the node
• L The right of the node Y Move to T On the left node of

The center of rotation is the root node T The left node （L）

Right rotation diagram

LR Left right rotation

The new node is inserted into the right subtree of the left subtree of the key node

LR Left right rotation Two rotation steps

1. Left rotation
   • L node Left rotation , Become R The left node
   • R Zuojie store (Y1) Left rotation , Become L The right of the node （ Turn left at the left child node ）
2. Right rotation
   • T node Right rotation , Become R The right of the node
   • R The right of the node (Y2) Right rotation , Become T The left node （ Right child node turn right ）

The center of rotation is the root node T The left node （R）

RR left-handed

The new node is inserted into the right subtree of the right subtree of the key node

RR Left hand step

• T Rotate left to become R The left node of
• R The left node Y Put it in T On the right node of

The center of rotation is the root node T The right of the node （R）.

Left rotation diagram

RL Right left

The new node is inserted into the left subtree of the right subtree of the key node

RL Right left Two rotation steps

1. Right rotation
   • R node Right rotation , Become L The right of the node
   • L Youjie store (Y2) Right rotation , Become R The left node （ Right child node turn right ）
2. Left rotation
   • T node Left rotation , Become L The left node
   • L The left node (Y1) Left rotation , Become T The right of the node （ Turn left at the left child node ）

The center of rotation is the root node T The right of the node （L）

ALV Tree delete element

Delete step

1. Find delete target
2. Determine the deletion target type , Use transformation ideas , Convert it to Delete leaves
3. The element target and AVL The tree link is broken , Adjust the balance , Finish deleting

Find delete target

AVL The tree is in the process of searching and deleting targets , You need to store all nodes on this path , For subsequent retrospective adjustment .

Node parent = null;
Node p = t,  q = null;
Stack<Node> st;
//p It's pointing AVL A pointer to the root node of the tree 
while (p) {
    		
	if (p.val == key)// The current node is to delete the target 
		break;
	parent = p;
	st.push(parent);// Store tracks 
	if (key > p.val)// Delete the target in the right tree 
		p = p.right;
	else// Delete the target in the left tree 
		p = p.left;
}
// Execute here ,p Or delete the target as expected , Either for null（ That there is no ）
// The next step should be to determine the type of deletion target , To convert 

Determine the deletion type , To convert

There are two subtrees or sub nodes in the deletion target

Find the driver or driver node , Replace the value with the precursor or follower node value , Finally, replace the predecessor or follower node

Use transformation ideas to Non leaf nodes are converted to deleted leaf nodes , The difficulty is greatly reduced .

The deletion target has at most one child node

There is only one child node , Very easy to handle , We just need to make the parent node of the deletion target link to delete the child node of the target , Then delete the target . As shown in the figure below ：

Of course, there is a special situation in this , That is, the whole tree has only two nodes , And the deletion target is the root node . In this case, we can directly make the child node become the root node . as follows ：

if (p==null)// Delete target does not exist 
	return false;
// Delete node 
if (p.left && p.right) {
    // Delete both sides of the target 
	parent = p;
	q = p.left;
	st.push(parent);
	while (q.right) {
    
		parent = q;
		st.push(parent);
		q = q.right;
	}
	p.val = q.val;
	p = q;// Convert to delete precursor 
}
//p Is to delete the target ,q Delete the child node of the target 
if (p.left)
	q = p.left;
else
	q = p.right;
if (parent==null)// The deletion target is the whole tree AVL The root node 
	t = q;
else {
    
	// To break off p node , Link to its children q
	if (parent.left == p) // Delete target is left child 
		parent.left = q;
	else// The deletion target is the right child 
		parent.right = q;
}
// The next step should be to adjust the balance 

Adjust the balance

As can be seen from the above, this article is defined in the code p To delete the target , Therefore, the following continues .

First , What we should understand is ：

1. if p It's the parent node parent My left son and daughter , Delete p, Cause the height of the left tree to decrease , therefore parent Of The balance factor requires +1;
2. if p It's the parent node parent My right child , Delete p, Cause the height of the right tree to decrease , therefore parent Of The balance factor requires -1;
3. because parent The parent node of will also be affected parent Influence , Therefore, it may also need to be adjusted , therefore It is possible that this adjustment needs to be traced back continuously .

parebt The equilibrium factor of was 0

In this case , Whether deleted parent The left subtree of is also a node on the right subtree , But it will not affect parent Is the height of the subtree of the parent node , So in this case It just needs to change parent The balance factor of :0------>1/-1

parent The original absolute value of the equilibrium factor of is 1, And the deleted node is located in the higher subtree

You can find , In this case , Deleting nodes on the branch tree will make parent The equilibrium factor of is changed to 0. However, due to deletion, the height of the branch tree is reduced 1, So we need to balance up , Follow the path stored in the stack to flash back .

therefore , Changing the balance factor of the parent node does not mean that the balance has been completed , And we need to trace and modify the ancestor nodes at the higher level .

parent The original absolute value of the equilibrium factor of is 1, And the deleted node is located in the lower subtree

under these circumstances , Delete nodes on shorter subtrees ,parent The balance factor of will become 2/-2,parent unbalance , Simply adjusting the balance factor cannot solve the problem , But needs Rotate to rebalance .

situation 1：
parent The equilibrium factor of 2,q The equilibrium factor of 0, Do it once Left spin The balancing work can be ended ; conversely ,parent The equilibrium factor of -2,q The equilibrium factor of 0, Do it once Right single spin The balancing work can be ended ;

situation 2：
parent The equilibrium factor of and q The equilibrium factor of The same symbol , You can use a Single rotation Rebalance . As shown in the figure below , Both are positive , One left rotation can balance the current branch tree structure . But due to rotation parent The height of the parent node of decreases 1, So we need to Continue to look up at the equilibrium state in the path .

situation 3：
parent The equilibrium factor of and q The equilibrium factor of Heterogram , You need to use Double rotation Rebalance . But due to rotation parent The height of the parent node of decreases 1, So we need to Continue to look up at the equilibrium state in the path .

Reference article

data structure —— The illustration AVL Trees ( Balanced binary trees )

Yibai tutorial - data structure -AVL Trees

AVL Delete tree