Balanced binary search tree

”code is art that makes our heart sing "

                                                                                                    --2021.8.28

Definition :

1. A binary search tree , The right node must be greater than （ Or equal to the parent node ), Left node less than （ Or equal to ) Parent node

2. At the same time, the height of the left subtree minus the height of the right subtree of each node shall not be greater than 1, That is to say -1 0 1.

Knowledge points involved ：

1. Insert

  It can be divided into the following situations :LL type RR type LR type RL type

Programming reflection :1.root=nullptr The root node should be set to null at first 2. It can be accessed by pointer and location character 3. Recursion has to have termination conditions

LL type :

RR type :

RL type :

LR type :

  Level traversal :

1. In the form of queues

2. Put the root node into , After that, it will be gradually put into the left and right nodes of each node

Template code :

#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
#define MAX_SIZE 128
template<typename T>
class AVLNode
{
public:
	AVLNode<T>() : left(NULL),right(NULL),parent(NULL), height(1) {}
	AVLNode<T>(T data) : left(NULL), right(NULL), parent(NULL), data(data), height(1) {}
	~AVLNode() {};
	T data;
	int height;
	AVLNode<T>* left;
	AVLNode<T>* right;
	AVLNode<T>* parent;
};
template<typename T>
class Queue
{
public:
	Queue<T>() : front(-1), rear(-1) { data[MAX_SIZE] = {}; }
	int front;
	int rear;
	AVLNode<T>* data[MAX_SIZE];
};
template<typename T>
void initQueue(Queue<T>* q)
{
	q->front = q->rear = -1;
}
template<typename T>
bool emptyQueue(Queue<T>* q)
{
	if (q->front == q->rear)
	{
		return true;
	}
	return false;
}
template<typename T>
bool enQueue(Queue<T>* q, AVLNode<T>*& node)
{
	if (q->rear == MAX_SIZE - 1)// The queue is full 
	{
		return false;
	}
	q->rear++;// Add at the end of the queue 
	q->data[q->rear] = node;
	return true;
}
template<typename T>
bool deQueue(Queue<T>* q, AVLNode<T>*& node)
{
	if (q->front == q->rear)// The queue is empty 
	{
		return false;
	}
	q->front++;//
	node = q->data[q->front];// Change value 
	return true;
}
template<typename T>
class AVLTree
{
private:

public:
	AVLNode<T>* root;
	AVLTree<T>() { this->root = nullptr ; };
	~AVLTree<T>() { delete root; };
	void _insert(T data)
	{
		
		if (nullptr == this->root)
		{
			this->root = new AVLNode<T>(data);// Judge whether it is empty before creating 
			return;// Remember return
		}
		this->root=_insert(this->root, data);
	}
	AVLNode<T>* _insert(AVLNode<T>* &root, T data)
	{
		
		// Insert left subtree and right subtree 
		if (/*nullptr!=root*/data < root->data)
		{
			if (nullptr == root->left)
			{
				root->left = new AVLNode<T>(data);
				root->left->parent=root;// Creating links is important 
			}
			else
			{
				_insert(root->left, data);// Recursion has to have termination conditions 
			}
		}
		else if(data>root->data)
		{
			
				if (nullptr == root->right)
				{
					root->right = new AVLNode<T>(data);
					root->right->parent = root;// This step is very important 
				}
				else 
				{
					_insert(root->right, data);
				}
		}
		// Rotation operation 
		root->height = calHeight(root);
		if (calBF(root) == 2)// That is the LL type 
		{
			// If it is LR type 
			if (calBF(root->left) == -1)
			{
				root->left = leftRotate(root->left);// First left 
			}
			root = rightRotate(root);// Retrodextral 
		}
		if (calBF(root) == -2)// That is the RR type 
		{
			if (calBF(root->right) == 1)// That is the RL type 
			{
				root->right = rightRotate(root->right);

			}
			root = leftRotate(root);
		}
		return root;

	}
	void preOrder()
	{
		preOrder(root);
	}
	void preOrder(AVLNode<T>* root)
	{
		if (nullptr == root)
		{
			return;
		}
		cout << root->data << " " << "height:" << root->height << endl;
		preOrder(root->left);
		preOrder(root->right);
	}
	void inOrder()
	{
		inOrder(root);
	}
	void inOrder(AVLNode<T>* root)
	{
		if (nullptr == root)
		{
			return;
		}
		inOrder(root->left);
		cout << root->data << " " << "height:" << root->height << endl;
		inOrder(root->right);
	}
	void postOrder()
	{
		postOrder(root);
	}
	void postOrder(AVLNode<T>* root)
	{
		if (nullptr == root)
		{
			return;
		}
		postOrder(root->left);
		postOrder(root->right);
		cout << root->data << " " << "height:" << root->height << endl;
	}
	void layerOrder()
	{
		Queue<T>* q = new Queue<T>();
		initQueue(q);
		if (nullptr != this->root)
		{
			enQueue(q, this->root);// First join the root node 
		}
		while (!emptyQueue(q))
		{
			deQueue(q, this->root);// Out of the team 
			cout << this->root->data << " ";//root It's constantly updated 
			if (nullptr != this->root->left)// Join the left node first   Then join the right node   Make sure to output... From the right first 
			{
				enQueue(q, this->root->left);
			}
			if (nullptr != this->root->right)//
			{
				enQueue(q, this->root->right);
			}
		}

	}
	int calHeight(AVLNode<T>* root);// Calculate the height   Height from bottom to top   Depth from top to bottom 
	int calBF(AVLNode<T>* root);// Calculate the equilibrium factor 
	AVLNode<T>* leftRotate(AVLNode<T>* root);
	AVLNode<T>* rightRotate(AVLNode<T>* root);
};
//Node Class function 
template <typename T>
int AVLTree<T>::calHeight(AVLNode<T>* root)
{
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else if (root->left == NULL)
	{
		return root->right->height + 1;
	}
	else if (root->right == NULL)
	{
		return root->left->height + 1;
	}
	else
	{
		return root->left->height > root->right->height ? root->left->height + 1 : root->right->height + 1;
	}
}
template <typename T>
int AVLTree<T>::calBF(AVLNode<T>* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 0;
	}
	else if (root->left == NULL)
	{
		return - root->right->height;
	}
	else if (root->right == NULL)
	{
		return root->left->height;
	}
	else
	{
		return root->left->height - root->right->height;
	}
}
template<typename T>
AVLNode<T>* AVLTree<T>::leftRotate(AVLNode<T>*root)
{
	
	AVLNode<T> *oldRoot = root;
	AVLNode<T> *newRoot = root->right;
	AVLNode<T> *parent = root->parent;
	if (NULL != parent)
	{
		if (oldRoot->parent->data > oldRoot->data)
		{
			parent->left = newRoot;
		}
		else
		{
			parent->right = newRoot;
		}
	}
	newRoot->parent = parent;
	// The above determines which subtree of the original node the old node is in   Replace with a new node 
	oldRoot->right = newRoot->left;// If there is a left subtree 
	if (NULL != newRoot->left)
	{
		newRoot->left->parent = oldRoot;
	}
	newRoot->left = oldRoot;
	oldRoot->parent = newRoot;
	oldRoot->height = calHeight(oldRoot);
	newRoot->height = calHeight(newRoot);
	return newRoot;
	// The above changes the left subtree of the new node into the right subtree of the old node , And change the old node into the left subtree of the new node  
}
template<typename T>
AVLNode<T>* AVLTree<T>::rightRotate(AVLNode<T>* root)
{
	AVLNode<T> *oldRoot = root;
	AVLNode<T> *newRoot = root->left;
	AVLNode<T> *parent = root->parent;
	if (NULL != parent)
	{
		if (oldRoot->parent->data > oldRoot->data)// Determine the left and right nodes of the old node and its parent node 
		{
			parent->left = newRoot;
		}
		else
		{
			parent->right = newRoot;
		}
	}
	newRoot->parent = parent;
	oldRoot->left = newRoot->right;
	if (NULL != newRoot->right)
	{
		newRoot->right->parent = oldRoot;
	}
	newRoot->right = oldRoot;
	oldRoot->parent = newRoot;
	newRoot->height = calHeight(newRoot);
	oldRoot->height = calHeight(oldRoot);
	return newRoot;
}

int main()
{
	AVLTree<int>*tree=new AVLTree<int>();
	tree->_insert(3);
	tree->_insert(2);
	tree->_insert(1);
	tree->_insert(4);
	tree->_insert(5);
	tree->_insert(6);
	tree->_insert(7);
	tree->_insert(10);
	tree->_insert(9);
	tree->_insert(8);
	tree->layerOrder();
	return 0;
}