【数据结构高阶】AVL树

上期博客我们讲解了set/multiset/map/multimap的使用，下面我们来深入到底层，讲解其内部结构：

目录

一、AVL树的概念

二、AVL树的实现

2.1 节点的定义

2.2 数据的插入

2.2.1 平衡因子的调整

2.2.1.1 调整平衡因子的规律

2.2.2 子树的旋转调整

2.2.2.1 左单旋

2.2.2.2 右单旋

2.2.2.3 左右双旋

2.2.2.4 右左双旋

2.3 AVL树的检查验证

2.4 测试代码

三、AVL树实现的完整代码

一、AVL树的概念

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

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

● 它的左右子树都是AVL树

● 左右子树高度之差（简称平衡因子，不是每种AVL树都有平衡因子，平衡因子只是AVL树实现的一种方式）的绝对值不超过1（下图的平衡因子计算公式为：节点的右子树高度-左子树高度）

下图是一个AVL树：

二、AVL树的实现

2.1 节点的定义

这次我们直接实现K-V模型的二叉树：

template<class Key,class Val>
class AVLTreeNode
{
public:
	AVLTreeNode<Key, Val>* _left;
	AVLTreeNode<Key, Val>* _right;
	AVLTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	int _bf;//balance factor(平衡因子)

	AVLTreeNode(pair<Key, Val> kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_bf(0)
	{}
};

2.2 数据的插入

AVL树的数据插入需要遵循二叉搜索树的规律：

template<class Key, class Val>
class AVLTree
{
public:
	typedef AVLTreeNode<Key, Val> Node;

	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};

但是成功插入数据后就结束了吗？在AVL树中可没有这么简单，我们需要更新其插入节点的父节点的平衡因子，来保证这课树的整体结构还是一个AVL树。

2.2.1 平衡因子的调整

下面我们来讨论一下更新父节点平衡因子的操作：

我们看到上面的二叉树，现在向其中插入一个键值为8的数据：

插入后我们发现其插入节点的父节点平衡因子需要修改，那就要修改一下：

修改其父节点后，我们发现其父节点的父节点的平衡因子也需要调整，那再调整一下吧：

但是本次调整过后，平衡因子出现了2这个数值，但是平衡因子只能是1/0/-1，说明这时该节点下的子树已经不满足AVL树的结构了，这时要对其子树进行旋转来调整该树的结构（至于怎么旋转我们在下面会详细讲解），经过旋转过后子树肯定是满足AVL树的结构的，所以就并不再检查进行旋转的节点父节点平衡因子了：

那我们再看看另一种情况，我们向下面的二叉树中插入键值为6的数据：

插入后，我们发现需要修改其父节点的平衡因子： 

修改后，我们发现其父节点的平衡因子为0，为0时就意味着子树的高度没有发生变化，我们就没有必要再向上更新其父节点的平衡因子了： 

2.2.1.1 调整平衡因子的规律

所以总结一下上述规律，我们插入节点后肯定是要调整其父节点的平衡因子的，那调整父节点的平衡因子后，什么时候要向上调整其父节点的父节点（爷爷节点）的平衡因子呢？

这里有三种情况：

当父节点的平衡因子调整过后为1或-1时，此时说明其节点所在的子树的高度发生了变化（变为1或-1前，平衡因子只可能是0，说明插入之前子树两边的高度是相同的，这时在插入一个节点会导致其中一颗子树的高度发生变化），这时需要再继续向上调整其父节点的平衡因子

当父节点的平衡因子调整过后为2或-2时，该节点的子树不平衡，需要处理这颗旋转处理子树，旋转实质是是将该节点所在的子树的高度降1，所以旋转过后不影响子树的高度变化，此时就不需要再向上更新其父节点的平衡因子了

当父节点的平衡因子调整过后为0时（变为0前，平衡因子只可能是1或-1，说明插入之前一边高，一边低，但是插入节点是在矮的那边，其子树的高度不变），说明所在的子树高度不变，不用继续向上更新

我们用代码来实现一下平衡因子的调整：

template<class Key, class Val>
class AVLTree
{
public:
	typedef AVLTreeNode<Key, Val> Node;

	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//向上调整各节点的平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				--parent->_bf;//更新平衡因子
			}
			else
			{
				++parent->_bf;//更新平衡因子
			}
			//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或1继续向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//平衡因子为2或-2,树的结构不平衡，旋转parent节点所在子树
			{
				//旋转parent所在的子树
			}
			else if (parent->_bf == 0)//平衡因子为0,插入结束
			{
				break;
			}
			else//出现其他的情况说明树的根据有问题，报错退出
			{
				cout << "树的结构出错了" << endl;
				assert(0);
				exit(-1);
			}
		}
		return true;
	}

