DS进阶：AVL树和红黑树

一、AVL树

1.1 AVL树的概念

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

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
（1）它的左右子树都是AVL树
（2）左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
 

AVL树有多种实现版本，但是我们采用平衡因子的版本来模拟实现AVL树。

1.2 AVL树的节点定义

        AVL树每插入或者删除一个节点，都有可能会影响高度，所以大多数情况下都需要向上调整平衡因子，所以我们的实现采用三叉链的形式（left、right、parent），方便我们找父节点，并且引入平衡因子，为的就是通过对平衡因子的调整和判断该树是否需要进行旋转。

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)
	{}
};

      平衡因子的大小=右子树的高度-左子树的高度。 

1.3 AVL树的插入

        首先AVL树本质上也是BST的逻辑，只不过增加了平衡因子来控制高度。所以在按照BST的逻辑插入节点之后，我们要去向上调整平衡因子。逻辑：如果我（cur）是你（parent）的左子树，那么你的bf就-- ，如果我是你的右子树，那么你的bf就++（因为平衡因子的大小=右子树的高度-左子树的高度。）

       而现在需要思考的问题就是，什么情况下需要去进行调整。因此我们需要分情况讨论

1、如果调整过后，平衡因子的绝对值为1，说明调整之前的平衡因子为0，即左右高度是相等的，此时变成1说明树的高度变了，因此需要继续向上调整。

2、如果调整过后，平衡因子的绝对值为2，说明调整之前的平衡因子绝对值为1，说明子树已经严重不平衡并且破坏了AVL树的规则，此时我们就要进行旋转。旋转过后就可以结束循环了

