红黑树/红黑树迭代器封装（C++）

        本篇将会较为全面的讲解有关红黑树的特点，插入操作，然后使用代码模拟实现红黑树，同时还会封装出红黑树的迭代器。

        在 STL 库中的 set 和 map 都是使用红黑树封装的，在前文中我们讲解了 AVL树，对于红黑树和 AVL 树来说，这两种树都是效率很高的搜索二叉树，但是相对而言 AVL 树会更加接近平衡二叉树，但是用于封装 set 和 map 的却是红黑树，这是因为虽然红黑树不是很接近平衡二叉树，但是和 AVL 树的搜索效率相比较其实相差不是很多，相反而言，对于红黑树在插入时的效率会比 AVL 树更高，所以封装 set 和 map 选择使用了红黑树。

        如下：

目录

1. 红黑树

All code

红黑树的特性

红黑树节点的定义

红黑树的插入操作

红黑树检测与暴力测试

2. 红黑树迭代器封装

 迭代器的测试

1. 红黑树

All code

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

enum Colour { RED, BLACK };

// 节点
template <class K, class V>
struct BRTreeNode {
	BRTreeNode<K, V>* _left;
	BRTreeNode<K, V>* _right;
	BRTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	BRTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

// k v
template <class K, class V>
class Iterator {
	typedef Iterator Self;
	typedef BRTreeNode<K, V> Node;
	typedef pair<K, V>& Ref;
	typedef pair<K, V>* Ptr;
public:
	Iterator(Node* node)
		:_node(node)
	{}

	Ref operator*() {
		return _node->_kv;
	}

	Ptr operator->() {
		return &(_node->_kv);
	}

	Self operator++() {
		// left middle right
		// 如果有右孩子节点，找出右孩子节点中的最左节点
		// 如果没有右孩子节点，需要不断向上迭代，找到最左节点
		if (_node->_right != nullptr) {
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left) {
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_left) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self operator--() {
		// 若当前迭代器为null，返回最右节点
		// left middle right
		// 如果有左孩子，找出左孩子中的最大节点
		// 如果没有左孩子，需要向上迭代


		if (_node->_left != nullptr) {
			Node* rightMin = _node->_left;
			while (rightMin && rightMin->_right) {
				rightMin = rightMin->_right;
			}
			_node = rightMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_right) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& it) {
		return _node != it._node;
	}

private:
	Node* _node;
};

template <class K, class V>
class BRTree {
	typedef BRTreeNode<K, V> Node;
public:
	typedef Iterator<K, V> iterator;
	// 封装迭代器
	iterator begin() {
		// 找到最左节点
		Node* leftMin = _root;
		while (leftMin && leftMin->_left) {
			leftMin = leftMin->_left;
		}
		return iterator(leftMin);
	}