private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};

2.2.2 子树的旋转调整

当某个节点的平衡因子变为2或-2时，我们需要对其所在的子树进行旋转调整

下面我们分情况来讨论：

2.2.2.1 左单旋

下面的图代表的是一棵AVL树，其中52和60表示的两个节点，A、B、C分别为高度为h的AVL子树：

下面向C子树中插入数据使其高度发生变化：

现在键值为52的节点平衡因子变为2，下面我们要将这棵子树旋转：

我们可以看到旋转的过程是这样的：

B子树变成52的右子树->52变成60的左子树->60变成整颗树的根

上面这种需要旋转的树的根节点平衡因子为2，并且其根节点右孩子节点的平衡因子为1；这种情况下的旋转我们将其称为左单旋

下面我们就用代码实现一下左单旋：

void RotateL(Node* parent)//左单旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* pparent = parent->_parent;
	parent->_right = subRL;//更新parent的右节点
	if (subRL)//防止该节点为空
	{
		subRL->_parent = parent;//更新subRL的父节点
	}
	parent->_parent = subR;//更新parent的父节点
	subR->_left = parent;//subR的左子树置为parent
	subR->_parent = pparent;//更新subR的父节点
	if (pparent == nullptr)//旋转的是整棵树
	{
		_root = subR;//更新根节点
	}
	else//将旋转后的子树链接上整个二叉树
	{
		if (pparent->_left == parent)
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
	}
	subR->_bf = parent->_bf = 0;//更新平衡因子
}

下图是画出了代码所表示的节点： 

2.2.2.2 右单旋

再来看到另一种情况：

 下面向子树A中插入数据使其高度发生变化：

现在键值为60的节点平衡因子变为-2，下面我们要将这棵子树旋转： 

我们可以看到旋转的过程是这样的：

B子树变成60的左子树->60变成52的右子树->52变成整颗树的根

上面这种需要旋转的树的根节点平衡因子为-2，并且其根节点左孩子节点的平衡因子为-1；这种情况下的旋转我们将其称为右单旋

下面我们用代码实现一下右单旋：

void RotateR(Node* parent)//右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* pparent = parent->_parent;
	parent->_left = subLR;//更新parent的左节点
	if (subLR)//防止该节点为空
	{
		subLR->_parent = parent;//更新subLR的父节点
	}
	parent->_parent = subL;//更新parent的父节点
	subL->_right = parent;//subL的右子树置为parent
	subL->_parent = pparent;//更新subL的父节点
	if (pparent == nullptr)//旋转的是整棵树
	{
		_root = subL;//更新根节点
	}
	else//将旋转后的子树链接上整个二叉树
	{
		if (pparent->_left == parent)
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
	}
	subL->_bf = parent->_bf = 0;//更新平衡因子
}

下图画出了代码所表示的节点： 

2.2.2.3 左右双旋

接着来看到稍微复杂一点的情况，下面的图代表的是一棵AVL树，其中99、66和88表示的是三个节点，A、D分别为高度为h的AVL子树，B、C分别为高度为h-1的AVL子树：

现在我们向B子树中插入数据使其高度发生变化：

现在键值为99的节点平衡因子变为-2，下面我们要将这棵子树旋转： 

下面先将66所在子树进行左单旋：

再让99所在子树右单旋：

上面这种需要旋转的树的根节点平衡因子为-2，并且其根节点左孩子节点的平衡因子为1；这种情况下的两次旋转我们将其称为左右双旋

但是我们要注意的是，当新增节点在C子树上时，通过左右双旋调整后的结果又不一样：

 

我们可以看到因为新增节点的位置发生了变化，最终导致了各节点的平衡因子出现了差异

除了这两种情况，还有一种当h为0的极端情况：

所以我们在用代码实现的时要注意

