1. AI技术聚合首页
  2. IT

【数据结构】—AVL树（C++实现）

xiaoxingxing • • IT • 阅读 45

                                                      🎬慕斯主页：修仙—别有洞天

                                                 💜本文前置知识： 搜索二叉树

                                                      ♈️今日夜电波：Letter Song—ヲタみん

                                                                1:36━━━━━━️💟──────── 5:35
                                                                    🔄   ◀️   ⏸   ▶️    ☰  

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

目录

一、前言          

        AVL树的概念

        AVL树同二叉搜索树的异同 

二、AVL树的实现

         节点的定义

         AVL树的初始化定义

         AVL树的插入（重点及难点！！！） 

         插入大致步骤

        根据规则找节点

         插入并且链接节点

         向上更新bf（平衡因子）的值

        左单旋

        右单旋

        左右双旋 

        右左双旋 

判断是否符合AVL树

三、整体代码 

一、前言          

        本文是基于二叉搜索树的知识前提下对于AVL树进行叙述的，主要叙述的方面在于AVL树的插入方面，因为AVL树同二叉搜索树的最大区别就在于插入的操作和删除操作，删除操作也是类似的，但是难就难在更新平衡因子，后续会补上。而对于其他的操作如：二叉搜索树的查找操作等等都是相似的，因此本文主要介绍AVL树的插入操作。

        AVL树的概念

         AVL树是一种自平衡二叉搜索树，它的特点是保证了每个节点的左右子树的高度差不超过1。它在插入和删除时会自动平衡，以保持树的高度始终在log N的范围内，从而保证了查找、插入、删除等操作的高效性。AVL树的名字来源于其发明者G.M.Adelson-Velsky和E.M.Landis的姓氏缩写。以下为一颗AVL树：

        AVL树同二叉搜索树的异同 

AVL树和二叉搜索树有很多相似之处，但也有许多不同之处。以下是它们的主要异同点：

相同点：

  1. 它们都是自平衡二叉搜索树，也就是说，在插入和删除节点后，它们能够保持一定的平衡性，从而保证查询操作的时间复杂度始终保持在O(logn)级别。
  2. 它们都遵循二叉搜索树的基本性质，即左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。

不同点：

  1. 在AVL树中，除了左右子树高度差不能超过1之外，每个叶子节点还必须在左右子树的高度之间，而在二叉搜索树中则没有这样的限制。（AVL中通常定义一个bf值（balance factor）用于记录节点左右子树的高度差）
  2. 在AVL树中，任何路径上的节点数差异不能超过1，而在二叉搜索树中则没有这样的要求。
  3. 在插入和删除节点后，AVL树需要进行更多的旋转操作来恢复平衡，而二叉搜索树则不需要这样的步骤。
  4. AVL树更适合于查找操作，因为它通过严格的平衡性保证了查询操作的效率，而二叉搜索树更适合于插入和删除操作，因为它可以通过简单的旋转操作来快速调整树结构。

二、AVL树的实现

         节点的定义

         通过KV模型定义AVL树节点，定义三叉链的结构储存父节点以及左右子树节点的地址，定义了bf（平衡因子）用于记录节点右子树与左子树之差（右-左），通过构造函数初始化列表，特别要将bf置为0，如果不置0后续操作可能会出错（别问作者怎么知道的(〃＞皿＜)）。

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

         AVL树的初始化定义

// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
    // 在AVL树中插入节点
	bool Insert(const pair<K, V>& kv);
    
    // AVL树的验证
    bool _IsBalance(Node* root)
    {
        return _IsBalance(_root);
    }
    
private:
    // 右单旋
	void RotateR(Node* parent);
    // 左单旋
	void RotateL(Node* parent);
    // 右左双旋
	void RotateRL(Node* parent);
    // 左右双旋
	void RotateLR(Node* parent);
    // 求高度
	int _Height(Node* root );
    // 根据AVL树的概念验证pRoot是否为有效的AVL树
    bool _IsBalance(Node* root);