	iterator end() {
		return iterator(nullptr);
	}
	// 插入
	bool insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* 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 {
				// 遇见相同元素
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < cur->_kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		cur->_parent = parent;
		// 开始调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			// 先判断当前插入的节点是在爷爷节点的左边还是右边
			if (parent == grandfather->_left) {
				Node* uncle = grandfather->_right;
				// 一共存在两种情况，叔叔节点存在且叔叔节点不为黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					// 更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else {
					// 现在这种情况属于叔叔节点不存在或者存在为黑
					// 需要判断当前属于什么情况
					if (cur == parent->_left) {
						//      g           p
						//   p     u -->  c   g
						// c                    u
						// 右旋即可
						RotateRight(grandfather);
						parent->_col = BLACK;
						cur->_col = grandfather->_col = RED;
					}
					else {
						//      g            g          c
						//   p     u -->   c   u -->  p   g
						//     c         p                   u
						// 先左旋，后右旋
						RotateLeft(parent);
						RotateRight(grandfather);
						cur->_col = BLACK;
						parent->_col = grandfather->_col = RED;
					}
					break;
				}
			}
			else {
				Node* uncle = grandfather->_left;
				// 一共存在两种情况，叔叔节点存在且叔叔节点为黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					// 更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else {
					if (cur == parent->_right) {
						//     g             p 
						//   u   p   -->   g   c
						//         c     u
						// 对g进行左旋
						RotateLeft(grandfather);
						grandfather->_col = cur->_col = RED;
						parent->_col = BLACK;
					}
					else {
						//     g             g            c
						//   u   p   -->   u   c   -->  g   p
						//      c                p    u
						// 先右旋，后左旋
						RotateRight(parent);
						RotateLeft(grandfather);
						cur->_col = BLACK;
						grandfather->_col = parent->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	// 右旋
	void RotateRight(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandfather = parent->_parent;

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

		parent->_parent = subL;
		subL->_right = parent;

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

	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandfather = parent->_parent;

		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;

		parent->_parent = subR;
		subR->_left = parent;

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

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

	bool isBalance() {
		// 需要检查黑色节点个数，需要检查红色节点的分布
		int refNum = 0;
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK)
				refNum++;
			cur = cur->_left;
		}
		return _Cheak(_root, 0, refNum);
	}
private:
	bool _Cheak(Node* root, int blackNum, int refNum) {
		if (root == nullptr) {
			if (refNum != blackNum) {
				cout << ":存在黑节点不平衡" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED) {
			cout << root->_kv.first << ":存在连续红节点" << endl;
			return false;
		}
		if (root->_col == BLACK) blackNum++;
		return _Cheak(root->_left, blackNum, refNum) && _Cheak(root->_right, blackNum, refNum);
	}

	void _InOrder(Node* root) {
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

红黑树的特性

       首先先给出红黑树的概念：

        红黑树是一种二叉搜索树，在每个节点上增加一共存储位表示节点的颜色，可以为 Red 或者 Black，通过对任何一条从根节点到叶子节点上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，所以接近平衡。

关于红黑树的特性，一共可以总结为以下四点：

        1. 每个节点不是黑色就是红色；

        2. 根节点是黑色的；

        3. 如果一个节点是红色的，则他的两个孩子节点的颜色是黑色的。

        4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

        5. 对于叶子节点都是黑色的（这里所指的黑色节点是指的是空结点）。

        红黑树的特性如上，那么关于红黑树是如何做到从根节点到叶子节点的路径中，最长的不会超过最短的两倍的呢？

        其实关于这个答案很简单，这是由上的1、3、4条性质所决定的，每条路径的黑色节点个数相同，并且一个节点不是黑色节点就是红色节点，所以对于最短路径可能为全都是黑色节点的路径，对于最长路径也不过是红色节点和黑色节点相混合的（因为红色节点的子节点必须为黑色节点），刚好是最短路径的两倍。

红黑树节点的定义

        首先先给出红黑树的节点定义，该节点的定义和平衡二叉树十分相似，节点的指针包含父节点的指针、左右孩子的节点的指针，然后还有表示保存演示的变量，然后就是保存键值的变量，如下：

// 颜色
enum Colour { RED, BLACK };

// 节点
template <class K, class V>
struct BRTreeNode {
	BRTreeNode<K, V>* _left;
	BRTreeNode<K, V>* _right;
	BRTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	BRTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

        如上的构造函数，我们将最新生成的节点默认为红色节点，那么为什么需要将节点默认设置为红色节点呢？

        这是因为倘若我们将节点的颜色设置为黑色节点，那么每一次在叶子节点处插入的节点也是黑色节点，但是这个使用就会出现一个问题，也就是刚插入节点的分支相对于其他分支多了一个黑色节点，和其他的性质对不上了。但是当我们插入的节点为红色节点的时候，就算是在红色节点下添加红色节点，我们也可以通过不断向上进行调整，调整到符合红黑树的性质。

红黑树的插入操作

        关于红黑树的操作而言，其大致逻辑和二叉搜索树一致，不过我们需要在插入之后对插入的节点进行调整，调整到满足红黑树的特性。上面我们已经说过，我们每一次插入是节点为红色节点，所以现在我们需要分别讨论出现连续红色节点的调整方法：

        首先先给出一些特殊的节点：插入的节点为根节点的时候，直接将根节点的颜色设置为黑色。另外，若插入在黑色节点的后面就不需要调整。

        由于二叉树是对称的，所以对应的操作也是对称的，出现一种情况就会有与之对应的第二种情况出现（比如插入的位置为爷爷节点的左子树或者右子树），所以只需要分析一种即可：

        关于红黑树的调整，其中一个比较关键的节点就算叔叔节点（父亲节点的兄弟节点），叔叔节点的特性将决定我们如何调整我们的红黑树。有关叔叔节点的特性，一共存在两种情况：（叔叔节点存在且不为红色），以及（叔叔节点不存在或者叔叔节点存在为黑色）。首

        先先谈论叔叔节点存在且为红色节点的情况：

        如上所示的调整方法，当我们插入的位置为红色节点的后面，并且叔叔节点存在且为红色，我们可以将爷爷节点调整为红色，然后将父亲节点和叔叔节点调整为黑色节点即可，这样调整的话，也不会影响各子树的黑色节点的数量，同时还可以将连续的红色节点拆分，但是需要注意的一点是，关于爷爷节点的上方的节点，若原爷爷节点上方的节点为红色节点，那么我们还需要进行迭代调整。

        第二种情况，叔叔不存在或者叔叔节点存在且为黑色节点的情况，如下：

        如上图所示，叔叔节点存在且为黑和叔叔节点不存在，进行的操作其实是相同的：我们只需要对爷爷节点进行右旋，然后将父节点设置为黑色节点，然后将爷爷节点设置为红色即可，根本不需要管叔叔节点处于什么样的状况。并且这样调整之后，不需要继续向上调整，这是因为调整之后原爷爷节点的位置还是黑色，所以不用在继续向上调整。

        以上只是当插入节点的位置为父节点的左边，还会有插入节点为父节点的右边的情况，如下：

        对于这种情况我们只需要对父节点进行左旋，然后对爷爷节点右旋。就可以解决问题了。

        关于如上的情况我们一直讨论情况是插入的节点在爷爷节点的左边，所以当插入在爷爷节点右边的时候，只需要相对以上情况对称选择调整或者向上调整即可。另外关于旋转的代码直接给出。

        所以关于的插入的代码为：

// 插入
bool insert(const pair<K, V>& kv) {
	if (_root == nullptr) {
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* 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 {
			// 遇见相同元素
			return false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first < cur->_kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;
	// 开始调整
	while (parent && parent->_col == RED) {
		Node* grandfather = parent->_parent;
		// 先判断当前插入的节点是在爷爷节点的左边还是右边
		if (parent == grandfather->_left) {
			Node* uncle = grandfather->_right;
			// 一共存在两种情况，叔叔节点存在且叔叔节点不为黑色
			if (uncle && uncle->_col == RED) {
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				// 更新
				cur = grandfather;
				parent = cur->_parent;
			}
			else {
				// 现在这种情况属于叔叔节点不存在或者存在为黑
				// 需要判断当前属于什么情况
				if (cur == parent->_left) {
					//      g           p
					//   p     u -->  c   g
					// c                    u
					// 右旋即可
					RotateRight(grandfather);
					parent->_col = BLACK;
					cur->_col = grandfather->_col = RED;
				}
				else {
					//      g            g          c
					//   p     u -->   c   u -->  p   g
					//     c         p                   u
					// 先左旋，后右旋
					RotateLeft(parent);
					RotateRight(grandfather);
					cur->_col = BLACK;
					parent->_col = grandfather->_col = RED;
				}
				break;
			}
		}
		else {
			Node* uncle = grandfather->_left;
			// 一共存在两种情况，叔叔节点存在且叔叔节点为黑色
			if (uncle && uncle->_col == RED) {
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				// 更新
				cur = grandfather;
				parent = cur->_parent;
			}
			else {
				if (cur == parent->_right) {
					//     g             p 
					//   u   p   -->   g   c
					//         c     u
					// 对g进行左旋
					RotateLeft(grandfather);
					grandfather->_col = cur->_col = RED;
					parent->_col = BLACK;
				}
				else {
					//     g             g            c
					//   u   p   -->   u   c   -->  g   p
					//      c                p    u
					// 先右旋，后左旋
					RotateRight(parent);
					RotateLeft(grandfather);
					cur->_col = BLACK;
					grandfather->_col = parent->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

void RotateRight(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* grandfather = parent->_parent;

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

	parent->_parent = subL;
	subL->_right = parent;

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

void RotateLeft(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* grandfather = parent->_parent;

	parent->_right = subRL;
	if (subRL) subRL->_parent = parent;

	parent->_parent = subR;
	subR->_left = parent;

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

红黑树检测与暴力测试

        将根据以上写出的代码给出对应的检测代码，其中主要检测红黑树是否平衡（满足红黑树特性），如下：

bool _Cheak(Node* root, int blackNum, int refNum) {
	if (root == nullptr) {
		if (refNum != blackNum) {
			cout << ":存在黑节点不平衡" << endl;
			return false;
		}
		return true;
	}
	if (root->_col == RED && root->_parent->_col == RED) {
		cout << root->_kv.first << ":存在连续红节点" << endl;
		return false;
	}
	if (root->_col == BLACK) blackNum++;
	return _Cheak(root->_left, blackNum, refNum) && _Cheak(root->_right, blackNum, refNum);
}

bool isBalance() {
	// 需要检查黑色节点个数，需要检查红色节点的分布
	int refNum = 0;
	Node* cur = _root;
	while (cur) {
		if (cur->_col == BLACK)
			refNum++;
		cur = cur->_left;
	}
	return _Cheak(_root, 0, refNum);
}

        检测代码如下：

void BRTreeTest01() {
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// {16, 3, 7, 11, 9, 26, 18, 14, 15}
	BRTree<int, int> tree;

	for (auto e : a) {
		
		tree.insert(make_pair(e, e));
	}
	tree.InOrder();
	cout << tree.isBalance() << endl;
}

void BRTreeTest02() {
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (int i = 0; i < N; i++) {
		v.push_back(rand() + 1);
	}
	size_t begin1 = clock();
	BRTree<int, int> tree;
	for (auto e : v)
		tree.insert({ e, e });
	size_t end1 = clock();
	cout << "insert" << end1 - begin1 << endl;

	cout << tree.isBalance() << endl;

}

        其中第一个测试为普通测试，第二个测试为压力测试。如下：

2. 红黑树迭代器封装

        我们前文中已经提到关于红黑树可以用于封装 set 和 map，那么关于这两个容器也会存在迭代器，我们现在直接在红黑树阶段封装一个迭代器。

        关于红黑树的迭代器，其中主要指向的是红黑树的节点，所以我们的迭代器主要为一个指向节点的指针，然后我们还需要对我们的迭代器进行运算符重载，比如常用的 * 解引用，  ->，还有 != 操作符。还有++ 与 -- 运算符重载。如下：

template <class K, class V>
class Iterator {
	typedef Iterator Self;
	typedef BRTreeNode<K, V> Node;
	typedef pair<K, V>& Ref;
	typedef pair<K, V>* Ptr;
public:
	Iterator(Node* node)
		:_node(node)
	{}

	Ref operator*() {
		return _node->_kv;
	}

	Ptr operator->() {
		return &(_node->_kv);
	}

	Self operator++() {
		// left middle right
		// 如果有右孩子节点，找出右孩子节点中的最左节点
		// 如果没有右孩子节点，需要不断向上迭代，找到最左节点
		if (_node->_right != nullptr) {
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left) {
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_left) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self operator--() {
		// left middle right
		// 如果有左孩子，找出左孩子中的最大节点
		// 如果没有左孩子，需要向上迭代


		if (_node->_left != nullptr) {
			Node* rightMin = _node->_left;
			while (rightMin && rightMin->_right) {
				rightMin = rightMin->_right;
			}
			_node = rightMin;
		}
		else {
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur != parent->_right) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& it) {
		return _node != it._node;
	}

private:
	Node* _node;
};

        如上的操作中，最为麻烦的操作就算 ++ 和 --，因为在红黑树中的节点并不是连续的，而是相互之间都是使用左右子树和父亲指针所维护的指针所连接起来的。

        对于 ++ 操作，我们需要取得下一个节点，根据中序遍历原则（左 中 右），当右子树不为空的时候，返回右子树中的最小节点，若右子树为空的时候，这个时候只能向上迭代，直到为祖先节点的左子树的时候，就可以停止迭代了，这个祖先节点就是我们要找的节点。

        -- 运算符重载和 ++ 相似，只不过一切操作都是相反的而已。

        另外，我们还需要在红黑树中定义 begin 和 end 函数，关于 begin 函数就是返回树的最左节点，但是关于 end 函数，我们这里直接返回的是指向 nullptr 的迭代器，但是这样会存在一个问题，也就是若我们直接给一个指向 end 的迭代器，我们并不能找到以上的树中的节点。

 迭代器的测试

        关于迭代器的测试如下：

void BRTreeTest03() {
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };
	BRTree<int, int> tree;
	for (auto e : a) 
		tree.insert(make_pair(e, e));
	
	auto it = tree.begin();
	while (it != tree.end()) {
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}

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

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

相关文章

手机自动化测试：4.通过appium inspector 获取相关app的信息，以某团为例，点击，搜索，获取数据等。

手机自动化测试：4.通过appium inspector 获取相关app的信息，以某团为例，点击，搜索，获取数据等。

0.使用inspector时&#xff0c;一定要把不相关的如weditor啥的退出去&#xff0c;否则&#xff0c;净是事。 1.从0开始的数据获取 第一个位置&#xff0c;有时0.0.0.0&#xff0c;不可以的话&#xff0c;你就用这个。 第二个位置&#xff0c;抄上。 直接点击第三个启动。不要…
阅读更多...
论文阅读：Indoor Scene Layout Estimation from a Single Image

论文阅读：Indoor Scene Layout Estimation from a Single Image

项目地址&#xff1a;https://github.com/leVirve/lsun-room/tree/master 发表时间&#xff1a;2018 icpr 场景理解&#xff0c;在现实交互的众多方面中&#xff0c;因其在增强现实&#xff08;AR&#xff09;等应用中的相关性而得到广泛关注。场景理解可以分为几个子任务&…
阅读更多...
Makefile：从零开始入门Makefile

Makefile：从零开始入门Makefile

目录 1.前言 2.Makefile的简单介绍 3.Makefile中的指令规则 4.Makefile的执行流程 5.Makefile中的变量类型 6.Makefile中的模式匹配 7.Makefile中的函数 8.Makefile补充知识 前言 在Linux中编译CPP文件&#xff0c;我们能够使用GCC命令进行编译&#xff0c;但当项目文件多且繁杂…
阅读更多...
如何利用pandas解析html的表格数据

如何利用pandas解析html的表格数据

如何利用pandas解析html的表格数据 我们在编写爬虫的过程中&#xff0c;经常使用的就是parsel、bs4、pyquery等解析库。在博主的工作中经常的需要解析表格形式的html页面&#xff0c;常规的写法是&#xff0c;解析table表格th作为表头&#xff0c;解析td标签作为表格的行数据 …
阅读更多...
网站不收录的原因

网站不收录的原因

随着互联网的发展&#xff0c;越来越多的网站被创建和更新&#xff0c;然而&#xff0c;并不是所有的网站都能被搜索引擎收录。有时候&#xff0c;这些网站会因为各种原因而被搜索引擎排除在搜索结果之外。下面我们来探讨一下网站不收录的原因。 首先&#xff0c;网站不收录可能…
阅读更多...
贪心算法学习三

贪心算法学习三

例题一 解法&#xff08;贪⼼&#xff09;&#xff1a; 贪⼼策略&#xff1a; ⽤尽可能多的字符去构造回⽂串&#xff1a; a. 如果字符出现偶数个&#xff0c;那么全部都可以⽤来构造回⽂串&#xff1b; b. 如果字符出现奇数个&#xff0c;减去⼀个之后&#xff0c;剩下的…
阅读更多...
12.【Orangepi Zero2】基于orangepi_Zero_2 Linux的智能家居项目

12.【Orangepi Zero2】基于orangepi_Zero_2 Linux的智能家居项目

基于orangPi Zero 2的智能家居项目 需求及项目准备 语音接入控制各类家电&#xff0c;如客厅灯、卧室灯、风扇回顾二阶段的Socket编程&#xff0c;实现Sockect发送指令远程控制各类家电烟雾警报监测&#xff0c; 实时检查是否存在煤气泄漏或者火灾警情&#xff0c;当存在警情时…
阅读更多...
Robust Tiny Object Detection in Aerial Images amidst Label Noise

Robust Tiny Object Detection in Aerial Images amidst Label Noise

文章目录 AbstractIntroductionRelated WorkMethodsClass-aware Label CorrectionUpdateFilteringTrend-guided Learning StrategyTrend-guided Label ReweightingRecurrent Box RegenerationExperimentpaper Abstract 精确检测遥感图像中的小目标非常困难，因为这类目标视觉信…
阅读更多...
关于目前ggrcs包的报错解决方案

关于目前ggrcs包的报错解决方案

目前有不少粉丝私信我说使用ggrcs包出现如下错误 我查看了一下&#xff0c;目前报错来源于新版本后的RMS包&#xff0c;主要是预测函数的报错&#xff0c;这个只能等R包作者来修复这个错误。目前需要急用的话&#xff0c;我提供了一个方案&#xff0c;请看下面视频操作 关于目前…
阅读更多...
外部排序快速入门详解:基本原理，败者树，置换-选择排序，最佳归并树

外部排序快速入门详解:基本原理，败者树，置换-选择排序，最佳归并树

文章目录 外部排序1.最基本的外部排序原理2.外部排序的优化2.1 败者树优化方法2.2 置换-选择排序优化方法2.3 最佳归并树 外部排序 为什么要学习外部排序&#xff1f; 答&#xff1a; 在处理数据的过程中&#xff0c;我们需要把磁盘(外存&#xff09;中存储的数据拿到内存中处理…
阅读更多...
通过 Python+Nacos实现微服务，细解微服务架构

通过 Python+Nacos实现微服务，细解微服务架构

shigen坚持更新文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 个人IP&#xff1a;shigen 背景 一直以来的想法比较多&#xff0c;然后就用Python编写各种代码脚本。很多…
阅读更多...
在 Ubuntu 中安装 Docker

在 Ubuntu 中安装 Docker

在 Ubuntu 中安装 Docker 首先&#xff0c;更新你的 Ubuntu 系统。 1、更新 Ubuntu 打开终端&#xff0c;依次运行下列命令&#xff1a; sudo apt update sudo apt upgrade sudo apt full-upgrade 2、添加 Docker 库 首先&#xff0c;安装必要的证书并允许 apt 包管理器…
阅读更多...
AI数据分析：根据Excel表格数据绘制柱形图

AI数据分析：根据Excel表格数据绘制柱形图

工作任务&#xff1a;将Excel文件中2013年至2019年间线上图书的销售额&#xff0c;以条形图的形式呈现&#xff0c;每个条形的高度代表相应年份的销售额&#xff0c;同时在每个条形上方标注具体的销售额数值 在deepseek中输入提示词&#xff1a; 你是一个Python编程专家&#…
阅读更多...
XMind v24.04.1 全功能VIP版（思维升级，效率飞跃）

XMind v24.04.1 全功能VIP版（思维升级，效率飞跃）

软件介绍 XMind 是一款功能丰富的思维导图和创新构思工具&#xff0c;可在多个平台助力高效思考。它涵盖了从灵感触发、结构构建到演示展示的完整思维过程&#xff0c;有效提升创建思维导图的效率。这款工具适用于记录灵感、创新思维、问题解决和效率提升等多元场景&#xff0…
阅读更多...
GEE训练教程——如何确定几何形状的中心点坐标和相交的坐标

GEE训练教程——如何确定几何形状的中心点坐标和相交的坐标

简介 在GEE中&#xff0c;可以使用.geometry()方法来获取几何形状的中心点坐标和相交的坐标。 首先&#xff0c;使用.geometry()方法获取几何形状的几何信息&#xff0c;然后使用.centroid()方法获取几何形状的中心点坐标。示例代码如下&#xff1a; // 获取几何形状的中心点…
阅读更多...
Golang | Leetcode Golang题解之第132题分割回文串II

Golang | Leetcode Golang题解之第132题分割回文串II

题目&#xff1a; 题解&#xff1a; func minCut(s string) int {n : len(s)g : make([][]bool, n)for i : range g {g[i] make([]bool, n)for j : range g[i] {g[i][j] true}}for i : n - 1; i > 0; i-- {for j : i 1; j < n; j {g[i][j] s[i] s[j] && g[…
阅读更多...
【Linux文件篇】系统文件、文件描述符与重定向的实用指南

【Linux文件篇】系统文件、文件描述符与重定向的实用指南

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; 前言&#xff1a;相信大家对文件都不会太陌生、也不会太熟悉。在没有学习Linux操作系统时&#xff0c;我们在学习C或C时都学过如何去创建、打开、读写等待文件的操作&#xff0c;知道一些语言级别的一些接口与函数。但…
阅读更多...
【C++题解】1389 - 数据分析

【C++题解】1389 - 数据分析

问题&#xff1a;1389 - 数据分析 类型&#xff1a;简单循环 题目描述&#xff1a; 该方法的操作方式为&#xff0c;如果要传递 2 个数字信息给友军&#xff0c;会直接传递给友军一个整数 n&#xff08;n 是一个 10 位以内的整数&#xff09;&#xff0c;该整数的长度代表要传…
阅读更多...
Python私教张大鹏 Vue3整合AntDesignVue之Breadcrumb 面包屑

Python私教张大鹏 Vue3整合AntDesignVue之Breadcrumb 面包屑

显示当前页面在系统层级结构中的位置&#xff0c;并能向上返回。 何时使用 当系统拥有超过两级以上的层级结构时&#xff1b; 当需要告知用户『你在哪里』时&#xff1b; 当需要向上导航的功能时。 案例&#xff1a;面包屑导航基本使用 核心代码&#xff1a; <template…
阅读更多...
[spring] Spring MVC Thymeleaf（上）

[spring] Spring MVC Thymeleaf（上）

[spring] Spring MVC & Thymeleaf&#xff08;上&#xff09; 本章内容主要过一下简单的 Spring MVC 的案例 简单来说&#xff0c;spring mvc 就是比较传统的网页开发流程&#xff0c;目前 boot 是可以比较轻松的配置 thymeleaf——毕竟 spring boot 内置对 thymeleaf 的…
阅读更多...
最新文章

Copyright @ 2022~2023