void RotateLR(Node* parent)//左右双旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int subLR_bf = subLR->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
	RotateL(subL);//调用左单旋
	RotateR(parent);//调用右单旋
	if (subLR_bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (subLR_bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (subLR_bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.2.2.4 右左双旋

最后我们只剩一种情况了：需要旋转的树的根节点平衡因子为-2，并且其根节点右孩子节点的平衡因子为-1

下面我们来分析：

我们向上面这棵树中的C子树插入数据使其高度发生变化：

现在键值为66的节点平衡因子变为2，下面我们要将这棵子树旋转：

下面先将99所在子树进行右单旋：

再将66所在子树进行左单旋：

这样先右旋再左旋的情况我们将其称做：右左双旋

和左右双旋一样，新增节点的位置发生变化，会导致各节点的平衡因子出现差异，当新增节点在B子树上时，通过左右双旋调整后的结果又不一样：：

另外还有h为0的特殊情况：

好了，分析到这里，使用代码实现也就不是问题了：

void RotateRL(Node* parent)//右左双旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int subRL_bf = subRL->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
	RotateR(subR);//调用右单旋
	RotateL(parent);//调用左单旋
	if (subRL_bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else if (subRL_bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (subRL_bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.3 AVL树的检查验证

下面我们来实现一个函数来检查自己所创建的AVL树是否符合规则：

int _CountHeight(Node* root)//计算树的高度
{
	if (root == nullptr)
		return 0;
	int leftnum = _CountHeight(root->_left);
	int rightnum = _CountHeight(root->_right);
	return leftnum > rightnum ? leftnum + 1 : rightnum + 1;
}
bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;
	int leftH = _CountHeight(root->_left);
	int rightH = _CountHeight(root->_right);
	if (rightH - leftH != root->_bf)//检查当前节点平衡因子是否正确
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}

	return abs(leftH - rightH) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);//检查左右子树高度之差的绝对值是否小于2
}
bool IsBalance()//检查是否为AVL树
{
	return _IsBalance(_root);
}

2.4 测试代码

void Test_AVLTree()
{
	const size_t N = 5000;
	AVLTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
	cout << t.CountHeight() << endl;
}

运行效果：

三、AVL树实现的完整代码

#pragma once
#include<iostream>
#include<cassert>

using namespace std;

template<class Key,class Val>
class AVLTreeNode
{
public:
	AVLTreeNode<Key, Val>* _left;
	AVLTreeNode<Key, Val>* _right;
	AVLTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	int _bf;//balance factor(平衡因子)

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


template<class Key, class Val>
class AVLTree
{
	typedef AVLTreeNode<Key, Val> Node;

public:
	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//向上调整各节点的平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				--parent->_bf;//更新平衡因子
			}
			else
			{
				++parent->_bf;//更新平衡因子
			}
			//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或1继续向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//平衡因子为2或-2,树的结构不平衡，旋转parent节点所在子树
			{
				//旋转parent所在的子树
				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;
			}
			else if (parent->_bf == 0)//平衡因子为0,插入结束
			{
				break;
			}
			else//出现其他的情况说明树的根据有问题，报错退出
			{
				cout << "树的结构出错了" << endl;
				assert(0);
				exit(-1);
			}
		}
		return true;
	}

	void InOrder()//中序遍历
	{
		_InOrder(_root);
		cout << endl;
	}

	int CountHeight()//计算树的高度
	{
		return _CountHeight(_root);
	}

	bool IsBalance()//检查是否为AVL树
	{
		return _IsBalance(_root);
	}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
		subR->_bf = parent->_bf = 0;//更新平衡因子
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
		subL->_bf = parent->_bf = 0;//更新平衡因子
	}

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int subLR_bf = subLR->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
		RotateL(subL);//调用左单旋
		RotateR(parent);//调用右单旋
		if (subLR_bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if(subLR_bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (subLR_bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int subRL_bf = subRL->_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据
		RotateR(subR);//调用右单旋
		RotateL(parent);//调用左单旋
		if (subRL_bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (subRL_bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (subRL_bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)//如果是空树就直接结束
		{
			return;
		}
		_InOrder(root->_left);//先递归遍历其左子树
		cout << root->_kv.first << " ";//再遍历其根节点
		_InOrder(root->_right);//最后递归遍历其右子树
	}

	int _CountHeight(Node* root)//计算树的高度
	{
		if (root == nullptr)
			return 0;
		int leftnum = _CountHeight(root->_left);
		int rightnum = _CountHeight(root->_right);
		return leftnum > rightnum ? leftnum + 1 : rightnum + 1;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int leftH = _CountHeight(root->_left);
		int rightH = _CountHeight(root->_right);
		if (rightH - leftH != root->_bf)//检查当前节点平衡因子是否正确
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}

		return abs(leftH - rightH) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);//检查左右子树高度之差的绝对值是否小于2
	}
private:
	AVLTreeNode<Key, Val>* _root = nullptr;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/213917.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

对一个多维随机变量作为线性变换以后的协方差矩阵

对一个多维随机变量作为线性变换以后的协方差矩阵

假设是一个n维的随机变量&#xff0c;它的协方差矩阵 对做线性变换&#xff0c;其中是一个矩阵&#xff08;当然也可以是一个标量&#xff09;&#xff0c;的协方差矩阵 证明如下&#xff1a; 将代入&#xff0c;得
阅读更多...
git如何关联克隆远程仓库

git如何关联克隆远程仓库

一、添加远程仓库 之前我们仅仅是在本地创建了一个Git本地仓库&#xff0c;这里我们再在GitHub创建一个Git远程仓库&#xff0c;并且让这两个仓库进行远程同步&#xff0c;这样&#xff0c;GitHub上的仓库既可以作为备份&#xff0c;又可以让其他人通过该仓库来协作开发。 1.…
阅读更多...
【无标题】我们只能用成功来摧毁我们，原来的自己只会破败自己的事情。

【无标题】我们只能用成功来摧毁我们，原来的自己只会破败自己的事情。

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…
阅读更多...
JavaWeb 添加页面和用户图像展示

JavaWeb 添加页面和用户图像展示

add.jsp&#xff08;需要登录之后才可以访问 &#xff09; -> 不是和login.jsp同级了那就 在images目录下加上默认图像 js目录下加入common.js javaWeb项目中&#xff0c;页面的路径 img的src form的action link的href script的src a的href推荐使用绝对路径 这个绝对路径…
阅读更多...
【海思SS528 | VO】MPP媒体处理软件V5.0 | 视频输出模块——学习笔记

【海思SS528 | VO】MPP媒体处理软件V5.0 | 视频输出模块——学习笔记

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…
阅读更多...
Project 1: The Game of Hog(CS61A)

Project 1: The Game of Hog(CS61A)

&#xff08;第一阶段&#xff09;问题 5a&#xff08;3 分&#xff09; 实现该函数&#xff0c;该函数模拟了完整的 Hog 游戏。球员 交替轮流掷骰子&#xff0c;直到其中一名玩家达到分数。playgoal 您现在可以忽略 Feral Hogs 规则和论点; 您将在问题 5b 中实现它。feral_h…
阅读更多...
（学习笔记）Xposed模块编写（一）

（学习笔记）Xposed模块编写（一）

前提&#xff1a;需要已经安装Xposed Installer 1. 新建一个AS项目 并把MainActvity和activity_main.xml这两个文件删掉&#xff0c;然后在AndriodManifest.xml中去掉这个Activity的声明 2. 在settings.gralde文件中加上阿里云的仓库地址&#xff0c;否则Xposed依赖无法下载 m…
阅读更多...
Elasticsearch：什么是向量数据库？

Elasticsearch：什么是向量数据库？

向量数据库定义 向量数据库是将信息存储为向量的数据库&#xff0c;向量是数据对象的数值表示&#xff0c;也称为向量嵌入。 它利用这些向量嵌入的强大功能来对非结构化数据和半结构化数据&#xff08;例如图像、文本或传感器数据&#xff09;的海量数据集进行索引和搜索。 向…
阅读更多...
操作系统相关--面试和笔试高频

操作系统相关--面试和笔试高频

操作系统 计算题 页面置换算法 先进先出&#xff08;FIFO&#xff09;更新算法&#xff1a;总是淘汰最先进入内存的页面。即目前出现次数最多的页面 最近最久未使用&#xff08;LRU&#xff09;更新算法&#xff1a;当需要更新一页时&#xff0c;选择在最近一段时间内最久没…
阅读更多...
TensorRT安装及使用教程（ubuntu系统部署yolov7）

TensorRT安装及使用教程（ubuntu系统部署yolov7）

1 什么是TensorRT 一般的深度学习项目&#xff0c;训练时为了加快速度&#xff0c;会使用多 GPU 分布式训练。但在部署推理时&#xff0c;为了降低成本&#xff0c;往往使用单个 GPU 机器甚至嵌入式平台&#xff08;比如 NVIDIA Jetson&#xff09;进行部署&#xff0c;部署端也…
阅读更多...
Xshell会话文件解密获取密码

Xshell会话文件解密获取密码

Xshell会话文件解密获取密码 开发了一个小工具用于获取已存储的xshell会话密码功能简介截图展示下载地址 开发了一个小工具用于获取已存储的xshell会话密码 在日常开发中&#xff0c;服务器太多&#xff0c;密码记不住。使用xshell管理服务器会话&#xff0c;记住密码&#xf…
阅读更多...
Docker容器（一）概述

Docker容器（一）概述

一、虚拟化概述 1.1引⼊虚拟化技术的必要性 服务器只有5%的时间是在⼯作的&#xff1b;在其它时间服务器都处于“休眠”状态. 虚拟化前 每台主机⼀个操作系统; 软硬件紧密结合; 在同⼀个主机上运⾏多个应⽤程序通常会遭遇冲突; 系统的资源利⽤率低; 硬件成本⾼昂⽽且不够灵活…
阅读更多...
开发猿的平平淡淡周末---2023/12/3

开发猿的平平淡淡周末---2023/12/3

2023/12/3 天气晴 温度适宜 AM 早安八点多的世界&#xff0c;起来舒展了下腰&#xff0c;阳光依旧明媚&#xff0c;给平淡的生活带来了一丝暖意 日常操作&#xff0c;喂鸡&#xff0c;时政&#xff0c;洗漱&#xff0c;恰饭&#xff0c;肝会儿游戏 看会儿手机 ___看累…
阅读更多...
【Windows】如何实现 Windows 上面的C盘默认文件夹的完美迁移

【Windows】如何实现 Windows 上面的C盘默认文件夹的完美迁移

如何实现 Windows 上面的C盘默认文件夹的完美迁移 1. 遇到的问题 在我想迁移C盘的 下载 和 视频 文件夹的时候&#xff0c;遇到了这样的问题&#xff0c;在迁移之后&#xff0c;我显卡录像的视频还是保存到了C盘默认位置里&#xff0c;以及我迁移了 下载 之后下载的盘依然是在…
阅读更多...
LeetCode刷题---反转链表

LeetCode刷题---反转链表

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏&#xff1a;http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言&#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法&#xff0c;所以下面题目主要也是这些算法做的 我讲述…
阅读更多...
MDETR 论文报告

MDETR 论文报告

MDETR - Modulated Detection for End-to-End Multi-Modal Understanding MDETR - Modulated Detection for End-to-End Multi-Modal Understanding发现问题主要贡献和创新点主要方法和技术MDETR 的架构损失函数1. 框预测损失2. 软标记预测损失3. 对比对齐损失4. 总损失 实验和…
阅读更多...
Linux网络之连接跟踪 conntrack

Linux网络之连接跟踪 conntrack

一 Linux网络之连接跟踪 conntrack k8s 有关conntrack的分析 ① 什么是连接跟踪 netfilter连接跟踪 conntrack 详述 思考&#xff1a;连接跟踪模块会对哪些协议进行跟踪?TCP、UDP、ICMP、DCCP、SCTP、GRE ② 为什么需要连接跟踪 没有连接跟踪有很多问题是不好解决的&a…
阅读更多...
C语言-内存分配

C语言-内存分配

内存分配 1. 引入 int nums[10] {0}; //对int len 10; int nums[len] {0}; //错是因为系统的内存分配原则导致的2. 概述 在程序运行时&#xff0c;系统为了 更好的管理进程中的内存&#xff0c;所以有了 内存分配机制。 分配原则&#xff1a; 2.1 静态分配 静态分配原…
阅读更多...
解决top-k问题--堆排序

解决top-k问题--堆排序

目录 TOP-K问题 堆排序 考虑以下情况&#xff1a; 1.在n个数里面找最大的一个数 2.在n个数里面找最大的两个数 3.在n个数中求前k大的数 为什么不用大根堆呢&#xff1f; 代码 时间复杂度 TOP-K问题 即求数据结合中前K个最大的元素或者最小的元素&#xff0c;一般情况下数…
阅读更多...
使用Redis构建任务队列

使用Redis构建任务队列

文章目录 第1关&#xff1a;先进先出任务队列第2关&#xff1a;优先级任务队列第3关&#xff1a;定时任务队列 第1关&#xff1a;先进先出任务队列 编程要求 在Begin-End区域编写 add_task(task_name) 函数&#xff0c;实现将任务加入队列的功能&#xff0c;具体参数与要求如下…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站