【C++】AVL(平衡二叉搜索树)树的原理及实现

这篇具有很好参考价值的文章主要介绍了【C++】AVL(平衡二叉搜索树)树的原理及实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

文章目录

一、引言

二、AVL树的概念

三、AVL树的插入

3、1 AVL树的简单插入

3、2 旋转分类

 3、2、1 新节点插入较高右子树的右侧:左单旋

3、2、2 新节点插入较高左子树的左侧:右单旋

3、2、3 新节点插入较高左子树的右侧:左右双旋(先左后右)

3、2、4 新节点插入较高右子树的左侧:右左双旋(先右后左)

四、检查AVL树

4、1 高度差与平衡因子对比 

4、2 不同的测试用例进行测试

五、性能分析

4.1 查找操作的复杂度

4.2 插入操作的复杂度

六、总结


🙋‍♂️ 作者:@Ggggggtm 🙋‍♂️

👀 专栏:C++、数据结构 👀

💥 标题:AVL树💥

 ❣️ 寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景 ❣️ 

一、引言

   二叉搜索树 虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下
  因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。因此就诞生出了AVL树。
   AVL树是一种自平衡二叉搜索树,它在查找、插入和删除操作中都能保持较好的性能。它的命名来自于它的发明者,Adelson-Velsky和Landis。AVL树的特点是通过旋转操作来保持平衡,使得任何一个节点的左右子树高度差不超过1

  本文将介绍AVL树的概念、实现以及性能分析。首先,我们将解释AVL树的结构和基本概念。然后,我们将详细讨论如何实现AVL树,并提供C++语言的示例代码。最后,我们将对AVL树的性能进行分析。

二、AVL树的概念

  AVL树是一种二叉搜索树,它的每个节点包含一个关键字(键值对)、左右孩子指针和父结点指针。每个节点还包含一个平衡因子(balance factor),用于表示该节点的左右子树高度差(平衡因子=左子树高度−右子树高度。 

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

	pair<K, V> _kv; //key-value
	int _bf; //balance factor

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

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

  • 它的左右子树都是AVL树。
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构
  AVL树的平衡性规则是指任何一个节点的左右子树的高度差不超过1。即对于任意节点,其左子树高度和右子树高度的差绝对值不大于1。

三、AVL树的插入

  本篇文章重点介绍AVL树的插入操作。因为在插入操作中包含了所有重要操作。

3、1 AVL树的简单插入

  插入一个新节点到AVL树中,需要进行以下几个步骤:

  1. 执行二叉搜索树的插入操作,找到新节点应该插入的位置。
  2. 更新相关节点的平衡因子。
  3. 检查是否破坏了平衡性规则,如果破坏了,则进行相应的旋转操作来恢复平衡。

  接着,在新节点插入后,我们需要检查树的平衡性。

  1. 插入新节点后的平衡因子调整:由于插入可能导致从插入节点到根节点的路径上的某些节点的平衡被破坏,我们需要从新插入的节点开始向上遍历,更新所有受影响节点的平衡因子。
  2. 平衡调整:一旦检测到某个节点的平衡因子不在范围[-1, 1]之间,就需要对其进行平衡调整,以确保树的平衡性。根据插入节点所在的子树的情况,可以进行四种类型的旋转操作:左旋、右旋、左右旋和右左旋。
  3. 继续向上检查:在执行旋转操作后,可能会影响到更高层次的节点的平衡性。因此,我们需要继续向上检查,直到根节点为止,以确保整个树的平衡性。

  当我们找到合适位置进行插入后,将该节点进行连接,在更新其父节点及相关节点的平衡因子。如下图例子:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  假设我们在上图中的值为6的节点左孩子插入一个节点。新插入的节点的平衡因子为0。但是其父节点(值为6的节点和值为7的节点)的平衡因子都发生了变化:6的节点和值为7的节点的平衡因子分别变为-1和0。为什么呢?这就与更新平衡因子的规则有关了。

  更新平衡因子的规则:

  1. 新增在右,parent-> bf++;新增在左,parent-> bf--;
  2. 更新后,parent->bf ==1or-1,说明parent插入前的平衡因子是0,说明左右子树高度相等,插入后有一边高,parent高度变了,需要继续往上更新;
  3. 更新后,parent->bf == 0,说明parent插入前的平衡因子是1 or -1,说明左右子树一边高一边低,插入后两边一样高,插入填上了矮了那边,parent所在子树高度不变,不需要继续往上更新;
  4. 更新后,parent->bf == 2 or -2,说明parent插入前的平衡因子是1 or -1,已经平衡临界值,插入变成2 or -2,打破平衡,parent所在子树需要旋转处理。
  5. 更新后,parent->bf 大于 2 或者 小于 -2的值,不可能,如果存在,则说明插入前就不是AVL树,需要去检查之前操作的问题。

  通过对上述的理解,我们可写出如下代码:

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.second > kv.second)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent)
		{
			if (parent->_right == cur)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (abs(parent->_bf) == 1)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}
