AVL tree - balanced binary tree


catalog:

I Concept & principle

Previously, we understood the binary search tree, but we found that if the data is orderly or close to orderly, the binary search tree will degenerate into a single tree

AVL tree is a balanced binary tree. It just adds a balance factor to the binary search tree to form the current balanced binary tree Binary search tree link
^
Here we focus on understanding the balance factor

II Balance factor

Balance factor: the balance factor is an integer value to judge whether the corresponding binary tree is balanced, so as to stabilize the binary tree and prevent the binary tree from degenerating into the above single branch tree

Rules:

1. There is a balance factor on each corresponding node to indicate whether the binary tree is balanced
~
2. Balance factor of each node = layers of right subtree - layers of left subtree
~
3. When the corresponding balance factor is (- 1 ~ 1), it is a balanced binary tree, otherwise it needs to be adjusted

III definition

There is a left child node inside the AVL tree Right child node Parent node Corresponding stored data There is also the balance factor. We create a structure and encapsulate it as something that should be stored inside a node

template<class T>		//Generic declaration
struct AVLNode{		//Created structure

	AVLNode<T>* _parent;	//Create corresponding parent node
	AVLNode<T>* _left;		//Left child
	AVLNode<T>* _right;		//Right child
	T _val;		//Internal corresponding value
	//Balance factor
	int _bf;	

	AVLNode(const T& val = T())		//Initialize a corresponding node
		:_parent(nullptr)		
		, _left(nullptr)
		, _right(nullptr)		//Node assigned nullptr
		, _val(val)		//Direct data transfer
		, _bf(0)		//The equilibrium factor is directly reduced to 0
	{}
};

In this way, all the things needed to create a corresponding node are passed in, When using this structure later, we only need to give it an alias, and then create it in the way of new

IV Rotation of AVL tree

1. Left hand interface understanding

Understanding of the left rotation interface: because the balance factor of the node will change after the AVL tree is inserted, for this reason, we need to operate the left rotation of the binary tree inserting a new node, so as to restore the binary tree to the balanced binary tree

	void RotateL(Node* parent){

		Node* subR = parent->_right;	//What is defined here is the right subtree corresponding to the parent node, that is, B
		Node* subRL = subR->_left;		//Here we get the left subtree of node B, that is, the node to be converted by left rotation

		subR->_left = parent;			//Connect B to the corresponding parent node
		parent->_right = subRL;			//Connect the right subtree of the parent node with B
		if (subRL)		//When the node in this intermediate state exists
			subRL->_parent = parent;	//Then let the parent node of its child node point to the real parent node
		if (parent == _root){			//When the parent node is the root node

			_root = subR;	//Point to parent node
			subR->_parent = nullptr;	//Its internal pointer is converted to null
		}
		else{	//If both exist

			Node* pparent = parent->_parent;	//Defines the parent node of the parent
			if (pparent->_left == parent)		//If the parent node is to the left of the grandfather node, point it to
				pparent->_left = subR;
			else
				pparent->_right = subR;			//Otherwise, it is the right direction
			subR->_parent = pparent;		//Finally, let the parent node generated by its left rotation point to the grandfather's node
		}

		parent->_parent = subR;	//Point the parent node of the parent to the child node of the rotation
		parent->_bf = subR->_bf = 0;		//Because after left rotation, the internal balance factor becomes 0
	}

The explanation of sinistral rotation has been relatively clear. The main thing is to draw pictures to understand the process step by step

2. Right hand interface understanding

