AVL tree - binary lookup tree with equilibrium condition

One 、 Premise theory

1. Relevant concepts

Balanced binary trees , Also known as AVL Trees . In fact, it is a binary search tree that follows the following two characteristics ：

• The depth difference between the left subtree and the right subtree in each subtree cannot exceed 1;
• Every subtree in a binary tree must be a balanced binary tree ;
  
  chart 1 Balanced binary trees

AVL Tree search 、 Insert 、 Delete operations are, on average and in the worst case O（logn）, This is because it always maintains the balance of binary tree . If the set we need to find itself has no order , While searching frequently, it also inserts and deletes frequently ,AVL Trees are a good choice .

2. Balance factor

Balance factor ： The value of subtracting the height of the left subtree from the height of the right subtree is called the balance factor of the node BF(Balance Factor), It represents the difference between the depth of the left subtree and the depth of the right subtree . The value of the balance factor of each node in the balanced binary tree can only be ：0、1 and -1.

3. Minimum unbalanced subtree

The closest... To the insertion node , And the absolute value of equilibrium factor is greater than 1 The node of is the subtree of the root .

Two 、 Steps of balance adjustment

1. Find the absolute value of the balance factor equal to 2 The node of

2. Find the smallest unbalanced subtree that loses balance after inserting a new node ( Closest to the insertion node , The absolute value of the balance factor is greater than 1 Node as root )

3. Balance adjustment

Imbalances	Adjustment method
LL type ( The left subtree of the left child is inserted into the node )	R( Unidirectional right rotation )
RR type ( The right subtree of the right child is inserted into the node )	L( Unidirectional left rotation )
LR type ( The right subtree of the left child is inserted into the node )	LR( Left right after the first )
RL type ( The left subtree of the right child is inserted into the node )	RL( First right then left )

3、 ... and 、 Deal with the four cases of imbalance

The nodes that must be rebalanced are called α, Since any node has at most two sons , Therefore, the occurrence of high imbalance requires α The height difference between the two subtrees of the point 2, Then this imbalance may appear below 4 In these cases ：

1. Yes α The left sub tree of the left son of (LL type )– Unidirectional right rotation

chart 2 LL type – Unidirectional right rotation

If due to node a The left subtree of is the root node, and the node is inserted into the left subtree of , Cause node a The equilibrium factor of is 1 to 2, Cause to a The subtree of the root node is out of balance , You only need to make one clockwise rotation to the right , With B The node is the middle fulcrum , High nodes A Turn right （ Clockwise rotation ）.

2. Yes α Right son of the right subtree for an insert (RR type )– Unidirectional left rotation

chart 3 RR type – Unidirectional left rotation

If due to node a The right subtree of is the root node, and the node is inserted on the right subtree , Cause node a The equilibrium factor of is -1 Turn into -2, with a The subtree of the root node needs to rotate counterclockwise to the left , With B The node is the middle fulcrum , High nodes A Turn left （ Counter clockwise rotation ）.

3. Yes α The left son of the right subtree for an insert (LR type )– Left right after the first

chart 4 LR type – Left right after the first

If due to node a The left subtree of is the root node, and the right subtree inserts the node , Cause node a The equilibrium factor consists of 1 to 2, Cause to a The subtree of the root node is out of balance , You need to rotate twice , For the first time C For the middle fulcrum will B left-handed , The second time with C For the middle fulcrum will A Right hand .

4. Yes α The right son of the left subtree for an insert (RL type )– First right then left

chart 5 RL type – First right then left

If due to node a The right subtree of is the root node, and the left subtree inserts the node , Cause node a The equilibrium factor consists of -1 Turn into -2, Cause to a The subtree of the root node is out of balance , You need to rotate twice （ Right and then left ） operation , For the first time C It is the middle fulcrum B Right hand , The second time with C It is the middle fulcrum A left-handed .

Four 、 Code implementation

The following code implements AVL The treatment of four equilibrium situations of trees , Other methods are the same as Binary search tree The same way .

template<typename Comparable>
class AvlTree {
    
	struct AvlNode {
    
		Comparable element;
		AvlNode* left;
		AvlNode* right;
		int height;

		AvlNode(const Comparable &ele,AvlNode*lt,AvlNode*rt,int h=0)
			:element{
    ele},left{
    lt},right{
    rt},height{
    h}{
    }
		AvlNode( Comparable&& ele, AvlNode* lt, AvlNode* rt, int h = 0)
			:element{
     std::move(ele) }, left{
     lt }, right{
     rt }, height{
     h }{
    }
	};

	// Return to node t Height , If it is nullptr Then return to -1
	int height(AvlNode* t)const {
    
		return t == nullptr ? -1 : t->height;
	}

	/** *  An internal method of inserting into a subtree  * x Is the item to insert  * t Is the root node of the subtree  *  Set the new root of the subtree  */
	void insert(const Comparable& x, AvlNode*& t) {
    
		if (t == nullptr)
			t = new AvlNode{
     x,nullptr,nullptr };
		else if (x < t->element)
			insert(x, t->left);
		else if (x > t->element)
			insert(x, t->right);
		balance(t);
	}
	
	static const int ALLOWED_IMBALANCE = 1;

	// hypothesis t It's balanced. , Or the difference from the balance is no more than 1
	void balance(AvlNode*& t) {
    
		if (t == nullptr)
			return;
		if (height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
			if (height(t->left->left) >= height(t->left->right))
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
		else if (height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
			if (height(t->right->right) >= height(t->right->left))
				rotateWithLeftChild(t);
			else 
				doubleWithLeftChild(t);
		t->height = max(height(t->left), height(t->right))+1;
	}

	/** *  Rotate the nodes of the binary tree with the left son  *  That's right AVL The tree is in the situation 1 A single rotation of  *  Update height , Then set the new root  */
	void rotateWithLeftChild(AvlNode*& k2) {
    
		AvlNode* k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->hegiht)+1;
		k2 = k1;
	}

	/** *  The node of the double rotation binary tree ： First, the left son and its right son  *  And then the nodes k3 With the new left son  *  That's right AVL Tree condition 3 One double rotation  *  Update height , Then set the new root  */
	void doubleWithLeftChild(AvlNode*& k3) {
    
		rotateWithRightChild(k3->left);
		rotateWithLeftChild(k3);
	}

	/** *  The internal method of implementing deletion from the subtree  * x Is the item to be deleted  * t Is the root node of the subtree  *  Set the new root of the subtree  */
	void remove(const Comparable& x, AvlNode*& t) {
    
		if (t == nullptr)
			return; // No items to delete were found , Do nothing 
		if (x < t->element)
			remove(x, t->left);
		else if (x > t->element)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) // There are two sons 
		{
    
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else {
    
			AvlNode* oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
		balance(t);
	}
};