private:
	Node* _root = nullptr;
};

3、2 旋转分类

  旋转也是有其自己的规则的:

  • 旋转后需要成为平衡树;
  • 旋转不能破环搜索树的规则。

  我们先看如下图的情况:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  我们在值为9的节点右边进行插入,我们发现其父节点和祖宗节点的平衡因子都发生了变化。此时我们是需要进行旋转调节的。但是我们也可以把该节点插入到其他节点下面,然后也可能会需要进行旋转。需要旋转的情况太多,所以我们需要进行分类。

  为了保持树的平衡,AVL树可能需要执行以下四种旋转操作之一:

  • 左旋(LL旋转)
  • 右旋(RR旋转)
  • 先左后右旋(LR旋转)
  • 先右后左旋(RL旋转)

  下面我们来一一解释各种旋转的原理。

 3、2、1 新节点插入较高右子树的右侧:左单旋

  左旋是在一个节点的右子树高度大于左子树高度时进行的旋转操作。通过左旋,可以将右子树的高度降低,使得整棵树重新恢复平衡。

  左旋的依据是,右子树的高度大于左子树的高度,因此需要将右子树中的某个节点旋转到根节点的位置,使得该节点成为新的根节点,并将原来的根节点作为新根节点的左子节点。

  具体需要左旋的情况如下:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  左旋是怎么实现的呢?如下图:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  上图就是把父节点中右树的左孩子给父节点父节点连接到右树的左边。通俗解释,把subRL赋给parent->_right(parent->_right=subRL),然后再将parent连接到subR的左(subR->_left=parent)。

  我们再分析是否符合旋转的规则。首先旋转后的高度是平衡的。其次符合搜索树的规则。但是我们不仅仅要更换节点,还要更新变换的父节点和平衡因子。我们改变了parent这棵树和子树subR。所以我们还需更新他们的父节点和平衡因子。我们看左旋的代码实现:

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
        
        // 旋转
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_right = subRL;
        
        // 更新父节点 
		if (subRL)  // h=0的情况下,subRL为nullptr
			subRL->_parent = parent;
		parent->_parent = subR;

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

			subR->_parent = ppNode;
		}
        
        // 更新平衡因子
		subR->_bf = parent->_bf = 0;
	}

3、2、2 新节点插入较高左子树的左侧:右单旋

  右旋是在一个节点的左子树高度大于右子树高度时进行的旋转操作。通过右旋,可以将左子树的高度降低,使得整棵树重新恢复平衡。

  右旋的依据是,左子树的高度大于右子树的高度,因此需要将左子树中的某个节点旋转到根节点的位置,使得该节点成为新的根节点,并将原来的根节点作为新根节点的右子节点。

  右旋的情况如下如:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  我们再根据下图具体分析一下:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  右旋与左旋转很类似,我们都需要借助 parent 来维护该树的平衡。首先是要把subLR子树移动到parent的左树上。然后,再把parent移动到subL的右树上。操作完这两部后,树就平衡了。 我们可结合下图理解:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

   不要忘记旋转后,要更新所变动节点的父节点和平衡因子,我们看代码:

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

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

		subLR->_bf = 0;
		if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}