The right-handed operation is similar to the left-handed operation. We can understand it by analogy. I won't comment more

	void RotateR(Node* parent){

		Node* subL = parent->_left;		//Similarly, create its corresponding node point
		Node* subLR = subL->_right;		//Its internal nodes point to

		subL->_right = parent;
		parent->_left = subLR;

		if (subLR)
			subLR->_parent = parent;
		//Determine whether the parent is the root node
		if (parent == _root){

			//Root node
			_root = subL;
			subL->_parent = nullptr;
		}
		else{

			Node* pparent = parent->_parent;
			if (pparent->_left == parent)
				pparent->_left = subL;
			else
				pparent->_right = subL;
			subL->_parent = pparent;
		}
		parent->_parent = subL;

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

3. Understanding of insert interface

The code about Insert here is connected. I just split it for easier understanding

For the implementation of inserting an element, we also first traverse the binary tree, find the corresponding addition position, and insert the corresponding data. We also need to use left-hand and right-hand operations to realize the balanced binary tree according to the insertion position

	bool insert(const T& val){		//Insert function

		//Binary search tree
		if (_root == nullptr){

			_root = new Node(val);	//If the root node is empty, it is directly created as the root node
			return true;
		}

		Node* cur = _root;		//Otherwise, the corresponding root node is created
		Node* parent = nullptr;		//Parent node is null
		while (cur){	//There is a corresponding insertion position

			parent = cur;		//Insert data
			if (cur->_val == val)
				return false;
			else if (cur->_val > val)
				cur = cur->_left;
			else
				cur = cur->_right;
		}

		cur = new Node(val);		//Create a new Node with Node
		if (parent->_val > val)
			parent->_left = cur;
		else
			parent->_right = cur;

		cur->_parent = parent;

		//Adjustment, starting from parent
		while (parent){

			//Update the balance factor of the parent
			if (parent->_left == cur)
				--parent->_bf;
			else
				++parent->_bf;

			if (parent->_bf == 0)	//parent short subtree height + 1
				break;
			else if (parent->_bf == 1 || parent->_bf == -1){

				//Continue to update upward
				cur = parent;
				parent = parent->_parent;
			}
			else if (abs(parent->_bf) == 2){

The above is the understanding of inserting nodes, and the following is the adjustment of the binary tree after inserting elements

(1) The new node is inserted to the left of the higher left subtree - left left: right single rotation

The distinction here is achieved by the size of the balance factor between the parent node and its corresponding child node!!!

if (parent->_bf == -2 && cur->_bf == -1){

					//If the left is high, it rotates right
					RotateR(parent);
				}

(2) The new node is inserted to the right of the higher right subtree - right right right: left single rotation

				else if (parent->_bf == 2 && cur->_bf == 1){

					RotateL(parent);	//Parent node left rotation
				}

(3) The new node is inserted to the right of the higher left subtree - left and right: first left single rotation and then right single rotation

				else if (parent->_bf == -2 && cur->_bf == 1){

					Node* subLR = cur->_right;
					int bf = subLR->_bf;

					RotateL(cur); 	//First child node left rotation
					RotateR(parent);	//Rotate the parent node to the right

					if (bf == 1){	Because when an update occurs,There will be a node update error,So update manually

						parent->_bf = 0;
						cur->_bf = -1;
					}
					else if (bf == -1){

						parent->_bf = 1;
						cur->_bf = 0;
					}
				}

(4) The new node is inserted to the left of the higher right subtree - right left: right single rotation first and then left single rotation

				else if (parent->_bf == 2 && cur->_bf == -1){

					//First obtain the bf corresponding to the subRL
					Node* subRL = cur->_left;
					int bf = subRL->_bf;

					RotateR(cur);
					RotateL(parent);

					//After the occurrence of right left double rotation, the bf value of the corresponding child nodes may be different and need to be updated
					//Here, the judgment method is used to distinguish the location of the linked node, and then update the corresponding bf
					if (bf == 1){

						cur->_bf = 0;  Because when an update occurs,There will be a node update error,So update manually
						parent->_bf = -1;
					}
					else if (bf == -1){

					cur->_bf = 1;
					parent->_bf = 0;
					}
				}
				break;
			}
		}
		return true;
	}

V Print interface

The printing interface here is relatively simple. It mainly uses recursive method to cycle to the internal val

	void inorder(){

		_inorder(_root);	//Call the following function
		cout << endl;
	}

	void _inorder(Node* root){

		if (root){

			_inorder(root->_left);		//First traverse the left node
			cout << root->_val << " ";
			_inorder(root->_right);		//Traversing the corresponding right node
		}
	}

Vi Verify AVL tree interface

The verification of AVL tree is to judge whether it is a balanced binary tree by the balance factor and the height difference between the left and right subtrees

	int Height(Node* root){		//Encapsulate the function to realize the height judgment of the corresponding child node

		if (root == nullptr)
			return 0;

		int left = Height(root->_left);
		int right = Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}

	bool _isBalance(Node* root){	//Function to judge whether it is balanced

		if (root == nullptr)
			return true;

		//Check whether the balance factor is consistent with the height difference between the left and right subtrees
		//Call the function to view the height of the corresponding subtree
		int left = Height(root->_left);
		int right = Height(root->_right);
		if (right - left != root->_bf){

			cout << " Node: " << root->_val << " bf:"
				<< root->_bf << " height gap: " << right - 1;		//output
			return false;
		}

		return abs(root->_bf) < 2
			&& _isBalance(root->_left)		//Circular judgment
			&& _isBalance(root->_right);
			//Balanced output 1
	}

	bool isBalance(){	//The final encapsulated interface

		return _isBalance(_root);
	}

In general, we still understand the implementation of balanced binary tree insertion, because traversal and left-handed and right-handed operations will be involved during insertion, which is difficult to understand. We pay attention to the understanding of left-handed and right-handed, as well as left-handed and right-handed

Keywords: Algorithm data structure Binary tree Cpp

Added by cbrknight on Fri, 11 Feb 2022 13:19:17 +0200