扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++数据结构AVL树全面分析
  • 220

0
分享到

C++数据结构AVL树全面分析

2024-04-02 19:04:59 220人浏览 八月长安
摘要

目录?概念?AVL树的实现?AVL树的节点定义?AVL树的插入?方法概述?平衡因子的调节?插入代码实现?AVL树的查找?AVL树的删除?方法概述?平衡因子的调节?删除代码如下?AVL

⭐️博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code

?概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

  • 它的左右子树都是AVL树
  • 左右子树高度之差的绝对值（也叫平衡因子）不超过1
  • 我规定：平衡因子（balance factor）= 右子树高度 - 左子树高度（后面这样实现）

?AVL树的实现

?AVL树的节点定义

这里节点是一个三叉链，里面存放了元素的数据和该节点此时的平衡因子。不管今后我们进行什么操作，都要维持这里的平衡因子的绝对值不超过1。


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树的插入

?方法概述

第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点（这一步很简单，上一篇博客介绍过）

第二步： 更新平衡因子，更新平衡因子的过程是一个难点，下面我给大家分析一下整个过程

?平衡因子的调节

?正常情况

实际上，我们应该能够发现，插入一个节点后，它之后影响它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一个分析过程：

第一步： 判断父亲节点是否存在，不存在直接结束，如果存在，且插入节点是它的左孩子，那么父亲节点的平衡因子就减1，如果是父亲的右，父亲的平衡因子就加1。然后对父亲节点的平衡因子进行检索。

第二步： 继续对父亲节点的平衡因子进行检索，平衡因子会有一下三种情况

第一种情况： 此时父亲的平衡因子为0，则说明插入前父亲的平衡因子为1或-1，缺少左节点或右节点插入后，插入的节点已经补齐了左节点或右节点，整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

第二种情况 此时父亲节点的平衡因子为-1或1，则说明插入前父亲的平衡因子为0，插入后增加了一个左节点或右节点，整体高度增加1，对上层有影响，继续迭代更新祖先的平衡因子。下面是一个演示图：

第三种情况： 此时父亲节点的平衡因子为-2或2，则说明插入前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，插入后增加了一个左节点或右节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

?旋转处理（出现了不平衡子树）

旋转有四种情况：

1.左单旋（新插入的节点在右子树的右侧）

具体步骤： 让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0.

先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）：

再画一个抽像图来演示：

代码实现如下：


// 左单旋 bf为2  右边高，把上面的压下来放到左边
void RotateL(Node* parent)
{		
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	// 1.先让把subR的左边（可能为空也可能不为空）作为parent的右边
	parent->_right = subRL;
	// 2.如果subRL不为空，就让subRL的父指针指向parent
	if (subRL) subRL->_parent = parent;
	// 3.先记录parent的父节点的位置，然后把parent作为subR的左边 
	Node* ppNode = parent->_parent;
	subR->_left = parent;
	// 4.parent的父指针指向subR
	parent->_parent = subR;

	// 5.如果ppNode为空==>说明subR现在是根节点，就让subR的父指针指向nullptr
	//   不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR
	if (ppNode == nullptr)
	{
		// 更新根节点
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		// 判断parent是ppNode的左还是右
		if (ppNode->_left == parent)
			ppNode->_left = subR;
		else
			ppNode->_right = subR;

		subR->_parent = ppNode;
	}

	// 6.把parent和subR的平衡因子更新为0
	subR->_bf = parent->_bf = 0;
}

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

具体步骤： 让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0.

先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）：

在给大家演示一下抽象图：

代码实现如下：