3、2、3 新节点插入较高左子树的右侧:左右双旋(先左后右)

  左右旋是在一个节点的左子树的右子树高度大于左子树高度时进行的旋转操作。左右旋可以通过先进行一次左旋,再进行一次右旋来实现树的平衡。

  左右旋的依据是,左子树的右子树高度大于左子树的高度,导致左子树整体比右子树要高。为了保持树的平衡,需要对左子树进行左旋,然后再对原父节点进行右旋。 

  我们已经讲述了如下两种情况:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

   那下种情况该怎么旋转呢?我们不妨先自己想一下看看怎么旋转。

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  由于旋转的原因,我们还需再次展开子树b。上述情况又分为如下三种情况:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  上述三种情况只不过是更新平衡因子有所不同,旋转的方法还是相同的。都是先对值为30的子树进行左单旋,然后再对值为90的子树进行右单旋,旋转完成后再 考虑平衡因子的更新。整体的需安装过程如下:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  我们可以再结合着代码理解一下:

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

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

		subLR->_bf = 0;
		if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}

3、2、4 新节点插入较高右子树的左侧:右左双旋(先右后左)

  右左双旋与左右双旋大同小异,只不过是在不同的情况下进行了不同顺序的旋转。旋转的思路和情况分类是一模一样的。我们先看一下需要右左双旋的情况:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  同样可按照旋转的需求,划分三种情况(与左右双旋类似)。这里就不在具体画出。具体的旋转过程如下:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  再对不同情况下的平衡因子进行更新,代码如下:

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

		int bf = subRL->_bf;

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

		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

四、检查AVL树

  当我们自己完成AVL树代码后,我们还需要检查一下是否正确。通过什么方式检查呢? 

4、1 高度差与平衡因子对比 

  我们首先想到的是通过中序遍历打印出来,看其是否是有序的。这样就算验证完成了吗?并不是!!!

  我们不仅仅要验证是否为搜索树,话要看其是否为平衡树。但是验证是否是平衡树时,又该怎么检查是否平衡呢?可不可以通过遍历整棵树,看其平衡因子绝对值是否小于等于1呢?怎么就感觉好像又可以,好像又不太行呢?平衡因子是我们自己更新的,还需要我们自己去检查吗?当然不用!!!我们需要求出该子树的高度差与平衡因子比较看是否相同,这样检验才是比较合理的。

  有了上述的思路,我们在看代码是怎么实现的,代码如下:

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

	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

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

		int leftHigh = TreeHeight(root->_left);
		int rightHigh = TreeHeight(root->_right);
		int subHigh = rightHigh - leftHigh;
		if (root->_bf != subHigh)
		{
			cout << "平衡因子有误:" << root->_kv.first << endl;
			return false;
		}


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

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

		return max(TreeHeight(root->_left), TreeHeight(root->_right)) + 1;
	}

4、2 不同的测试用例进行测试

  我们先来看一段特殊的测试代码:

void TestAVLTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	t1.InOrder();
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

   先看一下屏蔽掉右左双旋更新平衡因子代码的结果,输出结果如下:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  结果是有序的,但是平衡因子是有问题的!我们再把这段代码放开再看其输出结果:

【C++】AVL(平衡二叉搜索树)树的原理及实现,C++,数据结构,算法,c++,开发语言,数据结构

  只有一组数据并不能很好的说明问题,我们再随机生成数据进行多次测试,代码如下:

void TestAVLTree2()
{
	size_t N = 10000;
	srand(time(0));
	AVLTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		int x = rand();
		t1.Insert(make_pair(x, i));

	} 
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

五、性能分析

4.1 查找操作的复杂度

  AVL树的查找操作与普通的二叉搜索树相同,都是按照比较大小的规则在树中查找特定的元素。由于AVL树是平衡二叉搜索树,它保持了左右子树高度的平衡,因此查找操作的平均时间复杂度为O(log n),其中n是树中节点的数量

  在平衡状态下,每一层的节点数大约是前一层的两倍,这保证了树的高度始终保持在logarithmic级别。这种高度平衡的特性使得查找操作的时间复杂度始终保持在O(log n)的范围内,使得AVL树在大量数据的情况下依然能够快速有效地进行查找。

  总的来说,AVL树的查找操作性能非常出色,是其设计的主要优势之一。