3、如果调整过后，平衡因子的绝对值是0，说明调整之前的平衡因子的绝对值是1，这说明之前的高度是不平衡的，插入之后反而变得更平衡了，此时就可以结束循环了。

       根据上面的这些规则，我们现将整个架子先搭建起来，然后再去研究当bf的绝对值为2的时候应该怎么去进行旋转。

	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->_left;
			}
			else if (cur->_kv.first < kv.first) //比你小，你去右子树
			{
				parent = cur;
				cur = cur->_right;
			}
			else return false;//相等 
		}
		//此时肯定是对应地接在parent的后面
		cur = new Node(kv);
		if (kv.first < parent->_kv.first)   parent->_left =cur;                //比父亲小连左边
		else  parent->_right = cur; //比父亲大连右边
		//别忘了父亲指针
		cur->_parent = parent;
      //调整平衡因子
		while (parent)
		{
			//首先调整因子，如果我是你的左孩子，这时你的左边变高了，所以要--
			//如果我是你的右孩子，此时你的右边变高了，所以要++
			if (cur == parent->_left) --parent->_bf;
			else ++parent->_bf;
         //更新之后，我们要根据当前多的情况，决定是向上更新，还是旋转，还是退出
         if (abs(parent->_bf) == 1)  //更新之后变成1，说明之前是左右相等，现在高度变了
         {
				parent = parent->_parent;//继续向上更新
				cur = cur->_parent;
          }
         // 更新之后变成0，说明之前是1或者 - 1，插入后更加平衡了，此时就不需要进行下去了
        else if (abs(parent->_bf) == 0)  break;
        else if (abs(parent->_bf) == 2) //说明子树不平衡，需要对子树进行旋转处理
        {
				//……………………… （旋转）
				break;
         }

1.4 AVL树的旋转（重点）

每一个模块都分别画了抽象图和具象图

1.4.1 新节点插入较高左子树的左侧 （左左->右单旋）

1.4.2 新节点插入较高右子树的右侧 （右右->左单旋）

1.4.3 新节点插入较高左子树的右侧 （左右->左右双旋）

1.4.4 新节点插入较高右子树的左侧 （右左->右左双旋）

 1.4.5 旋转的代码完善

        分析完上面的四种情况，我们通过抽象图去判断具体应该怎么旋转，分别封装对应的旋转函数，然后再根据图去看看哪一些需要去调整平衡因子。统一放在我们的代码逻辑里面。 

       平时我们记忆该选择哪一种旋转方式，可以先画出折线图再一步一步去分析。

	void RotateR(Node *parent)
	{
	   //旋转前，先记录对应的节点
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppnode = parent->_parent;//子树的前驱节点
		//先让b变成60的左边
		parent->_left = subLR;
		if (subLR) subLR->_parent = parent;
		//让60变成30的右边
		subL->_right = parent;
		parent->_parent = subL;
		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
		if (ppnode==nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
		else
		{
			if (ppnode->_left == parent) ppnode->_left = subL;
			else ppnode->_right = subL;
			//向上连接
			subL->_parent = ppnode;
		}
		//旋转完后，别忘记调节平衡因子，按图，都为0
		subL->_bf = parent->_bf = 0;
	}


	void RotateL(Node* parent)
	{
		//旋转前，先记录对应的节点
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppnode = parent->_parent;//子树的前驱节点
		//先让b变成30的边
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		//让30变成60的左边
		subR->_left = parent;
		parent->_parent = subR;
		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
		else
		{
			if (ppnode->_left == parent) ppnode->_left = subR;
			else ppnode->_right = subR;
			//向上连接
			subR->_parent = ppnode;
		}
		//旋转完后，别忘记调节平衡因子，按图，都为0
		subR->_bf = parent->_bf = 0;
	}


	void RotateLR (Node* parent)
	{
	   //旋转前，先记录相应的节点
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		//先对30左旋，再对90右旋
		RotateL(subL);
		RotateR(parent);
		//此时要调整平衡因子，但是有三种情况
		if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (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 bf = subRL->_bf;
		//先对90右旋，再对30左旋
		RotateR(subR);
		RotateL(parent);
		//此时要调整平衡因子，但是有三种情况
		if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else assert(false);
	}


};

然后我们接着去根据4种旋转方式，判断insert需要调用哪一个类型的函数，完善我们的insert代码

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->_left;
		}
		else if (cur->_kv.first < kv.first) //比你小，你去右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else return false;//相等 
	}
	//此时肯定是对应地接在parent的后面
	cur = new Node(kv);
	if (kv.first < parent->_kv.first)   parent->_left =cur;                //比父亲小连左边
	else  parent->_right = cur; //比父亲大连右边
	//别忘了父亲指针
	cur->_parent = parent;
  //调整平衡因子
	while (parent)
	{
		//首先调整因子，如果我是你的左孩子，这时你的左边变高了，所以要--
		//如果我是你的右孩子，此时你的右边变高了，所以要++
		if (cur == parent->_left) --parent->_bf;
		else ++parent->_bf;

		//更新之后，我们要根据当前多的情况，决定是向上更新，还是旋转，还是退出
		if (abs(parent->_bf) == 1)  //更新之后变成1，说明之前是左右相等，现在高度变了
		{
			parent = parent->_parent;//继续向上更新
			cur = cur->_parent;
		}
		// 更新之后变成0，说明之前是1或者 - 1，插入后更加平衡了，此时就不需要进行下去了
		else if (abs(parent->_bf) == 0)  break;
		else if (abs(parent->_bf) == 2) //说明子树不平衡，需要对子树进行旋转处理
		{
			//旋转处理 1、让子树平衡（降低高度） 2、旋转同时保证是搜索树的逻辑。
			//此时会出现四种情况，左单旋 右单旋 左右双旋转  右左双旋
		
			//情况1 右单旋   较高左子树的左侧
			if (parent->_bf == -2 && cur->_bf == -1)  RotateR(parent);
			//情况2 左单旋   较高右子树的右侧
			else if (parent->_bf == 2 && cur->_bf == 1)  RotateL(parent);
			//情况3 左右双旋  较高左子树的右侧
			else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent);
		    //情况4  右左双旋  较高右子树的左侧
			else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent);
			else assert(false);//加个断言防止旋转出问题
			//旋转处理完之后，可以直接break
			break;
		}
		else  assert(false);//加个断言，防止平衡因子出问题
	}
	
	return true;
}

1.5 AVL树的验证

1.5.1 验证其为二叉搜索树

        这个比较容易，我们可以直接通过一个中序遍历，如果打印出来之后得到的是一个有序序列，说明这就是一个二叉搜索树。但是接下来我们还得判断他是否是平衡树。

void Inorder()//中序遍历接口
{
	_Inorder(_root);
	cout << endl;
}

void _Inorder(Node*root)
{
	if (root == nullptr) return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}

1.5.2 验证节点的平衡因子是否等于右子树的高度-左子树的高度

     首先我们需要封装一个计算树高度的函数。需要用到后序遍历。

