• 【C++】AVL树的4中旋转调整

    文章目录

    前提

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

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

    当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(-1、0、1)，即可降低树的高度，从而减少平均搜索长度。
    由此，该树被称为AVL树，即两位科学家名字的第一个字母。

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

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

      在这里插入图片描述
      如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。

    提示：以下是本篇文章正文内容，下面案例可供参考

    一、AVL树的结构定义

    树节点的结构创建：

    template<class K, class V>
struct AVLTreeNode
{
	
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
 	pair<K, V> _kv;  //键值对来存储 K AND V
	int _bf;//平衡因子
	//AVL树并没有规定必须要选择设计平衡因子，只是一个实现的选择，方便控制
 
	//构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
 
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    树的框架创建：

    
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;  //结点typedef 
public:
//......
private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    二、AVL的插入（重点）

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

    • 按照二叉搜索树的方式插入新节点
    • 调整节点的平衡因子
      （寻找位置->创建结点->插入节点->更新平衡因子->调整子树->形成AVL树）

    1. 插入的结点在较高左子树的左侧（右单旋）

    这样会造成parent的平衡因子变成-2， 当前节点（不是新增节点）的平衡因子变成-1
    在这里插入图片描述

    //右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* pParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (pParent == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subL;
			}
			else pParent->_right = subL;
			subL->_parent = pParent;
		}
		// 更新平衡因子
		parent->_bf = subL->_bf = 0;
	}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

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

    这样会造成parent的平衡因子变成2，当前节点（不是新增节点）的平衡因子变成1
    在这里插入图片描述

    //左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* pParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (pParent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subR;
			}
			else pParent->_right = subR;
			subR->_parent = pParent;
		}
		//更新平衡因子
		subR->_bf = parent->_bf = 0;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    3.新结点插入较高右子树的左侧（先右单旋再左单旋）

    会造成parent的平衡因子变成2， 当前节点（不是新增节点）平衡因子变成-1
    在这里插入图片描述

    void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;  //左子树60
		Node* subRL = subR->_left;// 右子树的左子树90
		int bf = subRL->_bf;// 记录SubRLd 平衡因子

		// 先以SubR为轴进行右单旋
		RotateR(parent->_right);
		// 再进行左单旋
		RotateL(parent);
		if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else assert(0);
	}


	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else assert(0);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

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

    这样会造成parent的平衡因子变成-2， 当前结点的平衡因子变成1
    在这里插入图片描述

    	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else assert(0);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    插入的整体代码

    bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;//parent是cur的父节点
	Node* cur = _root;//cur往下走
	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;//AVL树不允许有重复值
		}
	}
	//走到这里就表示找到我们要插入kv值的正确位置了,准备插入节点..........
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)//如果new的节点比父节点大，那么父节点的右指针指向new节点
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else//如果new的节点比父节点小，那么父节点的左指针指向new节点
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	//开始更新平衡因子
	while (parent)//更新到根节点才算更新完平衡因子
	{
		//1、如果是右子树新增结点，那么父节点的_bf就加一
		//2、如果是左子树新增结点，那么父节点的_bf就减一
		//+1和-1大家可以自己决定，只要是对的，怎么都行！
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}
		// 是否继续更新依据：子树的高度是否变化
		// 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1
		// 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新
		// 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了，
		// parent所在子树高度变了，继续往上更新
		// 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则
		// 就地处理--旋转

		// 旋转：
		// 1、让这颗子树左右高度不超过1
		// 2、旋转过程中继续保持他是搜索树
		// 3、更新调整孩子节点的平衡因子
		// 4、让这颗子树的高度跟插入前保持一致

		//如果新增节点cur，使得父节点parent的平衡因子变成了0，那么表示该插入节点对整棵树的平衡因子没有影响
		//不用向上判断，可以直接退出
		if (parent->_bf == 0)
		{
			break;
		}
		//如果新增cur使得父节点parent的平衡因子变成了1或者-1，那么我们要继续向上判断是否对上面的节点的
		//说明之前的平衡被打破，子树的高度变化了，有可能会造成父节点的平衡因子出现问题
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = parent->_parent;
		}
		//当平衡因子出现2 or -2 的时候就需要调整子树
		else if (parent->_bf == 2 || parent->_bf == -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;//旋转完一次就可以退出了，因为旋转的时候我们已经向上判断了，除非新插入，否则树就是avl树
		}
		else
		{
			assert(false);//这里直接报错，走到这里树就已经不是AVL树了
		}
	}
	return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
  • 相关阅读:
    【C++基础入门】42.C++中同名覆盖引发的问题
    【iOS】—— NSOperation、NSOperationQueue
    激光焊如何更准更稳？维视智造激光焊视觉解决方案助力精密制造
    完美校园打卡【云函数搭建】
    HTML:认识HTML与基本语法的学习
    【分享】集简云新功能：集简云浏览器机器人，将任意网站页面转换为API连接器
    精益求精：Android应用体积优化的终极指南
    大数据分布式计算工具Spark实战讲解(数据输入实战）
    C++关于字符串的一点注意事项
    Apache Seata如何解决TCC 模式的幂等、悬挂和空回滚问题
  • 原文地址：https://blog.csdn.net/weixin_65660590/article/details/134299708