// 右单旋 bf为-2  左边高，把上面的压下来放到右边
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 1.先让把subL的右边（可能为空也可能不为空）作为parent的左边
	parent->_left = subLR;
	// 2.如果subLR不为空，就让subLR的父指针指向parent
	if (subLR) subLR->_parent = parent;
	// 3.先记录parent的父节点的位置，然后把parent作为subL的右边
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	// 4.parent的父指针指向subL
	parent->_parent = subL;

	// 5.如果ppNode为空==>说明subR现在是根节点，就让subL的父指针指向nullptr
	//   不是根节点就把subL的父指针指向parent的父节点，parent的父节点（左或右）指向subL
	if (ppNode == nullptr)
	{
		// 更新根节点
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		// 判断parent是ppNode的左还是右
		if (ppNode->_left == parent)
			ppNode->_left = subL;
		else
			ppNode->_right = subL;

		subL->_parent = ppNode;
	}

	// 6.把parent和subL的平衡因子更新为0
	subL->_bf = parent->_bf = 0;
}

3.右左双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

具体步骤 先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子，有三种改法。

三个节点从左至右的三个节点一次是：parent、subRL和subR。

如果subRL的平衡因子为0，就将它们依次改为0，0, 0；

如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；

如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。

先看具像图：

再看一个抽象图（两种情况）：

subRL的bf为1

subRL的bf为-1

代码实现如下：


// 右左旋转==>parent->_bf==2&&cur->_bf==-1
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树

	// 旋转 先对subR进行右旋转，再对parent进行左旋转
	RotateR(subR);
	RotateL(parent);

	// 从左到右 parent subRL subR
	if (bf == -1)// subRL的左子树  bf: 0 0 1
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)// subRL的右子树 bf: -1 0 0
	{
		parent->_bf = -1;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
}

4.左右双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

具体步骤先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：subL、subLR和parent。（和上面的类似，这样有助于我们记住平衡因子的调整，同时我们也可以画简图理解记忆）

如果subLR的平衡因子为0，就将它们依次改为0，0, 0；

如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；

如果subLR的平衡因子为-1，就将它们依次改为0，0, 1。

先看具像图：

再看一个抽象图（也有两种情况）：

subLR的bf为-1

subLR的bf为1

代码实现如下：


// 左右旋转==>parent->_bf==-2&&cur->_bf==1
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树

	// 旋转 先对subL进行左旋转，再对parent进行右旋转
	RotateL(subL);
	RotateR(parent);

	// 从左到右 subL subLR parent
	if (bf == -1)// subLR的左子树  bf: 0 0 1
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)// subLR的右子树 bf: -1 0 0
	{
		subL->_bf = -1;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
}

?插入代码实现

插入的步骤也就是如上面说的一样，下面的代码我们通过迭代实现。

代码实现如下：


bool Insert(const pair<K, V>& kv)
{
	// 先按照二叉搜索数一样插入元素

	// 无节点是插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	// 有节点时插入
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		parent = cur;
		// 小于往左走
		if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
		}
		// 大于往右走
		else if (kv.first > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			// 找到了，就返回false
			return false;
		}
	}

	cur = new Node(kv);
	// 判断cur应该插在parent的左还是右 
	// 小于在左，大于在右		
	if (cur->_kv.first < parent->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	// 更新parent的平衡因子
	
	// 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况）
	while (parent)
	{
		// 更新parent的平衡因子
		// cur在parent的左，parent->_bf--
		// cur在parent的右，parent->_bf++
		if (cur == parent->_left)
			parent->_bf--;
		else
			parent->_bf++;
		// bf 可能为 -2、-1、0、1、2
		// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在补齐了左节点或右节点，bf==0，对上层无影响
		// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在增加了一个左节点或有节点，bf==-1 || bf==1,对上层有影响
		// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就是一边
		// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整
		if (parent->_bf == 0)
		{
			// 对上层无影响，退出
			break;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			// 对上层有影响，迭代更新
			cur = parent;
			parent = parent->_parent;
		}
		else
		{
			// 平衡树出现了问题，需要调整
			// 1.右边高，左旋转调整
			if (parent->_bf == 2)
			{
				// 如果是一条直线==>左旋转即可
				// 如果是一条折线==>右左旋转
				if (cur->_bf == 1)
					RotateL(parent);
				else if (cur->_bf == -1)
					RotateRL(parent);

			}
			// 2.左边高，右旋转调整
			else if (parent->_bf == -2)
			{
				// 如果是一条直线==>右旋转即可
				// 如果是一条折线==>左右旋转
				if (cur->_bf == -1)
					RotateR(parent);
				else if (cur->_bf == 1)
					RotateLR(parent);
			}

			// 调整后是平衡树，bf为0，不需要调整了
			break;
		}
	}

	return bool;
}