int Height()  //搜索树的高度
{
	return _Height(_root);
}
int _Height(Node* root)
{
	if (root == nullptr) return 0;
	int leftH = _Height(root->_left);
	int rightH = _Height(root->_right);
	return leftH > rightH ? leftH + 1 : rightH + 1;
}

       然后看看我们遍历到当前节点的时候，我们用该函数算出左子树的高度和右子树的高度，看看右子树-左子树是否等于平衡因子。 

1.5.3 以每个节点为根的树他的左右子树是否严格遵守高度差

      但是平衡因子是我们自己去调整的，所以我们最关键的还是去判断我们的左右子树的高度差绝对值是否<2 

     需要注意的是，我们必须确保每一个子树都满足AVL树的性质，所以调用完一次isbalance之后，还得去继续判断他的左子树和右子树！！！  这样才能说明他是一颗平衡树！！   

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

bool _IsBalance(Node* root)
{
	if (root == nullptr) return true;
	int leftH = _Height(root->_left);
	int rightH = _Height(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);
}

 1.6 AVL树的性能

      AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2N。但是如果要对AVL树做一些结构修改的操
作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数
据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

     为了解决这个问题，红黑树出现了！！

二、红黑树

2.1 红黑树的概念

        红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的（通过几条规则达到近似平衡）。

    总的来说，BST可能会退化成单支树，而AVL旋转过于严格，RB就是一种退而求其次的解决方法。 比如下面这颗树，AVL树一定旋转，但是RB不一定旋转。

 2.2 红黑树的性质

    接下来我们就来探究，大佬是如何通过几条规则来让红黑树确保没有一条路径会比其他路径长出俩倍的。

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
 

 思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点
个数的两倍？

 2.3 红黑树节点的定义

和将AVL树的平衡因此换成颜色

enum Colour
{
	RED,
	BLACK,
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;
	RBTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}

};

思考：为什么我们默认要把颜色设置成红色？？

      要分析究竟设置成红色还是黑色好一点，取决于以上的两条规则（1）如果一个节点是红色的，则它的两个孩子结点是黑色的 。（2）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

      首先我们要知道，插入这个节点之前该树一定是保持红黑树的性质，即满足上面的两个规则，如果我们新插入的节点默认选择黑色的话，那么凭空多出来的黑色节点必然会导致规则2被破坏，也就是说我们每插入一次就要去调整。如果我们选择的是红色的话，我们红色的父亲节点是黑色，那么就不需要进行调整，如果父亲节点是红色，我们才要进行调整！！！总的来说就是黑色是必然会破坏规则的，但是红色不一定，所以我们默认选择设置成红色，这样需要考虑的情况会更少一些。

2.4 红黑树的插入和旋转（重点）

情况1： 首先因为我们把默认节点设置为红色，所以如果被插入位置的父亲节点是黑色的话，就不需要进行调整了。

情况2：如果待插入前是空树， 那么新插入元素自动成为根，并且将其设置为黑色

      前两个情况比较简单，而后三个情况就是红黑树的非常关键的逻辑！！首先我们要知道我们调整的前提是当前待插入节点的父节点也是红色。

      如上图我们可以知道，因为待插入节点的父节点必然是红色，所以其祖父节点g必然是黑色，而我们下面情况的分析就是取决于u节点 