private:
	Node* _root = nullptr;
};

AVL树的插入（重点及难点！！！） 

         插入大致步骤

AVL树的插入操作可以分为以下几步：

  1. 向AVL树中插入一个新节点，首先找到该节点的位置。这可以通过比较新节点的值与当前节点的值来完成，直到找到一个空位置或者到达一个叶子节点为止。按照大往左，小往右，相等返回false的规则。
  2. 依次向下搜索直到找到相应的位置，就将新节点插入到这个位置，并且更新该节点的父节点和兄弟节点的指针。就将新节点插入到这个位置，然后向上更新节点的bf值。
  3. 插入完成后，需要检查新插入的节点是否破坏了AVL树的平衡性。如果破坏了平衡性，就需要执行一系列旋转操作来修复不平衡状态。具体来说，如果新插入的节点使得某个分支的深度增加了一级，那么可以执行一次相应的旋转操作：左旋、右旋、左右旋、右左旋，最后按要求更新各个节点的bf值。

以上就是AVL树的插入操作步骤。需要注意的是，每次插入操作都需要按照这些步骤来进行，才能保证AVL树的平衡性。

        根据规则找节点

         如果_root为空（即空树）则新建节点并返回。比较节点的值，如果插入节点大则往右子树遍历，小则往左子树遍历，如果与节点值相同则无需插入直接返回。后续找到相应的位置后就可跳出循环进行下一步操作。

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;
	}
}
         插入并且链接节点

         更新节点信息，新插入节点的_parent值，以及父节点链接他在左子树还是右子树的判断，链入AVL树中。

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
         向上更新bf（平衡因子）的值

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

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

        2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可。

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

        1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功。

        2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。

        3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

while (parent)
{
	if (cur == parent->_left)//根据在左还是右改变bf值
	{
		parent->_bf--;
	}
	else
	{
		parent->_bf++;
	}

	if (parent->_bf == 0)//bf=0则向上都无需变化
	{
		break;
	}
	else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
	{
		cur = parent;
		parent = parent->_parent;
	}
	else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正
	{
		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)//右旋再左旋情况
		{
			RotateRL(parent);
		}
		else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况
		{
			RotateLR(parent);
		}

		// 1、旋转让这颗子树平衡了
		// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
		break;
	}
	else
	{
		assert(false);//其它情况的bf值表示这颗avl树本身就有问题
	}
}

         左单旋

        由于我们每次插入都会进行调整操作，对此AVL树在新的节点插入前都是合法的，也就是说bf值只会在-1~1之间波动。 当 parent->_bf == 2 && cur->_bf == 1时，我们需要进行左单旋的操作以确保AVL树的合法性（也就是当父节点的右子树高时需要进行左单旋），以下为对此以下为大致的操作图：

        详细旋转过程： 

        对于左单旋操作，我们需要先记录几个节点，分别如下为parent、subR、subRL，因为我们主要是改变这三个的位置。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。

	void RotateL(Node* parent)//左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)//判断节点subRL是否为空，防止出错
			subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

        右单旋

        对于右单旋，操作同左单旋相似，也是需要记录三个节点：parent、subL、subLR,只不过此时我们是向右旋转。当 parent->_bf == -2 && cur->_bf == -1时，我们需要进行右单旋的操作以确保AVL树的合法性（也就是当父节点的左子树高时需要进行右单旋）。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。以下为对此以下为大致的操作图：

	void RotateR(Node* parent)//右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		

		subL->_right = parent;
		
		Node* parentParent = parent->_parent;

		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf = 0;
	}

        左右双旋 

         当parent->_bf == -2 && cur->_bf == 1时，也就意味着我们的插入操作在如下的b的位置，插入后的图为第二张图，对此我们仅仅只进行一次旋转是远远不够的，如下第三张图为以30为父节点（即subL）只进行了一次左单旋后所变化的图，如果我们仔细观察可以发现这非常符合需要右单旋的操作，因此，此时我们以90为父节点再进行一次右单旋操作。 当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subLR的bf值来确定。

