C++---AVL树

目录

1 AVL 树

1.1 AVL树的概念

1.2 AVL树节点的定义

1.3 AVL树的插入

旋转总体分为四种情况：

1. 新节点插入较高右子树的右侧---右右：左单旋​

 2. 新节点插入较高左子树的左侧---左左：右单旋​

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋​

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

1 AVL 树

1.1 AVL树的概念

        二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

        ~它的左右子树都是AVL树
        ~左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)，(平衡因子非必需，但是加入平衡因子更容易实现)

         如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(log_2 n)，搜索时间复杂度O(log_2 n)。

1.2 AVL树节点的定义

AVL树节点的定义：

template<class K,class V>
	struct AVLTreeNode//定义成三叉链有助于后期旋转
	{
        AVLTreeNode(const pair& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)
			,_bf(0)
		{}
 
		AVLTreeNode* _left;//指向左子树
		AVLTreeNode* _right;//指向右子树
		AVLTreeNode* _parent;//指向父节点
 
		pair _kv;//节点值
		int _bf;//balance factor平衡因子
	};

1.3 AVL树的插入

        AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
        1. 按照二叉搜索树的方式插入新节点
        2. 调整节点的平衡因子

首先，按照二叉搜索树方式插入新节点：

template<class K, class V>
	struct AVLTree
	{
		typedef AVLTreeNode Node;
	public:
		bool Insert(const pair& 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->_right;
				}
				else if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			//插入
			cur = new Node(kv);
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;
 
			//接下来控制平衡
 
 
			return true;
 
		}
	private:
		Node* _root = nullptr;
	};

那么，如何控制平衡呢？

首先，插入以后，我们要更新平衡因子：

 

//1.更新平衡因子
while (parent)
{
	if (cur == parent->_right)
	{
		parent->_bf++;
	}
	else
	{
		parent->_bf--;
	}
 
	if (parent->_bf == 0)
	{
		break;
	}
	else if (abs(parent->_bf) == 1)
	{
		parent = parent->_parent;
		cur = cur->_parent;
	}
	else if (abs(parent->_bf) == 2)
	{
		//说明parent所在子树不平衡，需要旋转
 
	}
	else
	{
		//理论不会走到这，除非插入前就不平衡
		assert(false);
	}
}

更新完平衡因子，我们需要在parent->_bf == 2 的地方旋转树，使之平衡。

旋转总体分为四种情况：

1. 新节点插入较高右子树的右侧---右右：左单旋

上图中插入前AVL树是平衡的，a,b,c表示高度为 h 的子树（并不是节点），h 为 0 则表示直接在节点为30的左子树直接插入。

void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
 
			parent->_right = subRL;
			if (subRL)//subRL可以为空，所以加条件
			{
				subRL->_parent = parent;
			}
			//parnet 可能为根也可以不是，记录一下
			Node* ppNode = parent->_parent;
 
			subR->_left = parent;
			parent->_parent = subR;
 
			if (_root == parent)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = subR;
				}
				else
				{
					ppNode->_right = subR;
				}
				subR->_parent = ppNode;
			}
            //更新平衡因子
			subR->_bf = parent->_bf = 0;
		}

 2. 新节点插入较高左子树的左侧---左左：右单旋

  右单旋与左单旋刚好对称，方法类似。         

void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
 
			parent->_left = subLR;
			if (subLR)//subLR可以为空，所以加条件
			{
				subLR->_parent = parent;
			}
			Node* ppNode = parent->_parent;
 
			subL->_right = parent;
			parent->_parent = subL;
 
			if (_root == parent)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = subL;
				}
				else
				{
					ppNode->_right = subL;
				}
				subL->_parent = ppNode;
			}
			//更新平衡因子
			subL->_bf = parent->_bf = 0;
		}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

        将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
考虑平衡因子的更新。
        双旋的平衡因子要分 在b子树插入，在c子树插入以及a,b,c,d为空数 三种情况。

void RotateLR(Node* parent)
		{
			//记录节点，用于后面改平衡因子
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;
 
			RotateL(parent->_left);
			RotateR(parent);
			//更新平衡因子
			subLR->_bf = 0;
			if (bf == 1)
			{
				parent->_bf = 0;
				subL->_bf = -1;
			}
			else if (bf == -1)
			{
				parent->_bf = 0;
				subL->_bf = 1;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				subL->_bf = 0;
			}
			else
			{
				//理论不会出现
				assert(false);
			}
		}

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

 方法与 先左单旋再右单旋 相反。

void RotateRL(Node* parent)
		{
			//记录节点，用于后面改平衡因子
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;
 
			RotateR(parent->_right);
			RotateL(parent);
 
			//更新平衡因子
			subRL->_bf = 0;
			if (bf == 1)
			{
				subR->_bf = 0;
				parent->_bf = -1;
			}
			else if (bf == -1)
			{
				subR->_bf = 1;
				parent->_bf = 0;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				subR->_bf = 0;
			}
			else
			{
				//理论不会出现
				assert(false);
			}
		}