情况3：u存在且为红

 情况4：u存在且为黑，由情况3变化而来，插入在较高子树的同一侧（单旋）

 情况5：u存在且为黑，由情况3变化而来，插入在较高子树的另一侧（双旋） 

 总结：

 2.5 红黑树旋转和插入代码实现


	//旋转代码和AVL树是一样的，只不过不需要搞平衡因子
	void RotateL(Node* parent)
	{
		//旋转前，先记录对应的节点
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppnode = parent->_parent;//子树的前驱节点
		//先让b变成30的边
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		//让30变成60的左边
		subR->_left = parent;
		parent->_parent = subR;
		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
		else
		{
			if (ppnode->_left == parent) ppnode->_left = subR;
			else ppnode->_right = subR;
			//向上连接
			subR->_parent = ppnode;
		}
	}


	void RotateR(Node* parent)
	{
		//旋转前，先记录对应的节点
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppnode = parent->_parent;//子树的前驱节点
		//先让b变成60的左边
		parent->_left = subLR;
		if (subLR) subLR->_parent = parent;
		//让60变成30的右边
		subL->_right = parent;
		parent->_parent = subL;
		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
		if (ppnode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
		else
		{
			if (ppnode->_left == parent) ppnode->_left = subL;
			else ppnode->_right = subL;
			//向上连接
			subL->_parent = ppnode;
		}
	}


//先用搜索树的逻辑插入节点，然后再去更新平衡因子。
bool Insert(const pair<K, V>& kv)
{
	//如果为空树，新节点就是根
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col=BLACK;
		return true;
	}
	//如果不为空树
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first > kv.first) //如果我比你大，到左子树去
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first) //比你小，你去右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else return false;//相等 
	}
	//此时肯定是对应地接在parent的后面
	cur = new Node(kv);
	if (kv.first < parent->_kv.first)   parent->_left = cur;                //比父亲小连左边
	else  parent->_right = cur; //比父亲大连右边
	//别忘了父亲指针
	cur->_parent = parent;
	
	
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		//情况1，如果u为存在且为红
		if (grandfather->_left == parent)//如果p是g的左边，u就在右边
		{
			Node* uncle = grandfather->_right;
			//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else //情况2或者情况3， u为黑或者不存在   旋转+变色
			{ 
				if (cur == parent->_left) //情况2 右单旋+p变黑 g变红
				{
					//      g
					//   p    u
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else  //情况3 右左双旋  c变黑 g变红
				{
					//          g
						//   p     u
						//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;//情况2和情况3都要跳出循环
			}
		
		}
		else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边    几乎一样，就是旋转的逻辑不同
		{
				Node* uncle = grandfather->_left;
				//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else//情况2或者情况3， u为黑或者不存在   旋转+变色
				{
					if (cur == parent->_right) //情况2 左单旋+p变黑 g变红
					{
						//      g
						//   p    u
						//          c
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else  //情况3 左右双旋  c变黑 g变红
					{
						//          g
							//   p     u
							//       c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//情况2和情况3都要跳出循环
				}
		}
	}
	_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错
	return true;
}

 2.6 红黑树的验证规则

bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout << "根节点颜色是红色" << endl;
		return false;
	}
	int benchmark = 0;//找到一条路径作为基准值 然后看看其他路径是否相等
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
			++benchmark;
		cur = cur->_left;
	}

	// 连续红色节点
	return _Check(_root, 0, benchmark);
}
bool _Check(Node* root, int blackNum, int benchmark)
{
	if (root == nullptr)
	{
		if (benchmark != blackNum)
		{
			cout << "某条路径黑色节点的数量不相等" << endl;
			return false;
		}

		return true;
	}

	if (root->_col == BLACK)
	{
		++blackNum;
	}

	if (root->_col == RED
		&& root->_parent
		&& root->_parent->_col == RED)
	{
		cout << "存在连续的红色节点" << endl;
		return false;
	}

	return _Check(root->_left, blackNum, benchmark)
		&& _Check(root->_right, blackNum, benchmark);
}

2.7 RB和AVL的比较

1、红黑树不追求"完全平衡"，即不像AVL那样要求节点的高度差 <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低。

2、就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)，删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

 总结：

（ 1 ）AVL更平衡，结构上更加直观，时间效能针对读取而言更高（搜索效率高）；维护稍慢，空间开销较大。
（ 2 ） 红黑树，读取略逊于AVL，维护强于AVL（复衡效率高），空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。

（3）总体来说RB的整体性能高于AVL，因此在实际应用中基本上都是用的RB。

2.8 红黑树的实际应用

1. C++ STL库 -- map/set、mutil_map/mutil_set
2. Java 库
3. linux内核
4. 其他一些库

     在后面关于封装map和set的过程中，会再次用到红黑树的知识，因为STL底层的架子就是用的红黑树。

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

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

相关文章

使用Keil移植工程时修改单片机型号参数

使用Keil移植工程时修改单片机型号参数

系列文章目录 STM32单片机系列专栏 C语言术语和结构总结专栏 当使用Keil对STM32系列单片机开发时&#xff0c;如果使用的是库函数&#xff0c;那么不同型号单片机的工程项目文件是可以直接移植的。只需要按照下面的步骤修改对应的芯片&#xff0c;就可以直接将工程移植过去&a…
阅读更多...
JVM垃圾收集器--分区收集器

JVM垃圾收集器--分区收集器

G1收集器 属性 G1&#xff08;Garbage-First Garbage Collector&#xff09;在 JDK 1.7 时引入&#xff0c;在 JDK 9 时取代 CMS 成为了默认的垃圾收集器。G1 有五个属性&#xff1a;分代、增量、并行、标记整理、STW。 分代 G1收集器 将内部分为多个大小相等的区域&#x…
阅读更多...
Java8 Stream常见用法

