• C++_AVL树

    AVL树

    AVL树

    AVL树概念

    如果是以有序或接近有序的顺序建二叉搜索树，会导致二叉搜索树退化单枝树，相当于在顺序表中查找，效率低下。

    因此，引入了AVL树**（当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整) ）**，使二叉树左右均衡，具有较高的查找效率。

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

    • 它的左右子树都是AVL树

    • 左右子树高度之差（平衡因子）的绝对值不超过1（-1/0/1）

      image-20220815151800122

      如果一颗二叉搜索树是平衡的，就是AVL树，如果有n个结点，其高度可保持在log n,时间复杂度在O（log n)

    AVL树节点的定义

    template<class K,class V>
struct AVLTree_Node
{
	pair<K, V> _data;			//该节点存储的数据
    
	AVLTree_Node<K,V>* _left;	//该节点的左孩子
	AVLTree_Node<K,V>* _right;	//该节点的右孩子
	AVLTree_Node<K,V>* _parent;	//该节点的双亲节点
	int _rf;					//该节点的平衡因子（右子树的高度-左子树的高度）

	AVLTree_Node(const pair<K,V>& data)	//构造函数
		:_data(data)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_rf(0)
	{}
};

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

    AVL树的插入

    AVL树在普通二叉搜索树的基础上引入了平衡因子，因此AVL树也是二叉搜索树，那么AVL树的插入过程分为两步：

    1. 按照二叉搜索树的规则插入新节点

    2. 调整节点的平衡因子

    bool Insert(const pair<K,V>& x)		
	{
		if (_root == nullptr)
		{
			_root = new Node(x);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data.first < x.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data.first > x.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;		//AVL树会去重，如果在AVL树已存在与新插入节点K相等的节点，插入失败
			}
		}
		cur = new Node(x);
		if (parent->_data.first < x.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
    	cur->_parent = parent;
    	/cur是新插入的节点，parent是cur的双亲节点，
    	/在插入之后，cur的平衡因子一定为0，parent的平衡因子有五种可能，可能为0，-1，1，-2，2
    	/在插入之前，parent的平衡因子可能是0/-1/1（因为在插入一个新节点前，这已经是一个AVL树）
    	/在插入之后，parent的平衡因子可能为0（之前可能为-1/1），-1（之前为0），1（之前为				0），-2（之前为-1），2（之前为1）
    	/如果插入后平衡因子为0，那么以parent为根节点的子树高度没有改变，那就不会影响parent以上的		节点的平衡因子
    	/如果插入后平衡因子为1/-1,那么以parent为根节点的子树高度发生了改变，就会影响parent以上的		  节点的平衡因子，就需要一层一层向上更新，直到某个节点的平衡因子更新为0/-2/2
    	/如果插入后平衡因子为-2/2,那么就需要对parent为根节点的子树进行处理
    
		while (parent)			//循环是为了向上更新
		{
			if (parent->_right == cur)			//更新parent的平衡因子
			{
				parent->_rf++;
			}
			else
			{
				parent->_rf--;
			}
			if (parent->_rf == 0) 				//更新后，parent的平衡因子为0，插入结束													（1、不需要向上更新，满足AVL树规则）
			{
				break;
			}
			else if (parent->_rf == -1 || parent->_rf == 1) 
            /更新后，parent的平衡因子为-1/1,需要向上更新
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_rf == -2 || parent->_rf == 2)
           	/更新后，parent的平衡因子为-2/2，违反AVL树规则，需要处理（旋转），旋转之后parent的			平衡因子为0（高度没有变化，不影响parent以上的节点），平衡因子符合规则，插入结束
           	/如果插入之前是h+2，插入节点，旋转之后，高度还是h+2
			{
				if (parent->_rf == 2 && cur->_rf == 1)//左单旋
				{
					RotateL(parent);
				}
				else if (parent->_rf == 2 && cur->_rf == -1)//cur右旋，parent左旋
				{
					RotateRL(parent);
				}
				else if (parent->_rf == -2 && cur->_rf == -1)//右单旋
				{
					RotateR(parent);
				}
				else if (parent->_rf == 2 && cur->_rf == 1)//cur左旋，parent右旋
				{
					RotateLR(parent);
				}
				break;
			}
			else
				assert(false);
		}
		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

    AVL树的旋转

    AVL树公有四种旋转（如果节点插入之前树的高度是h+2，插入，旋转之后，高度还是h+2）

    1. 右单旋

      image-20220815195508345

      在30节点的左子树插入新节点，左边高，60树右旋

      void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* ppnode = parent->_parent;
	parent->_left = subLR;
	if (subLR)
    {
		subLR->_parent = parent;
	}
	subL->_right = parent;
	parent->_parent = subL;
	if (_root == parent)
	{
		_root = subL;
		_root -> _parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
        {
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	subL->_rf = parent->_rf = 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. 左单旋

      image-20220815192807036

      在60节点右子树插入一个节点，右边高，30树左旋

      void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* ppnode = parent->_parent;
	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	parent->_parent = subR;
	if (_root == parent)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	subR->_rf = parent->_rf = 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

    3. 左右单旋（h为0时，60节点是新插入的）

      image-20220815211821927

      在30节点的右子树插入节点，90树的平衡因子违反规则，对于30节点右边高，对于90的节点左边高，所以需要先将30子树左旋，再将90树右旋

      void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	RotateL(subL);
	RotateR(parent);
	if (subLR->_rf == 1)
	{
		subL->_rf = -1;
		subLR->_rf = 0;
		parent->_rf = 0;
	}
	else if (subLR->_rf == -1)
	{
		subL->_rf = 0;
		parent->_rf = 1;
		subLR->_rf = 0;
	}
	else if (subLR->_rf == 0)	//h为0，subLR为插入结点
	{
		subL->_rf = 0;
		parent->_rf = 0;
		subLR->_rf = 0;
	}
	else
	{
		assert(false);
	}
}

      • 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

    4. 右左单旋（h为0时，60是新插入的）

      image-20220815212021417

      在90节点左子树插入新节点，30树的平衡因子违反规则，对于90节点左边高，对于30节点右边高，所以先把90树右旋，再把30树左旋

      void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	RotateR(subR);
	RotateL(parent);
	if (subRL->_rf == 1)
	{
		subR->_rf = 0;
		subRL->_rf = 0;
		parent->_rf = -1;
	}
	else if (subRL->_rf == -1)
	{
		subR->_rf = 1;
		parent->_rf = 0;
		subRL->_rf = 0;
	}
	else if (subRL->_rf == 0)
	{
		subR->_rf = 0;
		parent->_rf = 0;
		subRL->_rf = 0;
	}
	else
	{
		assert(false);
	}
}

      • 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

      为什么抽象图是这么画的？

      因为只有这样画，才有可能使当前整个数是需要处理的

    AVL树的验证

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

    1. 验证其为二叉搜索树

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

    2. 验证其为平衡树

      • 每个节点子树高度差的绝对值不超过1
      • 节点的平衡因子是否计算正确
      bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树
	if (nullptr == root)
		return true;

	// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
	int leftHeight = _Height(root->_left);		//_Height计算高度
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;

	// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
	// pRoot平衡因子的绝对值超过1，则一定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_data.first << "节点平衡因子异常" << endl;
		return false;
	}

	if (diff != root->_rf)
	{
		cout << root->_data.first << "节点平衡因子不符合实际" << endl;
		return false;
	}

	// pRoot的左和右如果都是AVL树，则该树一定是AVL树
	return _IsBalanceTree(root->_left)&& _IsBalanceTree(root->_right);
}

      • 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

    AVL树的性能

    • AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O（log n）。但是如果要对AVL树做一些结构修改的操作，性能非常低下。
  • 相关阅读:
    LeetCode 891. 子序列宽度之和
    【游戏编程扯淡精粹】UE5 蓝图
    146.LRU缓存
    2.1 初识Windows程序
    【ELK】日志分析系统概述及部署
    VBA 输出到CMD控制台显示暨更新当前行显示
    怎么样创建私服 nexus --- maven配置文件的各个标签的作用是什么
    Docker下搭建Redis分片集群
    1036 Boys vs Girls
    Python自动化测试selenium指定截图文件名方法
  • 原文地址：https://blog.csdn.net/weixin_53230235/article/details/126436522