当bf == 0，则subLR自己就是新增因此
            parent->_bf = subL->_bf = subLR->_bf = 0;

当bf==-1，则subLR的左子树新增
           parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;

当bf==1，则subLR的右子树新增
           subL->_bf = -1;parent->_bf = 0;subLR->_bf = 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)
		{
			// subLR自己就是新增
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			// subLR的左子树新增
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// subLR的右子树新增
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

          右左双旋 

        当parent->_bf == 2 && cur->_bf == -1时，我们需要进行右左双旋操作，当然同左右双旋一样，只进行一次旋转肯定是不够的，我们也可以猜到先对subR作为一次父节点进行右单旋，在再对parent进行左单旋。

当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subRL的bf值来确定。

当bf == 0，则subRL自己就是新增
            parent->_bf = subR->_bf = subRL->_bf = 0;

当bf==-1，则subRL的左子树新增
            parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;

当bf==1，则subRL的右子树新增

            parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;

 

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

判断是否符合AVL树

        主要运用递归的思想，不多阐述，实在不明白可以画递归展开图。 

		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);

			return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
		}

		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
			}

			return abs(rightHeight - leftHeight) < 2
				&& _IsBalance(root->_left)
				&& _IsBalance(root->_right);
		}

三、整体代码 

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& 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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent)
		{
			if (cur == parent->_left)//根据在左还是右改变bf值
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)//bf=0则向上都无需变化
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正
			{
				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)//右旋再左旋情况
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况
				{
					RotateLR(parent);
				}

				// 1、旋转让这颗子树平衡了
				// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
				break;
			}
			else
			{
				assert(false);//其它情况的bf值表示这颗avl树本身就有问题
			}
		}

		return true;
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	private:

		void RotateL(Node* parent)//左旋
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

			parent->_right = subRL;
			subR->_left = parent;

			Node* parentParent = parent->_parent;

			parent->_parent = subR;
			if (subRL)//判断节点subRL是否为空，防止出错
				subRL->_parent = parent;

			if (_root == parent)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parentParent->_left == parent)//链接subR给父节点的父节点，需要判断是在左子树还是右子树
				{
					parentParent->_left = subR;
				}
				else
				{
					parentParent->_right = subR;
				}

				subR->_parent = parentParent;
			}

			parent->_bf = subR->_bf = 0;
		}


		void RotateR(Node* parent)//右旋
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;


			subL->_right = parent;

			Node* parentParent = parent->_parent;

			parent->_parent = subL;

			if (_root == parent)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				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;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;

			RotateR(parent->_right);
			RotateL(parent);

			if (bf == 0)
			{
				// subRL自己就是新增
				parent->_bf = subR->_bf = subRL->_bf = 0;
			}
			else if (bf == -1)
			{
				// subRL的左子树新增
				parent->_bf = 0;
				subRL->_bf = 0;
				subR->_bf = 1;
			}
			else if (bf == 1)
			{
				// subRL的右子树新增
				parent->_bf = -1;
				subRL->_bf = 0;
				subR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void RotateLR(Node* parent)
		{
			//...
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;

			RotateL(parent->_left);
			RotateR(parent);

			if (bf == 0)
			{
				// subLR自己就是新增
				parent->_bf = subL->_bf = subLR->_bf = 0;
			}
			else if (bf == -1)
			{
				// subLR的左子树新增
				parent->_bf = 1;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
			else if (bf == 1)
			{
				// subLR的右子树新增
				subL->_bf = -1;
				parent->_bf = 0;
				subLR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			cout << root->_kv.first << " ";
			_InOrder(root->_right);
		}

		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);

			return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
		}

		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
			}

			return abs(rightHeight - leftHeight) < 2
				&& _IsBalance(root->_left)
				&& _IsBalance(root->_right);
		}

	private:
		Node* _root = nullptr;
};

                         感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                       

                                                                         给个三连再走嘛~  

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