?AVL树的查找

查找的代码和二叉搜索树是一样的，这里就不过多介绍。

代码实现如下：


bool Find(const K& key)
{
	if (_root == nullptr)
		return false;

	Node* cur = _root;
	while (cur)
	{
		// 小于往左走
		if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		// 大于往右走
		else if (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			// 找到了
			return true;
		}
	}

	return false;
}

?AVL树的删除

?方法概述

第一步： 我们先按照二叉搜索树树删除节点的方式，删除节点（这一步很简单，上一篇博客介绍过）

第二步： 然后根据对应删除情况更新平衡因子，这里更新平衡因子的方法与插入的更新方法是相反的，下面我给大家分析一下整个过程

?平衡因子的调节

?正常情况

删除节点后，如果删除的节点为根节点，就结束。否则根据删除节点为父节点的左右调整父节点的平衡因子。如果删除节点是父节点的左孩子，那么父亲节点的平衡因子加1，否则减1。然后对父亲节点进行检索。

有以下几种情况：

第一种情况： 此时父亲的平衡因子为0，则说明删除前父亲的平衡因子为1或-1，多出一个左节点或右节点，删除节点后，左右高度相等，整体高度减1，对上层有影响，需要继续调节。下面是一个演示图：（如果此时3为根节点，那么也可以结束）

第二种情况： 此时父亲的平衡因子为-1或1，则说明删除前父亲的平衡因子为0，左右高度相等，删除节点后，少了一个左节点或右节点，但是整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

第三种情况： 此时父亲节点的平衡因子为-2或2，则说明删除前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，删除了一个右节点或左节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

?需要旋转处理的几种情况

这里我只分析右边高的情况，左边高和它对称的，操作是相同的。

情况一：

操作方法： 对parent进行左旋转，因为subR的平衡因子为0，需要继续检索，然后继续迭代，把cur迭代sub的位置，parent到cur的父亲的位置

具像图：

抽象图：

情况二：

操作方法： 对parent进行左旋，然后修改平衡因子，把subR的平衡因子改为-1，parent的平衡因子改为1，因为subR的平衡因子为-1，所以无需迭代，直接结束

具像图：

抽象图：

情况三：

操作方法： 对subR进行右旋，然后对parent进行左旋，此时subR的平衡因子为0，需迭代

具像图：

抽象图：

?删除代码如下

删除代码如下：