Java8 Stream常见用法

Stream流的常见用法&#xff1a; 1.利用stream流特性把数组转list集合 //定义一个数组Integer[] array {5,2,1,6,4,3};//通过stream特性把数组转list集合List<Integer> list Arrays.stream(array).collect(Collectors.toList());//打印结果System.out.println(list);…
阅读更多...
全球数据爬取的解决方案-国外数据爬取

全球数据爬取的解决方案-国外数据爬取

引言 随着经济的持续低迷和对外贸易的需求扩大&#xff0c;各个公司为了更好的了解海外客户情况&#xff0c;最简单直接的办法就是从全球收集公共的网络数据。 无论是海外电商用户的消费习惯还是训练自己的通用人工智能chatgpt&#xff0c;都是需要海量和多种类型数据的支持。…
阅读更多...
【Linux】进程间通信（共享内存、消息队列、信号量）

【Linux】进程间通信（共享内存、消息队列、信号量）

一、System V —— 共享内存&#xff08;详解&#xff09; 共享内存区是最快的 IPC 形式。一旦这样的内存映射到共享它的进程的地址空间&#xff0c;这些进程间数据传递不再涉及到内核&#xff0c;换句话说&#xff0c;就是进程不再通过执行进入内核的系统调用来传递彼此的数…
阅读更多...
[NSSCTF]prize_p5

[NSSCTF]prize_p5

