Understanding and implementation of AVL tree

AVL Trees , Also called highly balanced binary search tree
The left and right subtrees are AVL Trees
Height difference between left and right subtrees （ It's called equilibrium factor ） The absolute value of is not more than 1（-1/0/1）

Balance factor = Height of right subtree - Height of left subtree
AVL Trees do not necessarily need balance factors
Using a balance factor is one way to control implementation

Triple chain storage , There is a pair of pair And balance factor

Insert
There is one parent, There is one cur
What is inserted is the Trident chain ,parent Also refer to

How to know the balance is not balanced
Newly inserted The balance factor must be 0
Insert to the right of the parent node , The balance factor of the parent node +1; Insert on the left , Parent node balance factor -1
cur Is a new node , It only affects cur The equilibrium factor of the node

Control balance
1. Update equilibrium factor – Add the ancestor path from the node to the root node
①cur ==parent->left , parent->left–
②cur ==parent->right,parent->right++
③ After the update ,parent->bf == 0, End of update —— Description before update parent -> bf yes 1 perhaps -1, Now become 0, The description is filled in the short side ,parent The height of the subtree remains unchanged
④ After the update ,parent->bf == 1 or -1, Continue online processing —— Description before update parent->bf yes 0, Now become 1 or -1, One side of the subtree became taller ,parent The height of the subtree
Changed , Will continue to affect the above subtree
The upward process is the power of the Trident chain
⑤ After the update ,parent->bf == 2 or -2, parents The subtree is already unbalanced , Need to rotate

The worst case scenario , All the way to the root
Add notes when writing , Easy to check later
It is not directly asserted in the above five cases , Note that there was a problem before inserting

2. Abnormal balance factor , Spin processing

Simple feeling
Insert 123 213 321
The structure of trees is different

Right single spin
Abstract picture , Represents many situations
Drawing diagram The corresponding is Concrete figure
If a become h+1, May trigger 60 Of bf become -2, Trigger rotation
Why is it called right single spin ？ Because the left side of the tree is high , Need to rotate to the right , Balance left and right
Do two things ：
① Keep the search tree rules
② Control balance
For abstract graphs ,b become 60 Left side ,60 become 30 To the right of

The meaning of rotation ：1 . The tree is balanced 2 . The overall height has dropped 1
Conditions ：cur Of bf yes -1 , parent Of bf yes -2 , Rotate
Not simply will cur To the right of （subLR） Give it to parent The left side of the is so simple
Because it doesn't just update the balance factor , The Trident chain also needs to be updated
b It could be empty , To avoid the problem of null pointers
Finally, if parent It's not a root node , You need to put parent Link with the node above
Always maintain our Trident chain

In descending order, the insertion will be right single rotation , You can debug and view

Left spin
It's high on the right , Make a left spin
It is similar to right single spin

Double left and right
30 The pivot point is the right height ,90 The pivot point is high on the left
If you use single rotation , There are still mistakes in the results , Originally, the left side was high , Will become high on the right
Double left and right ->30 Left simple rotation of the node of 【 It's high on the right 】,90 Right simple rotation of the node of 【 Left high 】（ After left single rotation , Become completely left high , And then turn it to the right , Balance ）
step ：
1 .30 Is the pivot point , Make a left spin
2 .90 Is the pivot point , Make a right spin

AVL Three rules of tree
1. Insert according to the rules of the search tree
2. Update equilibrium factor
3. There is an imbalance , Spin processing

There are four kinds of rotation
1. Left high , Press to the right , It's called right monocyclone
2. It's high on the right , Press to the left , It's called left monocyclone
3. It cannot be balanced by single rotation , With double spin

Judge avl Is a tree a balanced tree ？
It is wrong to check the balance factor , There may be problems （ In case the balance factor is updated incorrectly ）
Judging by height is the best , Recursive check , Every sub tree should be checked
Check whether the difference between the left and right trees is less than 2 that will do
After that, the shape of the tree is correct , The single equilibrium factor is not necessarily correct （ It may cause rotation when it should not be ）
So check the balance factor

Debugging is a means , There are many logs

Double selection cannot be simply left-handed + Right hand
There are many changes in the balance factor during the period , It can't be solved by reusing the previous code directly , It needs to be dealt with again

Right left double rotation （ chart ）
Can be seen as 60 The nodes of are distributed to both sides

Double left and right （ chart ）

