平衡二叉搜索树

”code is art that makes our heart sing "

                                                                                                    --2021.8.28

定义:

1.一棵二叉搜索树，满足右节点大于（或等于父节点),左节点小于（或等于)父节点

2.同时又满足每个节点的左子树的高度减去右子树的高度不大于1，即为-1 0 1.

涉及知识点：

1.插入

 分为以下几种情况:LL型 RR型 LR型 RL型

编程反思:1.root=nullptr 根节点一开始要设为空 2.用指针和取地符访问均可以3.递归要有终止条件

LL型:

RR型:

RL型:

LR型:

 层次遍历:

1.采用队列的形式

2.先将根节点放入，过后再逐步放入各节点的左右节点

模板代码:

#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)//队列已满
	{
		return false;
	}
	q->rear++;//在队尾进行添加
	q->data[q->rear] = node;
	return true;
}
template<typename T>
bool deQueue(Queue<T>* q, AVLNode<T>*& node)
{
	if (q->front == q->rear)//队列为空
	{
		return false;
	}
	q->front++;//
	node = q->data[q->front];//更改值
	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);//先判断空再创建
			return;//记得return
		}
		this->root=_insert(this->root, data);
	}
	AVLNode<T>* _insert(AVLNode<T>* &root, T data)
	{
		
		//插入左子树和右子树
		if (/*nullptr!=root*/data < root->data)
		{
			if (nullptr == root->left)
			{
				root->left = new AVLNode<T>(data);
				root->left->parent=root;//创建链接这个很重要
			}
			else
			{
				_insert(root->left, data);//递归要有终止条件
			}
		}
		else if(data>root->data)
		{
			
				if (nullptr == root->right)
				{
					root->right = new AVLNode<T>(data);
					root->right->parent = root;//这个步骤很重要
				}
				else 
				{
					_insert(root->right, data);
				}
		}
		//旋转操作
		root->height = calHeight(root);
		if (calBF(root) == 2)//说明是LL型
		{
			//如果是LR型
			if (calBF(root->left) == -1)
			{
				root->left = leftRotate(root->left);//先左旋
			}
			root = rightRotate(root);//后右旋
		}
		if (calBF(root) == -2)//说明是RR型
		{
			if (calBF(root->right) == 1)//说明是RL型
			{
				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);//先将根节点入队
		}
		while (!emptyQueue(q))
		{
			deQueue(q, this->root);//出队
			cout << this->root->data << " ";//root是不断更新的
			if (nullptr != this->root->left)//先将左结点入队 再将右结点入队 确保先从右边输出
			{
				enQueue(q, this->root->left);
			}
			if (nullptr != this->root->right)//
			{
				enQueue(q, this->root->right);
			}
		}

	}
	int calHeight(AVLNode<T>* root);//计算高度 高度从下往上 深度从上往下
	int calBF(AVLNode<T>* root);//计算平衡因子
	AVLNode<T>* leftRotate(AVLNode<T>* root);
	AVLNode<T>* rightRotate(AVLNode<T>* root);
};
//Node类函数
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;
	//以上判断旧节点在原先节点的哪个子树上 用新节点取替换
	oldRoot->right = newRoot->left;//如果有左子树存在
	if (NULL != newRoot->left)
	{
		newRoot->left->parent = oldRoot;
	}
	newRoot->left = oldRoot;
	oldRoot->parent = newRoot;
	oldRoot->height = calHeight(oldRoot);
	newRoot->height = calHeight(newRoot);
	return newRoot;
	//以上将新节点的左子树变成旧节点的右子树，并将旧节点变为新节点的左子树 
}
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)//判断旧节点其父节点的左右节点
		{
			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;
}