【C++高阶】：AVL树的全面探索和深度学习

✨                                                       世事漫随流水，算来一梦浮生      🌏 

📃个人主页：island1314

🔥个人专栏：C++学习

🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏  💞 💞 💞

🚀前言

       前面我们学到了二叉搜索树，【C++高阶】二叉搜索树的全面解析与高效实现

       虽然二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法，即AVL树，它以其独特的平衡机制和高效的搜索性能，成为了一颗璀璨的明星。它不仅解决了二叉搜索树在数据插入和删除时可能产生的失衡问题，更通过旋转操作，使得树的高度始终保持在一个相对较低的水平，从而保证了搜索的高效性。让我们来详细看看AVL树到底是怎么解决上述问题的吧，踏上这学习之旅。

一. AVL树的概念

📒二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度，

📙一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

  

  🎈注意： 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O（）搜索时间复杂度O（）。

  二. AVL树节点的定义

  AVL树节点的定义通常包含以下几个关键部分：

  🧩1. 基本元素

       在调整失衡的AVL树时，我们需要频繁的访问父节点，所以在AVL树中我们需要使用三叉链，因此AVL树的节点除了包含左右子节点的指针，还需要一个指向父节点的指针。

  • _left：指向节点的左子节点的指针
  • _right：指向节点的右子节点的指针
  • _parent：指向节点的父节点的指针
  • _kv：一个结构体或配对（pair），包含节点的键值（key）和值（value）。这取决于AVL树的具体用途，可能只包含键或包含键值对。

    🧩2. 平衡因子（_bf）

    • 一个整数，表示节点左子树和右子树的高度差。AVL树的性质要求任何节点的平衡因子的绝对值不超过1（-1, 0, 1）

    • 如果左子树比右子树高一层，那么平衡因子就为-1；如果左右子树一样高，平衡因子就为0；如果右子树比左子树高一层，那么平衡因子就为1，这三种情况下AVL树的性质都没有被打破。

    • 按照这个规则，如果平衡因子为-2、2或其他值，则说明左右子树已经失衡，性质被打破。

      🧩3.构造函数

      • 初始化一个新节点时，通常需要一个构造函数，它接受一个键值对（或仅键），并设置节点的左子节点、右子节点、父节点和平衡因子（初始化为0）

        另外需要说明一下，本文中，我们使用key/value模型的AVL树

        🧩AVL节点定义：

        template
        struct AVLTreeNode
        {
        	pair _kv;//第一个数据存储key，第二个数据存储value
        	AVLTreeNode* _left;
        	AVLTreeNode* _right;
        	AVLTreeNode* _parent;
        	int _bf; // balance factor，平衡因子，值为右子树与左子树高度差，右边插入就加一，左边插入减一
        	AVLTreeNode(const pair& kv)
        		:_kv(kv)
        		, _left(nullptr)
        		, _right(nullptr)
        		, _parent(nullptr)
        		, _bf(0)  //新节点左右都为空，平衡因子为0
        	{}
        };

        注意：

        可能有些同学对pair没有了解，这里简单介绍一下，pair可以将两个数据组成一组元素，因此对于key/value模型这种需要用到两个数据为一组的元素时就可以使用，内部的成员变量为first和second，主要使用方法如下：

        pair p1(v1, v2); //输入两个数据创建pair类型变量
        make_pair(v1, v2);       //输入两个数据通过函数创建pair类型变量
        p1.first                 //访问p1的第一个数据
        p1.second                //访问p1的第二个数据

        三. AVL树的插入

        🌈AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

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

          在我们进行插入操作之前，我们先定义一个AVL树的类

          AVL树定义：

          template
          class AVLTree
          {
              typedef AVLTreeNode Node;
          public:
              // 其他未实现的成员函数
          private:
              Node* _root = nullptr;
          };

          cur插入后，parent的平衡因子一定需要调整

          在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

          • 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
          • 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

            插入后，parent的平衡因子可能有三种情况：0，正负1， 正负2

            • 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整

              成0，此时满足AVL树的性质，插入成功

            • 如果parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更

              新成正负1，此时以parent为根的树的高度增加，需要继续向上更新

            • 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进

              行旋转处理

              AVL树的插入操作类似于我们之前二叉搜索树的插入，只不过AVL树的插入操作涉及到旋转操作，我们先演示一下它的全部代码

              bool Insert(const pair& kv)  //和之前的二叉平衡树插入类似
              {
              	if (_root == nullptr)
              	{
              		_root = new Node(kv);
              		return true;
              	}
              	//第一步先找到cur应该插入的位置
              	Node* parent = nullptr, * cur = _root;
              	while (cur)
              	{
              		parent = cur; //保留其父节点
              		if (cur->_kv.first _right;
              		}
              		else if (cur->_kv.first > kv.first)
              		{
              			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 (cur == parent->_left) //在左侧插入节点，平衡因子减小
              			parent->_bf--;
              		else //右侧插入节点，平衡因子增大
              			parent->_bf++;
              		if (parent->_bf == 0)
              		{
              			break;
              		}
              		else if (parent->_bf == 1 || parent->_bf == -1)
              		{
              			// 继续往上更新
              			cur = parent;
              			parent = parent->_parent;
              		}
              		else if (parent->_bf == 2 || parent->_bf == -2) //和书上相反，因为书上是把左侧插入节点平衡因子增大，这里左侧插入减小
              		{
              			// 不平衡了，旋转处理，cur为插入节点的父节点，paernt为cur的父节点
              			if (parent->_bf == 2 && cur->_bf == 1) //RR型，在子树根节点右子树的右子树插入节点
              			{ //逆时针左旋转
              				RotateL(parent);
              			}
              			else if (parent->_bf == -2 && cur->_bf == -1)//LL型，在子树根节点左子树上的左子树插入节点，
              			{ //顺时针右旋转
              				RotateR(parent);
              			}
              			else  if (parent->_bf == 2 && cur->_bf == -1) //RL型，在子树根节点右子树上的左子树插入节点
              			{//先顺时针右旋变成RR型，再逆时针左旋，最后就是原子树根节点右子树上左子树作为子树根节点。
              				RotateRL(parent);
              			}
              			else if (parent->_bf == -2 && cur->_bf == 1) //LR型，在子树根节点左子树上的右子树插入节点
              			{ //先逆时针左旋变成LL型，再顺时针右旋，最后就是原子树根节点左子树上的右子树作为子树根节点。
              				RotateLR(parent);
              			}
              			break;
              		}
              		else
              		{
              			assert(false);
              		}
              	}
              	return true;
              }

              四. AVL树的旋转

              如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，

              使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

              🌈右单旋

              新节点插入子树根节点左子树的左子树上（LL型）:

              

              此处旋转是将30的右子树变成60的左子树，然后让60成为30的右子树

              在旋转中有几点要注意：

              • 30这个节点的右孩子可能不存在
              • 60这个节点可能是根节点，也可能是子树

                如果是根节点，旋转完成后，要更新根节点
                如果是子树，可能是某个节点的左子树，也可能是右子树

                AVL树右单旋代码示例：

                void RotateR(Node* parent) //顺时针右单旋，arent为根，subL为根左子树，subLR为根左子树的右子树
                { //subLR变成parene的左边，parent变成subL的右边，subL变成这颗子树的根
                	Node* subL = parent->_left, *subLR = subL->_right;
                	Node* parentParent = parent->_parent;
                	
                	//改变parent的左子树
                	parent->_left = subLR;
                	if (subLR != nullptr) //避免为空
                		subLR->_parent = parent;
                	//改变parent的父节点
                	subL->_right = parent;
                	parent->_parent = subL;
                	//改变子树根节点，调整subL为子树根节点
                	if (parentParent == nullptr){//第一种情况：parent为根节点
                		_root = subL;
                		subL->_parent = nullptr;
                	}
                	else{//第二种情况：parent不为根节点
                		if (parentParent->_left == parent) parentParent->_left = subL;
                		else parentParent->_right = subL;
                		subL->_parent = parentParent; //记得更新子树根节点的父节点
                	}
                	parent->_bf = subL->_bf = 0; //更新平衡因子
                }

                🌈左单旋

                新节点插入子树根节点右子树的右子树上（LL型）:

                

                左单旋与上面的右单旋类似，所以我们直接来看代码

                AVL树左单旋代码示例：

                void RotateL(Node* parent) //逆时针左单旋，parent为子树根节点，subR为根右子树，subRL为根右子树的左子树
                { //subRL变成parene的右边，parent变成subR的左边，subR变成这颗子树的根
                	Node* subR = parent->_right, *subRL = subR->_left;
                	Node* parentParent = parent->_parent;
                	//改变parentt的右子树
                	parent->_right = subRL;
                	if(subRL != nullptr) //避免为空
                		subRL->_parent = parent;
                	//改变parent的父节点
                	subR->_left = parent;
                	parent->_parent = subR;
                	//改变子树根节点，调整subR为子树根节点
                	if (parentParent == nullptr) { //第一种情况：parent为根节点
                		_root = subR;
                		subR->_parent = nullptr;
                	}
                	else{ //第二种情况，parent不是根节点
                		if (parentParent->_left == parent) parentParent->_left = subR;
                		else parentParent->_right = subR;
                		subR->_parent = parentParent;//记得更新子树根节点的父节点
                	}
                	parent->_bf = subR->_bf = 0;//更新平衡因子
                }

                🌙左右双旋

                新节点插入子树根节点左子树的右子树上（LR型）:

                

                这里是将双旋变成单旋后再旋转，先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。

                AVL树左右双旋代码示例：

                void RotateLR(Node* parent) //先以根节点的左子树进行右旋，再对根节点进行左旋
                {
                	Node* subL = parent->_left, *subLR = subL->_right;
                	int bf = subLR->_bf;
                	RotateL(parent->_left);
                	RotateR(parent);
                	if (bf == 0) { //其本身就是新增节点，h = 0
                		subL->_bf = 0;
                		subLR->_bf = 0;
                		parent->_bf = 0;
                	}
                	else if (bf == 1) { //在subL的右子树插入节点
                		subL->_bf = -1;
                		subLR->_bf = 0;
                		parent->_bf = 0;
                	}
                	else if (bf == -1){ //在subL的左子树插入节点
                		subL->_bf = 0;
                		subLR->_bf = 0;
                		parent->_bf = 1;
                	}
                	else assert(false);
                }

                🌙右左双旋

                新节点插入子树根节点右子树的左子树上（RL型）:

                

                操作过程左右双旋类似，我们直接看代码

                void RotateRL(Node* parent) //先以根节点的右子树进行右旋，再对根节点进行左旋
                {
                	Node* subR = parent->_right, *subRL = subR->_left;
                	int bf = subRL->_bf; //g
                	RotateR(parent->_right);
                	RotateL(parent);
                	//更新平衡因子
                	if (bf == 0) { //其本身就是新增节点, h = 0
                		subR->_bf = 0;
                		subRL->_bf = 0;
                		parent->_bf = 0;
                	}
                	else if (bf == -1) { //在subRL上的右子树插入节点
                		subR->_bf = 1;
                		subRL->_bf = 0;
                		parent->_bf = 0;
                	}
                	else if (bf == 1) { //在subRL的左子树上插入节点
                		subR->_bf = 0;
                		subRL->_bf = 0;
                		parent->_bf = -1;
                	}
                	else assert(false);
                }

                总结：

                假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

                • parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
                  当subR的平衡因子为1时，执行左单旋
                  当subR的平衡因子为-1时，执行右左双旋
                  • parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
                    当subL的平衡因子为-1是，执行右单旋
                    当subL的平衡因子为1时，执行左右双旋

                    旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新

                    五. AVL树的验证

                    📝AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

                    📝1. 验证其为二叉搜索树

                    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

                    代码示例：

                    void InOrder()
                    {
                    	_InOrder(_root);
                    	cout _left);
                    	cout _kv.first _right);
                    }
                    

                    📝2. 验证其为平衡树

                    • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
                    • 节点的平衡因子是否计算正确

                      代码示例：

                      	bool IsBalance()
                      	{
                      		return _IsBalance(_root);
                      	}
                      private:  
                      	bool _IsBalance(Node* root) 
                      	{
                      		if (root == nullptr) return true;
                      		int leftHeight = _Height(root->_left), rightHeight = _Height(root->_right);
                      		int diff = rightHeight - leftHeight;
                      		if (abs(diff) >= 2)
                      		{
                      			cout _kv.first _left);
                      		size_t rightHeight = _Height(root->_right);
                      		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
                      	}

                      📝3. 验证用例：

                      void TestAVLTree()
                      {
                      	AVLTree t;
                      	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
                      	for (auto e : a)
                      	{
                      		t.Insert({ e, e });
                      		//cout  kv.first)
                      			{
                      				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 (cur == parent->_left) //在左侧插入节点，平衡因子减小
                      				parent->_bf--;
                      			else //右侧插入节点，平衡因子增大
                      				parent->_bf++;
                      			if (parent->_bf == 0)
                      			{
                      				break;
                      			}
                      			else if (parent->_bf == 1 || parent->_bf == -1)
                      			{
                      				// 继续往上更新
                      				cur = parent;
                      				parent = parent->_parent;
                      			}
                      			else if (parent->_bf == 2 || parent->_bf == -2) //和书上相反，因为书上是把左侧插入节点平衡因子增大，这里左侧插入减小
                      			{
                      				// 不平衡了，旋转处理，cur为插入节点的父节点，paernt为cur的父节点
                      				if (parent->_bf == 2 && cur->_bf == 1) //RR型，在子树根节点右子树的右子树插入节点
                      				{ //逆时针左旋转
                      					RotateL(parent);
                      				}
                      				else if (parent->_bf == -2 && cur->_bf == -1)//LL型，在子树根节点左子树上的左子树插入节点，
                      				{ //顺时针右旋转
                      					RotateR(parent);
                      				}
                      				else  if (parent->_bf == 2 && cur->_bf == -1) //RL型，在子树根节点右子树上的左子树插入节点
                      				{//先顺时针右旋变成RR型，再逆时针左旋，最后就是原子树根节点右子树上左子树作为子树根节点。
                      					RotateRL(parent);
                      				}
                      				else if (parent->_bf == -2 && cur->_bf == 1) //LR型，在子树根节点左子树上的右子树插入节点
                      				{ //先逆时针左旋变成LL型，再顺时针右旋，最后就是原子树根节点左子树上的右子树作为子树根节点。
                      					RotateLR(parent);
                      				}
                      				break;
                      			}
                      			else
                      			{
                      				assert(false);
                      			}
                      		}
                      		return true;
                      	}
                      	Node* Find(const K& key)
                      	{
                      		Node* cur = _root;
                      		while (cur)
                      		{
                      			if (cur->_key _right;
                      			}
                      			else if (cur->_key > key){
                      				cur = cur->_left;
                      			}
                      			else{
                      				return cur;
                      			}
                      		}
                      		return nullptr;
                      	}
                      	Node* LeftMost()
                      	{
                      		if (_root == nullptr) return nullptr;
                      		Node* cur = _root;
                      		while (cur->_left) cur = cur->_left;
                      		return cur;
                      	}
                      	Node* RightMost()
                      	{
                      		if (_root == nullptr) return nullptr;
                      		Node* cur = _root;
                      		while (cur->_right) cur = cur->_right;
                      		return cur;
                      	}
                      	void InOrder()
                      	{
                      		_InOrder(_root);
                      		cout _left), rightHeight = _Height(root->_right);
                      		int diff = rightHeight - leftHeight;
                      		if (abs(diff) >= 2)
                      		{
                      			cout _kv.first _left);
                      		size_t rightHeight = _Height(root->_right);
                      		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
                      	}
                      	void _InOrder(Node* root)
                      	{
                      		if (root == nullptr)
                      		{
                      			return;
                      		}
                      		_InOrder(root->_left);
                      		cout _kv.first _right, *subRL = subR->_left;
                      		Node* parentParent = parent->_parent;
                      		//改变parentt的右子树
                      		parent->_right = subRL;
                      		if(subRL != nullptr) //避免为空
                      			subRL->_parent = parent;
                      		//改变parent的父节点
                      		subR->_left = parent;
                      		parent->_parent = subR;
                      		//改变子树根节点，调整subR为子树根节点
                      		if (parentParent == nullptr) { //第一种情况：parent为根节点
                      			_root = subR;
                      			subR->_parent = nullptr;
                      		}
                      		else{ //第二种情况，parent不是根节点
                      			if (parentParent->_left == parent) parentParent->_left = subR;
                      			else parentParent->_right = subR;
                      			subR->_parent = parentParent;//记得更新子树根节点的父节点
                      		}
                      		parent->_bf = subR->_bf = 0;//更新平衡因子
                      	}
                      	void RotateR(Node* parent) //顺时针右单旋，arent为根，subL为根左子树，subLR为根左子树的右子树
                      	{ //subLR变成parene的左边，parent变成subL的右边，subL变成这颗子树的根
                      		Node* subL = parent->_left, *subLR = subL->_right;
                      		Node* parentParent = parent->_parent;
                      		
                      		//改变parent的左子树
                      		parent->_left = subLR;
                      		if (subLR != nullptr) //避免为空
                      			subLR->_parent = parent;
                      		//改变parent的父节点
                      		subL->_right = parent;
                      		parent->_parent = subL;
                      		//改变子树根节点，调整subL为子树根节点
                      		if (parentParent == nullptr){//第一种情况：parent为根节点
                      			_root = subL;
                      			subL->_parent = nullptr;
                      		}
                      		else{//第二种情况：parent不为根节点
                      			if (parentParent->_left == parent) parentParent->_left = subL;
                      			else parentParent->_right = subL;
                      			subL->_parent = parentParent; //记得更新子树根节点的父节点
                      		}
                      		parent->_bf = subL->_bf = 0; //更新平衡因子
                      	}
                      	void RotateRL(Node* parent) //先以根节点的右子树进行右旋，再对根节点进行左旋
                      	{
                      		Node* subR = parent->_right, *subRL = subR->_left;
                      		int bf = subRL->_bf; //g
                      		RotateR(parent->_right);
                      		RotateL(parent);
                      		//更新平衡因子
                      		if (bf == 0) { //其本身就是新增节点, h = 0
                      			subR->_bf = 0;
                      			subRL->_bf = 0;
                      			parent->_bf = 0;
                      		}
                      		else if (bf == -1) { //在subRL上的右子树插入节点
                      			subR->_bf = 1;
                      			subRL->_bf = 0;
                      			parent->_bf = 0;
                      		}
                      		else if (bf == 1) { //在subRL的左子树上插入节点
                      			subR->_bf = 0;
                      			subRL->_bf = 0;
                      			parent->_bf = -1;
                      		}
                      		else assert(false);
                      	}
                      	void RotateLR(Node* parent) //先以根节点的左子树进行右旋，再对根节点进行左旋
                      	{
                      		Node* subL = parent->_left, *subLR = subL->_right;
                      		int bf = subLR->_bf;
                      		RotateL(parent->_left);
                      		RotateR(parent);
                      		if (bf == 0) { //其本身就是新增节点，h = 0
                      			subL->_bf = 0;
                      			subLR->_bf = 0;
                      			parent->_bf = 0;
                      		}
                      		else if (bf == 1) { //在subL的右子树插入节点
                      			subL->_bf = -1;
                      			subLR->_bf = 0;
                      			parent->_bf = 0;
                      		}
                      		else if (bf == -1){ //在subL的左子树插入节点
                      			subL->_bf = 0;
                      			subLR->_bf = 0;
                      			parent->_bf = 1;
                      		}
                      		else assert(false);
                      	}
                      	void Destroy(Node* root)
                      	{
                      		if (root == nullptr)return;
                      		Destroy(root->_left);
                      		Destroy(root->_right);
                      		delete root;
                      	}
                      	Node* Copy(Node* root)
                      	{
                      		if (root == nullptr)
                      			return nullptr;
                      		Node* newRoot = new Node(root->_key, root->_value);
                      		newRoot->_left = Copy(root->_left);
                      		newRoot->_right = Copy(root->_right);
                      		return newRoot;
                      	}
                      private:
                      	Node* _root = nullptr;
                      };
                      void TestAVLTree()
                      {
                      	AVLTree t;
                      	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
                      	for (auto e : a)
                      	{
                      		t.Insert({ e, e });
                      		//cout