【五一创作】|【C++】AVL树的实现

#include<iostream>
#include<cassert>
using namespace std;
template<class K, class V>
struct  AVLTreeNode
{

	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;//当前节点值
	int _bf;//平衡因子

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


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
   public:
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;//用于记录cur的前一个节点
		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
			{
				//若插入的值，在树中有相同的值 ，则插入失败
				return false;
			}
		}
		cur = new Node(kv);
		//再次判断parent当前节点值与插入值大小
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//cur的上一个节点即为 刚才的记录cur前一个节点的parent
		cur->_parent = parent;



		//更新平衡因子
		while (parent)
		{
			//若插入节点在parent的右子树
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			//若插入节点在parent的左子树
			else
			{
				parent->_bf--;
			}


			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			//平衡因子为0，不需要向上更新
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				//1.让这颗子树平衡 2.降低子树高度
				if ( parent->_bf == 2&&cur->_bf == 1 )//左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
				{
					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);
				}
				//旋转后整颗树已经平衡了，就不需要在继续了
				break;
			}
		}

		return true;
	}


	void inorder()//中序遍历
	{
		_inorder(_root);
		cout << endl;
	}
	//判断一颗二叉树是否为平衡树
	bool isbalance()
	{
		return _isbalance(_root);
	}
private:
	
	int height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftH = height(root->_left);//左子树高度
		int rightH = height(root->_right);//右子树高度
		//返回左右子树高度大的加1
		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	bool _isbalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftH = height(root->_left);
		int rightH = height(root->_right);

		if (rightH - leftH != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		 }
		//判断最终绝对值是否小于2
		return abs(leftH - rightH) < 2&&_isbalance(root->_left)&&_isbalance(root->_right);
	}
	 
	void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << " ";
		_inorder(root->_right);
	}
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		Node* ppnode = parent->_parent;//记录parent的前一个节点

		subR->_left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)//说明parent是根即代表整棵树
		{
			_root = subR;//subR作为新的根
			_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
		}
		else//说明旋转的是一部分，所以要跟ppnode相连接
		{
			if (ppnode->_left == parent)//若连接在左子树上
			{
				ppnode->_left = subR;
			}
			else//若连接在右子树上
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;//将subR父节点置为ppnode
		}
		parent->_bf = subR->_bf = 0;//平衡因子都为0
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		Node* ppnode = parent->_parent;//记录parent的父节点
		subL->_right = parent;
		parent->_parent = subL;

		if (ppnode == nullptr)//若旋转整棵树
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else//若旋转整棵树的部分子树
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;//使subL的父节点为ppnode
		}
		parent->_bf = subL->_bf = 0;

	}

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;//记录平衡因子，在后续单旋会置为0
		
		//先对parent的左子树进行左单旋
		RotateL(parent->_left);
		//再对当前根进行右单旋
		RotateR(parent);

		if (bf == -1)//h==2时，在b处插入节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)//h==2时，在c处插入节点
		{
			subL ->_bf = -1;
			subLR ->_bf= 0;
			parent->_bf = 0;
		}
		else if (bf == 0)//当h==0时，60作为新增节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}

	}

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;//记录平衡因子，在后续单旋会置为0
		RotateR(parent->_right);
		RotateL(parent);
		//h==2时，c插入，c的高度变化为h
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		//h==2时，b插入，b的高度变化为h
		else if (bf ==-1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		// h==1时，60本身就是新增节点
		else if(bf == 0 )
		{
			subR->_bf = 0;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			//不存在情况，若进入则出问题了
			assert(false);
		}
	}

private:
	Node* _root = nullptr;
};


void test_AVLTree1()
{
    //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
	AVLTree<int, int>v1;
	for (auto e : a)
	{
		v1.insert(make_pair(e,e));
	}
	v1.inorder();
	cout << v1.isbalance() << endl;//返回值为布尔值
}