bool Erase(const K& key)
{
	if (_root == nullptr)
		return false;

	// 有节点时插入
	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)
	{
		// 小于往左走
		if (key < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		// 大于往右走
		else if (key > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 找到了
			// 1.左边为空，把parent指向cur的右
			// 2.右边为空，把parent指向cur的左
			// 3.左右都不为空，用右子树的最左边的节点（最小节点）的值替换要删除的节点，然后转换为用1的情况删除该节点
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
					delete cur;
					break;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
						parent->_bf++;
					}
					else
					{
						parent->_right = cur->_right;
						parent->_bf--;
					}

				}

				if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
					delete cur;
					break;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
						parent->_bf++;
					}
					else
					{
						parent->_right = cur->_left;
						parent->_bf--;
					}
				}

				if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
				delete cur;
			}
			else
			{
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;// 先去右子树
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;// 一种往左走
				}

				cur->_kv = rightMin->_kv;

				// 替代删除
				// 删除minNode  第一种情况：左节点为空
				if (rightMinParent->_left == rightMin)
				{
					rightMinParent->_left = rightMin->_right;
					rightMinParent->_bf++;
				}
				else
				{
					rightMinParent->_right = rightMin->_right;
					rightMinParent->_bf--;
				}

				if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1) AfterEraseUpdateBf(rightMinParent);
				delete rightMin;
			}
			return true;
		}
	}
	return false;
}
void AfterEraseUpdateBf(Node* parent)
{
	if (parent == nullptr)
		return;
	
	Node* cur = parent;
	Goto first;

	while (parent)
	{
		// 更新parent的平衡因子
		// cur在parent的左，parent->_bf++
		// cur在parent的右，parent->_bf--
		if (cur == parent->_left)
			parent->_bf++;
		else
			parent->_bf--;
		// bf 可能为 -2、-1、0、1、2
		// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在删掉了左节点或右节点，整体高度变了，对上层有影响
		// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在删掉了一个左节点或有节点，整体高度不变，对上层无影响
		// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就另一边
		// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整
	first:
		if (parent->_bf == 0)
		{
			// 对上层有影响，迭代更新
			// 如果parent是根节点就结束
			if (parent->_parent == nullptr)
				break;
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			// 对上层无影响，退出
			break;
		}
		else
		{
			// 平衡树出现了问题，需要调整
			// 1.右边高，左旋转调整
			if (parent->_bf == 2)
			{
				// 如果是一条直线==>左旋转即可
				// 如果是一条折线==>右左旋转
				if (parent->_right->_bf == 1)
				{
					RotateL(parent);
					cur = parent->_parent;
					parent = cur->_parent;
					continue;
				}
				else if (parent->_right->_bf == -1)// 调整后 p sL s  如果sL是1或-1可以退出 
				{
					Node* s = parent->_right;
					Node* sL = s->_left;
					RotateRL(parent);
					// 不平衡向上调整  注意：bug1（以为调整完就是1或-1了，其实这里不是，画图思考一下）
					//if (sL->_bf != 1 && sL->_bf != -1)
					{
						cur = sL;
						parent = cur->_parent;
						continue;
					}
				}
				else if (parent->_right->_bf == 0)// 旋转后平衡因子要修改，画图感受 parent: 1 parent->_parent:- 1
				{
					RotateL(parent);
					parent->_bf = 1;
					parent->_parent->_bf = -1;
				}

			}
			// 2.左边高，右旋转调整
			else if (parent->_bf == -2)
			{
				// 如果是一条直线==>右旋转即可
				// 如果是一条折线==>左右旋转
				if (parent->_left->_bf == -1)
				{
					RotateR(parent);
					cur = parent->_parent;// bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图
					parent = cur->_parent;
					continue;//parent不是-1或1就继续
				}
				else if (parent->_left->_bf == 1)// 调整后 s sR p  如果sL是1或-1可以退出
				{
					Node* s = parent->_left;
					Node* sR = s->_right;
					RotateLR(parent);
					// 不平衡向上调整 为0时如果parent为根
					//if (sR->_bf != 1 && sR->_bf != -1)
					{
						cur = sR;
						parent = cur->_parent;
						continue;
					}
				}
				else if (parent->_left->_bf == 0)// 平衡因子要修改，画图感受 parent->_parent: 1 parent: -1 
				{
					RotateR(parent);
					parent->_parent->_bf = 1;
					parent->_bf = -1;
				}
			}

			// 调整后是平衡树，bf为1或-1，不需要调整了
			break;
		}
	}
}

?AVL树的测试代码

下面是验证是否为AVL树的代码：


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

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

	return 1 + max(leftHeight, rightHeight);
}
bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
		return true;
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

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

实例演示：