前言 之前就学过反序列化的字符串逃逸 但是没怎么做题 补一下窟窿 题目 <?phperror_reporting(0);class catalogue{public $class;public $data;public function __construct(){$this->class "error";$this->data "hacker";}public functi…
阅读更多...
HTTP网络协议的请求方法，具体详解（2024-04-26）

HTTP网络协议的请求方法，具体详解（2024-04-26）

1、HTTP 即超文本传输协议&#xff0c;是一种实现客户端和服务器之间通信的响应协议&#xff0c;它是用作客户端和服务器之间的请求 根据 HTTP 标准&#xff0c;HTTP 请求可以使用多种请求方法。 2、方法分类 HTTP1.0 定义了三种请求方法&#xff1a; GET, POST 和 HEAD 方…
阅读更多...
表情识别 | 卷积神经网络(CNN)人脸表情识别（Matlab）

表情识别 | 卷积神经网络(CNN)人脸表情识别（Matlab）

表情识别 | 卷积神经网络(CNN)人脸表情识别&#xff08;Matlab&#xff09; 目录 表情识别 | 卷积神经网络(CNN)人脸表情识别&#xff08;Matlab&#xff09;预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab使用卷积神经网络(CNN)&#xff0c;进行人脸表情情绪识别…
阅读更多...
论文解读：(CAVPT)Dual Modality Prompt Tuning for Vision-Language Pre-Trained Model

论文解读：(CAVPT)Dual Modality Prompt Tuning for Vision-Language Pre-Trained Model

v1文章名字&#xff1a;Dual Modality Prompt Tuning for Vision-Language Pre-Trained Model v2文章名字&#xff1a;Class-Aware Visual Prompt Tuning for Vision-Language Pre-Trained Model 文章汇总 对该文的改进&#xff1a;论文解读&#xff1a;(VPT)Visual Prompt …
阅读更多...
STM32H7 HSE时钟的使用方法介绍

STM32H7 HSE时钟的使用方法介绍

目录 概述 1 STM32H750 HSE时钟介绍 2 使用STM32Cube创建Project 3 认识HSE时钟 3.1 HSE时钟的特性 3.2 HSE的典型应用电路 4 STM32Cube中配置时钟 4.1 时钟需求 4.2 配置参数 4.2.1 使能外围资源 4.2.2 使用STM32Cube注意项 4.2.3 配置参数 5 总结 概述 本文主要…
阅读更多...
ESP-IDF编译系统详解（1）

ESP-IDF编译系统详解（1）

接前一篇文章&#xff1a;VSCode ESP-IDF安装与配置全过程 本文内容主要参考&#xff1a; 《ESP32-C3物联网工程开发实战》 —— 乐鑫科技 编著 特此致谢&#xff01; 前文已经详述了ESP-IDF开发环境的搭建&#xff0c;包括ESP-IDF的下载与安装完整流程&#xff0c;以及VSCo…
阅读更多...
【Docker】Docker 实践（一）：在 Docker 中部署第一个应用

【Docker】Docker 实践（一）：在 Docker 中部署第一个应用

Docker 实践&#xff08;一&#xff09;&#xff1a;在 Docker 中部署第一个应用 1.使用 YUM 方式安装 Docker2.验证 Docker 环境3.在 Docker 中部署第一个应用3.1 小插曲&#xff1a;docker pull 报 missing signature key 错误3.2 重新安装 Nginx 1.使用 YUM 方式安装 Docker…
阅读更多...
MySQL中脏读与幻读

MySQL中脏读与幻读

一般对于我们的业务系统去访问数据库而言&#xff0c;它往往是多个线程并发执行多个事务的&#xff0c;对于数据库而言&#xff0c;它会有多个事务同时执行&#xff0c;可能这多个事务还会同时更新和查询同一条数据&#xff0c;所以这里会有一些问题需要数据库来解决 我们来看…
阅读更多...
IoT Scenario: Smart Retail System-Multiple Sources and Multiple Terminals

IoT Scenario: Smart Retail System-Multiple Sources and Multiple Terminals

物联网/大数据可视化领域发文可以联系&#xff1a;nascimsina.com IoT Scenario: Smart Retail System Overview The use of IoT in the retail industry enhances customer experiences, optimizes inventory management, and provides valuable insights into consumer beh…
阅读更多...
【HarmonyOS】Stage 模型 - 基本概念

【HarmonyOS】Stage 模型 - 基本概念

一、项目结构 如图1所示&#xff1a; 图1 从项目结构来看&#xff0c;这个应用的内部包含了一个子模块叫 entry&#xff0c;模块是应用的基本功能单元&#xff0c;它里面包含源代码、资源、配置文件等。 像这样的模块在应用内部可以创建很多。但模块整体来讲就分成两大类&am…
阅读更多...
js 实现记住密码功能

js 实现记住密码功能

这是我弄得一点源码 使用 js 记住密码 选了半天最后 选择了 js.cookie.min.js 实现的 当然 也加了一点 加密手段 用的 crypto-js 这个 自己封装了一下 感觉还行 以后能重复用的 二话不说 先放资源 &#xff1a; 这么多资源 不得给个赞 关注一下的 当然 最简单的就是…
阅读更多...
拖拽式工作流开发有什么突出优势？

拖拽式工作流开发有什么突出优势？

想要实现高效率的办公方式&#xff0c;可以试着了解低代码技术平台及拖拽式工作流开发的优势特点。具有好操作、好维护、够灵活、可视化界面操作等优势特点的低代码技术平台可以助力企业实现流程化办公&#xff0c;在发展越来越快速的今天&#xff0c;拖拽式工作流开发得到了很…
阅读更多...
陪丨玩丨系丨统前后端开发流程，APP小程序H5前后端源码交付支持二开！多人语音，开黑，线上线下两套操作可在一个系统完成！

陪丨玩丨系丨统前后端开发流程，APP小程序H5前后端源码交付支持二开！多人语音，开黑，线上线下两套操作可在一个系统完成！

100%全部源码出售 官网源码APP源码 管理系统源码 终身免费售后 产品免费更新 产品更新频率高 让您时刻立足于行业前沿 软件开发流程步骤及其作用&#xff1a; 软件开发是一个复杂而系统的过程&#xff0c;涉及多个环节&#xff0c;以下是软件开发的主要流程步骤及其作用…
阅读更多...
小程序使用阿里巴巴矢量图标库

小程序使用阿里巴巴矢量图标库

一、登录官网 www.iconfont.cn 二、在搜索框中搜索想要的图标&#xff0c;将鼠标移动到图标上会看到三个标记 可以使用下载&#xff0c;直接使用&#xff1a; 可以使用css文件使用&#xff1a; 首先点击购物车样式的选项&#xff0c;而后点击下图位置&#xff1a; 点击自己创…
阅读更多...
怎么排查K8S容器当中的Java程序内存泄露问题

怎么排查K8S容器当中的Java程序内存泄露问题

今天早上发现生产线其中的一个服务在凌晨的时候突然重启了&#xff0c;内存突然从1G升到1.8G&#xff0c;CPU使用量从0.1升到了0.28&#xff0c;说明在这个时间点&#xff0c;内存突增达到了限额以上&#xff0c;服务重启了。因为这个服务布署了多节点&#xff0c;这次重启对业…
阅读更多...
最新文章

Copyright @ 2022~2023