【C++】AVL树的插入、旋转

目录

• 一、AVL树介绍
• • 1.1 概念
  • 1.2 定义
  • 二、AVL树的实现
  • • 2.1 插入
    • 2.2 旋转
    • • 2.2.1 左单旋
      • 2.2.2 右单旋
      • 2.2.3 左右双旋
      • 2.2.4 右左双旋

        一、AVL树介绍

        1.1 概念

        AVL树是高度平衡的二叉搜索树，相比普通的二叉搜索树，它防止了变成单支树的情况。因为AVL树每插入一个新的节点，它都会调整使左右子树的高度差的绝对值不超过1，从而降低了树的高度，提高了搜索效率。

        特点：

        • 左右子树都是AVL树
        • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
        • 搜索时间复杂度O( l o g 2 n log_2 n log2​n)
        • 有平衡因子控制高度差：右子树高度减去左子树高度

          

          1.2 定义

          AVL树是三叉链结构，即左孩子指针、右孩子指针和双亲指针，多了一个双亲指针方便找到上一个节点。定义它的数据域，为kv模型的类型。定义平衡因子，作用是记录当前节点的左右子树高度之差。

          template
          struct AVLTreeNode
          {
          	AVLTreeNode* _left;
          	AVLTreeNode* _right;
          	AVLTreeNode* _parent;
          	int _bf;
          	pair _kv;
          	AVLTreeNode(const pair& kv)
          		:_left(nullptr)
          		, _right(nullptr)
          		, _parent(nullptr)
          		, _bf(0)
          		, _kv(kv)
          	{}
          };
          

          二、AVL树的实现

          2.1 插入

          AVL树的插入过程与二叉搜索树的插入过程是一样的，只不过在此基础上增加了调整节点的平衡因子。所以总结为两个步骤：

          1. 按照二叉搜索树的方式插入新节点
          2. 调整节点的平衡因子

          没标数字的是新插入的节点

          

          调整平衡因子，首先要从cur和parent入手，即新插入的节点和插入节点的上一个节点。如果插入节点cur是parent的右边，则parent的平衡因子+1；反之，则-1。整个调整过程是一个循环，因为刚开始改变的是下面的平衡因子，上面节点的平衡因子也可能会随之改变。循环条件为parent不为空，还要其他条件可以终止循环，下面细讲。

          所以根据parent的平衡因子的值可以分为3步：

          1. parent的平衡因子为0
          2. parent的平衡因子为1或者-1
          3. parent的平衡因子为2或者-2

          这里说明下，没有parent的平衡因子可能为3/-3的情况，如果出现了说明之前的树有问题

          1️⃣parent的平衡因子为0

          此情况说明原来的parent的左边或者右边存在一个节点，新插入的节点在parent没有节点的一侧，parent两边都有节点，平衡因子为0，不影响上面的节点，调整结束，跳出循环。

          

          2️⃣parent的平衡因子为1或者-1

          如果parent的平衡因子为1或者-1，则会影响上面的节点，所以让parent节点转换为它的上一个节点，cur转换为parent，向上更新，以次类推。每次循环还是要经过cur是parent的左边还是右边，才能确定parent的平衡因子是+1还是-1。直到cur为根节点，parent为空时循环结束。

          

          3️⃣parent的平衡因子为2或者-2

          当parent向上更新，到某个节点时(有可能不是根节点)它的平衡因子为2或者-2，这时违背了AVL树的规则，因此要进行处理——旋转，来改变树的高度差，使其左右之树的高度差的绝对值不超过1

          下图的树插入节点后要发生旋转

          

          旋转后，高度差恢复平衡，跳出循环。

          总结：

          AVL树插入节点要进行调整平衡因子，调整结束有3种：

          1.parent为空——已经调整到根节点了

          2.parent的平衡因子为0——不影响上面节点

          3.旋转后——树恢复平衡状态

          代码：

          //插入
          bool Insert(const pair& kv)
          {
          	//如果根为空
          	if (_root == nullptr)
          	{
          		_root = new Node(kv);
          		return true;
          	}
          	//非空
          	Node* cur = _root;
          	Node* parent = nullptr;
          	while (cur)
          	{
          		if (cur->_kv.first _right;
          		}
          		else if (cur->_kv.first > kv.first)
          		{
          			parent = cur;
          			cur = cur->_left;
          		}
          		else
          		{
          			return false;//有重复不能插入
          		}
          	}
          	cur = new Node(kv);
          	if (parent->_kv.first _right = cur;
          	}
          	else
          	{
          		parent->_left = cur;
          	}
          	cur->_parent = parent;
          	//调整平衡因子
          	while (parent)
          	{
          		if (parent->_left == cur)
          		{
          			parent->_bf--;
          		}
          		else
          		{
          			parent->_bf++;
          		}
          		if (parent->_bf == 0)//不需要修改，直接跳出
          		{
          			break;
          		}
          		else if (parent->_bf == 1 || parent->_bf == -1)//向上更新
          		{
          			cur = cur->_parent;
          			parent = parent->_parent;
          		}
          		else if (parent->_bf == 2 || parent->_bf == -2)//要旋转
          		{
          			//旋转有4种情况
          			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
          			{
          				RotateRL(parent);//右左双旋-先右后左
          			}
          			break;//旋转后跳出
          		}
          		else
          		{
          			assert(false);//之前树就有问题
          		}
          	}
          	return true;
          }
          

          2.2 旋转

          这里就开始详细分析AVL树的旋转了，旋转分为4种情况，有左单旋、右单旋、左右双旋和右左双旋。发生这4种旋转的条件不一样，下面逐个分析：

          2.2.1 左单旋

          整体思路：cur的左孩子变成parent的右孩子（cur的左孩子可能为空），parent变成cur的左孩子，cur连接原来parent的双亲（有可能原来的parent就是根节点，如果是，cur变成根）

          先来简单的图示分析：

          

          parent是平衡因子为2的节点，cur是平衡因子为1的节点，为调整成平衡，parent要变成cur的左孩子，而在此之前，cur的左孩子要先变成parent的右孩子（上面的图节点较少，所以cur没有左孩子），最终平衡。

          通过上面的例子，可以基本了解左单旋的整个过程，下面来较多节点的例子：

          

          定义两个临时变量，subR指向parent的右孩子，即cur的位置(后面的操作就可以不用cur)，subRL为subR的左孩子。

          按照上面的步骤，subRL变成parent的右孩子，parent变成subR的左孩子，定义一个ppnode节点为原来parent的双亲，如果parent是在ppnode的左边，则ppnode的左边连接subR，；反之，则右边连接subR。如果parent原来是根节点，那么根节点就变成subR。最后修改parent和subR的平衡因子，它们的平衡因子都变成了0

          

          有个问题，旋转有4种情况，怎么知道用哪种呢？其实上面的两种图示已经显示出左单旋的条件。当parent的平衡因子为2，并且cur的平衡因子为1时，要进行的旋转为左单旋。

          代码：

          //左单旋
          void RotateL(Node* parent)
          {
          	Node* subR = parent->_right;
          	Node* subRL = subR->_left;
          	parent->_right = subRL;
          	//不为空
          	if (subRL)
          	{
          		subRL->_parent = parent;
          	}
          	subR->_left = parent;
          	Node* ppnode = parent->_parent;
          	parent->_parent = subR;
          	//处理parent如果为根
          	if (parent == _root)
          	{
          		_root = subR;
          		subR->_parent = nullptr;
          	}
          	//不为根，处理与ppnode的连接
          	else
          	{
          		if (ppnode->_left == parent)
          		{
          			ppnode->_left = subR;
          		}
          		else
          		{
          			ppnode->_right = subR;
          		}
          		subR->_parent = ppnode;
          	}
          	//修改平衡因子
          	parent->_bf = 0;
          	subR->_bf = 0;
          }
          

          2.2.2 右单旋

          整体思路：cur的右孩子变成parent的左孩子，parent变成cur的右孩子，cur连接原来parent的双亲。

          简单图示：

          

          parent是平衡因子为-2的节点，cur是平衡因子为-1的节点，为调整成平衡，cur的右孩子要先变成parent的右孩子，parent变成cur的右孩子，然后修改平衡因子，最终平衡。

          用较多节点的例子来分析：

          

          定义两个临时变量，subL指向parent的左孩子，subLR指向subL的右孩子。

          subLR变成parent的左孩子，parent变成subL的右孩子，定义一个ppnode节点为原来parent的双亲，步骤同左单旋。最后修改parent和subL的平衡因子，它们的平衡因子都变成了0

          

          通过例子可知，发生右单旋的条件是parent的平衡因子为-2，cur的平衡因子为-1

          代码：

          //右单旋
          void RotateR(Node* parent)
          {
          	Node* subL = parent->_left;
          	Node* subLR = subL->_right;
          	parent->_left = subLR;
          	//不为空
          	if (subLR)
          	{
          		subLR->_parent = parent;
          	}
          	subL->_right = parent;
          	Node* ppnode = parent->_parent;
          	parent->_parent = subL;
          	if (parent == _root)
          	{
          		_root = subL;
          		subL->_parent = nullptr;
          	}
          	else
          	{
          		if (ppnode->_left == parent)
          		{
          			ppnode->_left = subL;
          		}
          		else
          		{
          			ppnode->_right = subL;
          		}
          		subL->_parent = ppnode;
          	}
          	//修改平衡因子
          	parent->_bf = 0;
          	subL->_bf = 0;
          }
          

          2.2.3 左右双旋

          左右双旋是先左单旋，再右单旋。左单旋的是parent的左子树，右单旋的是包括parent的当前树。既然已经有单旋了，为什么还要双旋呢？如图：

          

          通过上面例子可知，如果插入的位置与前面(左单旋或者右单旋插入时的位置)不同，只有左或者右旋转不能使树变平衡，因此要进行双旋。

          左右双旋的情况主要分为以下3类：

          

          当插入的节点是subLR时，subLR的平衡因子为0；插入的节点在subLR的左边，subLR的平衡因子为-1，插入的节点在subLR的右边，subLR的平衡因子为1；通过图示可知，发生左右双旋的条件是parent的平衡因子为-2，cur的平衡因子为1。这3种情况经过左右双旋后，subLR的平衡因子都变成0，但是parent和subL的平衡因子是有区别的。

          下面来看看3种情况的旋转：

          1️⃣插入的新节点是subLR

          

          2️⃣插入的新节点在subLR的左边

          

          3️⃣插入的新节点在subLR的右边

          

          通过上面的图发现，当插入的新节点是subLR，subLR的平衡因子为0，旋转后，subL和parent的平衡因子也为0；插入的新节点在subLR的左边，subLR的平衡因子为-1，旋转后，subL的平衡因子为0，parent的平衡因子为1；插入的新节点在subLR的右边，subLR的平衡因子为1，旋转后，subL的平衡因子为-1，parent的平衡因子为0。

          代码：

          //左右双旋-先左后右
          void RotateLR(Node* parent)
          {
          	Node* subL = parent->_left;
          	Node* subLR = subL->_right;
          	int bf = subLR->_bf;//提前保存原来的bf
          	RotateL(subL);
          	RotateR(parent);
          	//旋转后，不同情况最后的bf会不一样
          	subLR->_bf = 0;//确定的
          	if (bf == -1)
          	{
          		subL->_bf = 0;
          		parent->_bf = 1;
          	}
          	else if (bf == 1)
          	{
          		subL->_bf = -1;
          		parent->_bf = 0;
          	}
          	else if (bf == 0)
          	{
          		subL->_bf = 0;
          		parent->_bf = 0;
          	}
          	else
          	{
          		assert(false);
          	}
          }
          

          2.2.4 右左双旋

          右左双旋是先右单旋，再左单旋。右单旋的是parent的右子树，左单旋的是包括parent的当前树。

          右左双旋也分为3类：

          

          当插入的节点是subRL时，subRL的平衡因子为0；插入的节点在subRL的左边，subRL的平衡因子为-1；插入的节点在subRL的右边，subRL的平衡因子为1；通过图示可知，发生右左双旋的条件是parent的平衡因子为2，cur的平衡因子为-1。这3种情况经过右左双旋后，subRL的平衡因子固定都变成了0，但是parent和subL的平衡因子有区别。

          下面是3种情况的旋转：

          1️⃣插入的新节点是subRL

          

          2️⃣插入的新节点在subRL的左边

          

          3️⃣插入的新节点在subRL的右边

          

          插入的新节点是subRL，subRL的平衡因子为0，旋转后，subR和parent的平衡因子也为0；插入的新节点在subRL的左边，subRL的平衡因子为-1，旋转后，subR的平衡因子为1，parent的平衡因子为0；插入的新节点在subRL的右边，subRL的平衡因子为1，旋转后，subR的平衡因子为0，parent的平衡因子为-1。

          代码：

          //右左双旋-先右后左
          void RotateRL(Node* parent)
          {
          	Node* subR = parent->_right;
          	Node* subRL = subR->_left;
          	int bf = subRL->_bf;
          	RotateR(subR);
          	RotateL(parent);
          	subRL->_bf = 0;
          	if (bf == -1)
          	{
          		subR->_bf = 1;
          		parent->_bf = 0;
          	}
          	else if (bf == 1)
          	{
          		subR->_bf = 0;
          		parent->_bf = -1;
          	}
          	else if (bf == 0)
          	{
          		subR->_bf = 0;
          		parent->_bf = 0;
          	}
          	else
          	{
          		assert(false);
          	}
          }