void TestAVLTree1()
{
	AVLTree<int, int> at;
	srand((size_t)time(nullptr));
	// int a[] = { 4,3,5,3,1,2,7 };
	// int a[] = { 1,2,3,4,5,6,7,8,9 };
	// int a[] = { 2,4,6,3,5,1,9,10,8,7 };
	// int a[] = { 4,2,3,5 };
	// int a[] = { 16,3,7,11,9,26,18,14,15 };
	// int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	// int* a = new int[10000];
	
	vector<int> a;
	for (size_t i = 0; i < 13; ++i)
	{
		// a.push_back(rand());
		a.push_back(13);
	}
	for (auto e : a)
	{
		int begin = clock();
		pair<AVLTreeNode<int, int>*, bool> ret = at.Insert(make_pair(e, e));
		int end = clock();
		// cout << ret.first->_kv.second << endl;
		// cout << ret.first->_kv.second << ":" << ret.second << endl;
		
		cout << "插入 " << e << " 后变化 --> Height: " << at.Height() << " 是否为AVLTree：" << at.IsBalanceTree();
		cout << " 用时: " << end - begin << "ms" << endl;

	}

	cout << "------------------------------------------------------" << endl;
	// at.InOrder();
	for (auto e : a)
	{
		if (e == 11478)
		{
			int a = 0;
		}
		int begin = clock();
		at.Erase(e);
		int end = clock();

		cout << "删除 " << e << " 后变化 --> Height: " << at.Height() << " 是否为AVLTree：" << at.IsBalanceTree();
		cout << " 用时: " << end - begin << "ms" << endl;
	}

	at.InOrder();
}

代码运行结果如下：

?总结

AVL树的全部内容就介绍到这，图画了一下午，创造不易，感谢支持，下一篇博客更新红黑树的相关内容，喜欢的话，欢迎点赞支持~

到此这篇关于c++数据结构AVL树全面分析的文章就介绍到这了,更多相关C++ AVL树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C++数据结构AVL树全面分析