AVL It is not widely used in practice , Mainly because of the red and black trees

AVL Tree implementation code ：
AVL.h

#pragma once
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <functional>
#include <assert.h>

using namespace std;

template<class K,class V>
struct AVLNode {
    
	// Store trigeminal chains and balance factors , There is also a pair of key value pairs 
	struct AVLNode<K, V>* _parent;
	struct AVLNode<K, V>* _left;
	struct AVLNode<K, V>* _right;

	int _bf;
	pair<K, V> _kv;
	AVLNode(const pair<K,V>& kv)
		:_parent(nullptr),
		_left(nullptr),
		_right(nullptr),
		_bf(0),
		_kv(kv)
	{
    }
};

template<class K,class V>
class AVLTree {
    
	typedef AVLNode<K, V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{
    }

	// Insert 
	bool Insert(const pair<K, V>& kv)
	{
    
		if (_root == nullptr)
		{
    
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
    
			if (cur->_kv.first > kv.first)
			{
    
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
    
				parent = cur;
				cur = cur->_right;
			}
			else
			{
    
				// If the value size is the same, it will not be inserted directly 
				return false;
			}
		}

		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
    
			cur->_parent = parent;
			parent->_right = cur;
		}
		else
		{
    
			cur->_parent = parent;
			parent->_left = cur;
		}

		// Start adjusting the balance factor 

		while (parent)
		{
    
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			if (parent->_bf == 0)
			{
    
				return true;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
    
				// If the equilibrium factor is 1 or -1 Words , Continue online updates 
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
    
				// If the equilibrium factor is 2 Words , It's about to rotate 
				// The specific rotation depends on the shape of the tree 

				if (cur->_bf == 1 && parent->_bf == 2)// Right tree （ It's high on the right ） The situation of , To carry on the left-hand 
				{
    
					RotateL(parent);
				}
				else if (cur->_bf == -1 && parent->_bf == -2)
				{
    
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
    
					RotateLR(parent);
				}
				else if(parent->_bf == 2 && cur->_bf == -1)
				{
    
					RotateRL(parent);
				}
				else
				{
    
					assert(false);// The impossible condition assertion reports an error ,
				}

				break;
			}
		}

		return true;
	}

	// Right hand 
	void RotateR(Node* parent)
	{
    
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if(subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent)
		{
    
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
    
			if (parent == parentParent->_left)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}

		subL->_bf = parent->_bf = 0;
	}

	// left-handed 
	void RotateL(Node* parent)
	{
    
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		// Solve the problem of non null pointers 
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (_root == parent)
		{
    
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
    
			if (parent == parentParent->_left)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;

			subR->_parent = parentParent;
		}

		subR->_bf = 0;
		parent->_bf = 0;
	}

	// Double left and right 
	void RotateLR(Node* parent)
	{
    
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
    
			parent->_bf = 0;
			subL->_bf = -1;
			subLR = 0;
		}
		else if (bf == -1)
		{
    
			parent->_bf = -1;
			subL->_bf = 0;
			subLR = 0;
		}
		else if (bf == 0)
		{
    
			parent->_bf = 0;
			subL->_bf = 0;
			subLR = 0;
		}
		else
		{
    
			assert(false);
		}
	}
	                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
	// Right left double rotation 
	void RotateRL(Node* parent)
	{
    
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 1)
		{
    
			subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
    
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 0)
		{
    
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
    
			assert(false);
		}
	}

	void InOrder()
	{
    
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
    
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	bool IsBalance()
	{
    
		return _IsBalance(_root);
	}

	int Height(Node* root)
	{
    
		if (root == nullptr)
			return 0;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		return leftHeight + 1 ?rightHeight + 1 : leftHeight > rightHeight;
	}

	bool _IsBalance(Node* root)
	{
    
		if (root == nullptr)
			return true;
		
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
    
			cout << root->_kv.first << " The equilibrium factor is " << root->_bf << endl;
			cout << root->_kv.first << " The balance factor of should be " << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(rightHeight - leftHeight)< 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}


private:
	Node* _root;
};

void TestAVLTree()
{
    
	AVLTree<int, int> t;
	//int a[] = { 5,4,3,2,1,0 };
	int a[] = {
     16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
    
		t.Insert(make_pair(e, e));
		cout << "Insert" << e << ":" << t.IsBalance() << endl;
	}
	t.InOrder();
}