4.2 插入操作的复杂度

  在AVL树中进行插入操作时,需要首先执行标准的二叉搜索树的插入操作,将新节点插入到合适的位置。然后,需要进行平衡调整,以确保插入操作不会破坏树的平衡性。

  插入操作的时间复杂度包括两个部分:插入节点的时间复杂度和平衡调整的时间复杂度。插入节点的时间复杂度是O(log n),其中n是树中节点的数量,这是因为AVL树保持了树的高度平衡,使得每一层的节点数大约是前一层的两倍。

  平衡调整的时间复杂度取决于进行的旋转操作次数。最坏情况下,插入一个节点可能需要执行O(log n)次旋转操作,但平均情况下,插入节点的时间复杂度仍然是O(log n)。这是因为在绝大多数情况下,只需要进行少数次旋转操作即可将树恢复平衡。

  总体来说,AVL树的插入操作的平均时间复杂度是O(log n),使得在插入新元素时仍然能够保持高效的性能。

六、总结

  AVL树是一种自平衡的二叉搜索树,其平衡性质使得在查找、插入和删除操作上都能保持较高的性能。通过限制树的平衡因子在一定范围内,AVL树能够在任何时刻保持树的高度平衡,从而避免了退化成链表的情况。

  在AVL树的操作中,插入和删除操作可能会导致树的平衡性被破坏,因此需要进行相应的平衡调整操作,包括左旋、右旋、左右旋和右左旋等。这些操作能够使树保持平衡,继续提供高效的性能。

  AVL树的性能分析表明,查找、插入和删除操作的平均时间复杂度均为O(log n),其中n为树中节点的数量。虽然平衡调整可能会增加一些开销,但总体上AVL树仍然能够保持高效的操作性能。文章来源地址https://www.toymoban.com/news/detail-636120.html

到了这里,关于【C++】AVL(平衡二叉搜索树)树的原理及实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++庖丁解牛】自平衡二叉搜索树--AVL树

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都

    2024年04月09日
    浏览(95)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(47)
  • 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)

    前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是: 其底层都是按照 二叉搜索树 来实现的。 但是二叉搜索树有其自身的缺陷,假如 往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) ,

    2024年02月06日
    浏览(43)
  • 数据结构——常见二叉树的分类(完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树)

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(41)
  • 【C++】二叉搜索树的原理及实现

      二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。    文章目录 简介 一、二叉搜索树的概念 二、二叉搜索树的操作及实现 2、1 二叉搜索树的插入 2、1、1 插入的原理 2、1、2

    2024年02月14日
    浏览(47)
  • AVL树(平衡二叉搜索树)

    如果BST树插入的顺序是有序的,那么BST树就会退化成一个双链表结构,查询的速率就会很慢, 所以有了AVL树的意义。 AVL 树的定义: 是具有下列性质的二叉搜索树         1、它的左子树和右子树都是AVL树         2、左子树和右子树的高度之差的绝对值不超过1 结点的平衡因

    2024年02月05日
    浏览(29)
  • 【平衡二叉搜索树(AVL)-- 旋转】

    打怪升级:第60天 AVLTree,也就是我们所说的:自平衡二叉搜索树,AVL命名由来是两位发明者的名字的首字母,并无其他含义。 AVL树有两个重要的特点: AVL树是一棵搜索树; AVL树左右子树的高度差的绝对值不大于1; AVL树的左右子树也是AVL树。 高度差可取0,1,-1。 注:我们将

    2024年02月02日
    浏览(29)
  • 【高阶数据结构】AVL树 {概念及实现;节点的定义;插入并调整平衡因子;旋转操作:左单旋,右单旋,左右双旋,右左双旋;AVL树的验证及性能分析}

    二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: AVL树:又被称为高度平衡搜索二叉树,

    2024年02月10日
    浏览(46)
  • [数据结构 C++] AVL树的模拟实现

    问题引入: 在上一篇文章中,我们提到了二叉搜索树在插入时,可能会形成单边树,会降低二叉搜索的性能。因此我们需要平衡二叉搜索树,降低二叉搜索树的高度,使得二叉搜索树趋于一颗完全二叉树的样子,这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡

    2024年02月03日
    浏览(52)
  • 数据结构课设(五)二叉排序树与平衡二叉树的实现

    假定二叉排序树与平题所处理数据均为整型。分别采用二叉链表和顺序表作存储结构,实现对二叉衡二叉树的操作。具体要求如下: (1)用二叉链表作存储结构: ①读入一个整数序列L(要求该整数序列从磁盘文件读取),生成一棵二叉排序树②对二叉排序树T作中序遍历,输出结果

    2024年02月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包