本文链接: https://lsjlt.com/news/155864.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++数据结构AVL树全面分析
    目录概念AVL树的实现AVL树的节点定义AVL树的插入方法概述平衡因子的调节插入代码实现AVL树的查找AVL树的删除方法概述平衡因子的调节删除代码如下AVL树的测试代码总结⭐️博客代...
    99+
    2024-04-02
  • C++数据结构红黑树全面分析
    目录概念和性质红黑树的实现红黑树节点定义红黑树结构定义红黑树的插入方法概述调整节点颜色插入代码实现红黑树的删除方法概述调整颜色删除代码实现红黑树的查找红黑树的验证AVL树和红黑树的比...
    99+
    2024-04-02
  • Java数据结构之AVL树实例分析
    这篇文章主要介绍“Java数据结构之AVL树实例分析”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“Java数据结构之AVL树实例分析”文章能帮助大家解决问题。AVL树的引入搜索二叉树有着极高的搜索效...
    99+
    2023-06-30
  • C++数据结构之AVL树的实现
    目录1.概念(1)二叉搜索树的缺点(2)定义节点2.插入(1)拆分(2)找节点与插节点(3)更新平衡因子与旋转3.判断4.完整代码及测试代码完整代码测试代码1.概念 (1)二叉搜索树...
    99+
    2024-04-02
  • C++数据结构之AVL树如何实现
    这篇文章主要讲解了“C++数据结构之AVL树如何实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++数据结构之AVL树如何实现”吧！1.概念(1)二叉搜索树的缺点要手撕AVL树，我们首先...
    99+
    2023-07-02
  • Android数据结构全面总结分析
    前言 这次算一个总结，我们平时都会用到各种各样的数据结构，但是可能从未看过它们内部是如何去实现的。只有了解了它们内部大概的一个实现原理，才能在不同的场景中能选出最适合这个场景的数据结...
    99+
    2022-12-08
    Android 数据结构 Android 数据结构总结分析
  • AndroidMap数据结构全面总结分析
    目录前言MapArrayMapTreeMapHashMap总结前言 上一篇讲了Collection、Queue和Deque、List或Set，没看的朋友可以去简单看看，这一篇主要讲和...
    99+
    2022-12-08
    Android Map数据结构 Android Map
  • C++数据结构红黑树的示例分析
    这篇文章给大家分享的是有关C++数据结构红黑树的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。概念和性质红黑树的概念： 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或...
    99+
    2023-06-29
  • AVL树数据结构输入与输出怎么实现
    本篇内容介绍了“AVL树数据结构输入与输出怎么实现”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！AVL树(平衡二叉树)：AVL树本质上是一颗...
    99+
    2023-06-30
  • Java 数据结构篇-实现 AVL 树的核心方法
    🔥博客主页： 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍  文章目录         1.0 AVL 树的说明         2.0 AVL 树的成员变量及其构造方法         ...
    99+
    2024-01-21
    数据结构 算法 java
  • Python数据结构之树的全面解读
    目录前言🧡基本概念🌳树的定义🌲基本术语💚树的逻辑结构🍉前序遍历🍓后序遍历㇮...
    99+
    2024-04-02
  • PHP数据结构：AVL树的平衡之道，维持高效有序的数据结构
    avl 树是一种平衡二叉搜索树，确保快速高效的数据操作。为了实现平衡，它执行左旋和右旋操作，调整违反平衡的子树。avl 树利用高度平衡，确保树的高度相对于节点数始终较小，从而实现对数时间...
    99+
    2024-05-14
    php 数据结构
  • Python数据结构树与算法分析
    目录1.示例2.术语及定义3.实现3.1 列表之列表3.2节点与引用4.二叉树的应用4.1解析树4.2树的遍历5.利用二叉堆实现优先级队列6.二叉搜索树6.1搜索树的实现7.平衡二叉...
    99+
    2024-04-02
  • java数据结构之树的示例分析
    这篇文章主要介绍java数据结构之树的示例分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！树定义和基本术语定义树(Tree)是n(n≥0)个结点的有限集T，并且当n＞0时满足下列条件：（1）有且仅有一个特定的称为根...
    99+
    2023-05-30
    java
  • 图解AVL树数据结构输入与输出及实现示例
    目录AVL树(平衡二叉树)：AVL树的作用：AVL树的基本操作：AVL树的插入，单旋转的第一种情况---右旋：AVL树的插入，单旋转的第二种情况---左旋：AVL树的插入，双旋转的第...
    99+
    2024-04-02
  • C++数据结构二叉搜索树的实现应用与分析
    目录概念二叉搜索树的实现基本框架二叉搜索树的插入二叉搜索树的查找二叉搜索树的删除（重点）二叉搜索树的应用二叉树性能分析总结⭐️博客代码已上传至gitee：https://gitee....
    99+
    2024-04-02
  • C++数据结构模板进阶的多方面分析
    目录非类型模板参数模板的特化函数模板的特化类模板的特化模板的分离编译总结⭐️博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class...
    99+
    2024-04-02
  • Java数据结构之红黑树的示例分析
    小编给大家分享一下Java数据结构之红黑树的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！一、红黑树所处数据结构的位置：在JDK源码中, 有treeMap...
    99+
    2023-05-30
    java
  • 数据结构（四）：树
    树 概念：树是一些节点的集合，一棵树由称作根（root）的节点 r 以及0个或多个非空的（子）树组成，这些子树中每一棵的根都被来自根 r 的一条有向的边（edge）连接。每一棵子树的根叫做根 r 的儿子（child），r 是每一棵子树的根...
    99+
    2023-01-31
    数据结构
  • Python数据结构__树
    树是一种非常重要的数据结构，它是非线性结构，它不是Python内置的数据结构；树：  1.非线性结构，每个元素可以有多个前驱和后继；  2.树是n(n>=0)个元素的集合    n=0时，称为空树；    树只有一个特殊的没有前驱的元...
    99+
    2023-01-31
    数据结构 Python
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作