数据结构之红黑树

红黑树的概念

红黑树（Red-Black Tree）同AVL树一样, 也是一种自平衡的二叉搜索树, 但在每个结点上增加一个存储位表示结点的颜色, 可以是Red或Black, 通过对任何一条从根到叶子的路径上各个结点着色方式的限制, 红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的. (最长路径也不会超出最短路径的两倍, 因此红黑树的平衡性要求相对宽松. 没有AVL树那样严格)

红黑树的性质(重要)

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

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

 我们可以先来分析一种极端的情况,如果一颗红黑树有红有黑, 那它的最短路径一定是一条全黑的路径, 想要获取最长的路径, 就可以在此基础上继续添加红色结点, 因为只要红色结点不相邻, 添加红色结点能保证路径的黑色结点数不变, 那就可以创建一条一黑一红一黑一红..的路径, 这条路径就是最长的路径, 所以最长路径最多是最短路径的两倍, 不可能超过最短路径两倍, 最长的路径都超不过其它的路径更超不过.

另一个问题, 性质5中每个叶子结点都是黑色的(此处的叶子结点指的是空结点, 也被称为NIL节点), 有什么用？ 

 这个红黑树有多少条路径？

如果不带空的话, 我们可能会认为有5条, 但是这里计算路径其实应该走到空（NIL）,所以正确的应该是有11条路径, 我们可以认为这条规则就是为了更好的帮我们区分不同路径的。 

结点的黑高(黑色高度):从某结点出发(不含该结点)到达任一空叶结点的路径上经过的黑结点总数 .

有了AVL树, 为啥还要有红黑树?

对于一棵红黑树来说, 如果它里面全部的黑色结点一共有N个的话, 那它的最短路径长度就差不多是log{_{2}}^{N}, 然后整棵树的节点数量就是在N-2N之间

设红黑树的高度为h, 总结点数为n, 首先, 从任意节点出发, 到其子树的叶子节点的路径中黑色节点的数量称为该节点的黑高, 即bh, 设根节点为T,那么根节点的黑高就是bh(T), 假设一棵红黑树全部都是黑色节点, 那么它的黑高bh(T)就是它的树高，我们可得这样一棵树的结点数为（根据满二叉树的高度与节点数量的关系）:n = 2_{}^{bh(T)}-1, 我们还要考虑红色节点, 所以在此基础上加上红色节点的数量, 那么不论加几个红色节点, 只要增加, 一定满足下式: n >= 2_{}^{bh(T)}-1

根据红黑树的性质，我们可知根节点的黑高bh(T)至少为h/2    (h为树高)，也就是说: bh(T) >= h/2, 所以n >= 2_{}^{h/2} -1, 所以 h > = 2log{_{2}}^{n+1}.

AVL树
平衡标准比较严格：每个左右子树的高度差不超过1
最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整
红黑树
平衡标准比较宽松：没有一条路径会大于其他路径的2倍
最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40）
搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整
如何选择
搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

红黑树结构的定义

先来定义一下红黑树的结构： 

结点的颜色我们可以用一个枚举: 

enum COLOR
{
	RED,
	BLACK
};

结点的结构:

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _left;
	T _val;
	COLOR _col;

	RBTreeNode(const T& val)
		: _parent(nullptr)
		, _right(nullptr)
		, _left(nullptr)
		, _val(val)
		, _col(RED)
	{}

};

这里结点的颜色我们默认给的是红色, 为什么要选择红色, 黑色不可以吗？   

如果我们插入一个新结点给的是黑色, 那它一定会违反上面提到的红黑树的性质——每条路径上黑色结点的数量一致: 

因为原来每条路径黑色结点数量是相同的,现在新插入一个黑色结点的话, 那插入的这条路径会增加一个黑色结点, 但是其它路径数量不变, 所以其它所有的路径黑色结点数量都和这一条不相等, 这样再调整就比较麻烦了, 相当于影响了这棵树"全家"。

那如果我们插入结点默认给红色呢？
红色的话要看具体情况了:

如果它的父亲是黑色, 那就没问题, 不需要进行什么处理:


如果插入一个红色结点, 但是它的父亲也是红色, 那就出事了, 因为红黑树里面不能出现连续的红色结点,那这种情况就需要调整了:

但是这样的调整的代价相对来说比较小, 因为可能不需要改动全局, 只是改变一个局部, 下面再具体说.

树的结构: 

template<class T>
class RBTree
{
public:
    //成员函数
private:
	RBTreeNode<T>* _root = nullptr;
};

 插入

由于红黑树也是一种二叉搜索树, 是在二叉搜索树的基础上加上其平衡限制条件来实现平衡,所以红黑树插入的逻辑也根搜索二叉树一样：

如果插入的是根结点, 根结点要手动设置为黑色. 

​

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

	cur = new Node(kv);
	//cur->_col = RED; //默认cur就是红色
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent; //记得要链接父亲
	}
	else if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent; //记得要链接父亲
	}
	else
		assert(false);

    //下面是调整
    //....
}

根据颜色开始调整

对于红黑树来说, 插入新结点之后, 我们要检查红黑树的性质是否遭到破坏, 如果遭到破坏的话, 就需要进行相应的调整, 因为新节点的默认颜色是红色, 因此：

如果其双亲节点的颜色是黑色, 没有违反红黑树任何性质, 则不需要调整；
但当新插入节点的父亲节点是红色时, 就违反了性质不能有连续红色结点出现, 此时需要对红黑树的颜色进行调整:

 约定: cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

而出现连续的红色结点的情况可以分为2种:

1. cur为红, p为红, g为黑, u存在且为红 

2. cur为红, p为红, g为黑, u不存在或为黑

可以看到关键就在于叔叔结点, 为什么? 因为到这种情况了cur和parent此时一定是红色, grandfather结点一定是黑色, 唯一有区别的只是叔叔结点.

情况一: cur为红，p为红，g为黑，u存在且为红 

​

解决方式：将p,u改为黑, g改为红, 然后把g当成cur, 继续向上调整。 

​ 

​ 

可以看到叔叔为红的这种情况下只需要调整颜色就能又满足规则.

可以简单讨论一下子树路径黑结点和为1和2时候共有几种情况: 

当a,b,c,d,e都是0的时候,有四种情况:

​ 

当a,b,c,d,e都是1的时候:

​

while (parent && parent->_col == RED)
{
	Node* grandparent = parent->_parent;

	//parent在grandparent的左
	if (parent == grandparent->_left)
	{
		Node* uncle = grandparent->_right;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandparent->_col = RED;
			cur = grandparent;
			parent = cur->_parent;
		}
	}
    //如果parent在grandparent的右,逻辑类似
    else if (parent == grandparent->_right)
    {
	    Node* uncle = grandparent->_left;
	    if (uncle && uncle->_col == RED)
	    {
		    parent->_col = uncle->_col = BLACK;
		    grandparent->_col = RED;
		    cur = grandparent;
		    parent = cur->_parent;
	    }
    }
    _root->_col = BLACK;//不管中间调了多少次,最后的根一定是黑,
                        //如果被调整到根变红了,需要调为黑,如果没调到,重新赋值一遍也没有影响
}

parent颜色为黑不需要单独去判断, 因为本来就不需要任何操作, 根本不会进入循环.

情况二:  cur为红，p为红，g为黑，u不存在/u存在且为黑

 ​

说明: u的情况有两种

1.如果u节点不存在, 则cur一定是新插入节点, 因为此时c,a,b,d,e都是空, 因为要满足一个路径的黑色结点个数相同.

​

2.如果u节点存在, 则其一定是黑色的, 那么cur节点原来的颜色一定是黑色的, 上面看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

​

在这里又可以再细分为两种子情况:

1. p为g的左孩子,cur为p的左孩子(左左)和p为g的右孩子, cur为p的右孩子(右右).

2.  p为g的左孩子,cur为p的右孩子(左右)和p为g的右孩子, cur为p的左孩子(右左).

1.左左和右右 

那对于这种情况我们要进行的单旋转+变色.

旋转: 

为什么要旋转？

因为这种情况的话最长路径有可能已经超过最短路径的两倍了, 比如上面这个图如果如果d/e是空的话就已经超过了, 所以要先旋转降高度, 再去调整颜色使它符合红黑树.

进行什么旋转呢？

那就要看具体情况了, 其实还是我们AVL树那里的四种情况:

当前我们是 p为g的左孩子, cur为p的左孩子, 是在较高左子树的左侧插入(左左), 所以要进行的旋转是右单旋;

同理p为g的右孩子, cur为p的右孩子,是在较高右子树的右侧插入(右右),进行左单旋.

变色:

变色的话不论那种旋转是统一的:p、g变色–p变黑，g变红

​

为什么不直接把cur变黑呢?

这样也满足路径黑结点和保持不变啊: 

​ 

此时parent的颜色又变成了红色, 又需要再继续向上调整, 而一开始的方法中parent调整完就是黑的, 就结束了, 不需要再向上调整, 更简便!

代码: 

while (parent && parent->_col == RED)
{
	Node* grandparent = parent->_parent;

	//parent在grandparent的左
	if (parent == grandparent->_left)
	{
		Node* uncle = grandparent->_right;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandparent->_col = RED;
			cur = grandparent;
			parent = cur->_parent;
		}
		else
		{
			if (cur == parent->_left)
			{
				rotateR(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
			}
		}
	}

	//parent在grandparent的左
	else if (parent == grandparent->_right)
	{
		Node* uncle = grandparent->_left;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandparent->_col = RED;
			cur = grandparent;
			parent = cur->_parent;
		}
		else
		{
			if (cur == parent->_right)
			{
				rotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
			}
		}
	}
	_root->_col = BLACK;
}

这里的旋转复用AVL的旋转即可, 去掉更新平衡因子的部分. 

2.左右和右左

双旋+变色 

前提条件根上面一样，还是cur为红，p为红，g为黑，u不存在/u存在且为黑 

''

进行什么旋转呢？ 

1.p为g的左孩子，cur为p的右孩子，则针对p做左单旋, g作右单旋
2.相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋, g作左单旋.

以左右单旋图中为例, 先进行一个左单旋: 

再进行一个右单旋: 

 再变色:

这样就调整好了 

代码: 

while (parent && parent->_col == RED)
{
	Node* grandparent = parent->_parent;
	//parent在grandparent的左
	if (parent == grandparent->_left)
	{
		Node* uncle = grandparent->_right;
        //叔叔存在且为红直接变色
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandparent->_col = RED;
			cur = grandparent;
			parent = cur->_parent;
		}
        //叔叔不存在或者叔叔是黑进行旋转
		else
		{
            /右单旋
			if (cur == parent->_left)
			{
				rotateR(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
			}
            //左右双旋
			else if (cur == parent->_right)
			{
				rotateL(parent);
				rotateR(grandparent);
				grandparent->_col = RED;
				cur->_col = BLACK;
			}
		}
	}

	//parent在grandparent的左
	else if (parent == grandparent->_right)
	{
        //叔叔存在且为红直接变色
		Node* uncle = grandparent->_left;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandparent->_col = RED;
			cur = grandparent;
			parent = cur->_parent;
		}
        //叔叔不存在或者叔叔是黑进行旋转
		else
		{
            //左单旋
			if (cur == parent->_right)
			{
				rotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
			}
            //右左双旋
			else if (cur == parent->_left)
			{
				rotateR(parent);
				rotateL(grandparent);
				grandparent->_col = RED;
				cur->_col = BLACK;
			}
		}
	}
	_root->_col = BLACK;
}

红黑树的测试

验证其为搜索二叉树

首先我们还是先来验证他是否是二叉搜索树，看它中序是否有序就行了:

void InOrderPrint()
{
	_InOrder(_root);
}

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}
int main()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrderPrint();
	cout << endl;
	return 0;
}

顺序是正确的

 验证其是否平衡且满足红黑树性质

如何判断它是否满足是一棵红黑树呢？

其实就是去检查那几条规则（性质）:

1.首先结点颜色要么是黑色, 要么是红色, 这没什么好检查的。
2.然后根结点必须是黑色, 这个可以检查一下,如果根结点不是黑色（是红色）直接就不符合了

3.然后如果出现连续的红色结点, 那也不符合。
那怎么检查有没有出现连续红色结点呢？
我们可以去遍历这棵树, 然后遇到红色结点判断它的孩子是不是红色结点, 如果存在红色结点它的孩子也是红色, 那就不符合, 这样可以,但是不太好, 因为孩子的话要检查两个,而且结点的孩子有还有可能不存在, 为空, 那还得再加一个判断。
所以我们可以这样做: 遍历遇到红色结点我们去看它的父亲, 如果它的父亲也为红色那就不行。而判断父亲的话, 只有根结点没有父亲, 但是根结点是黑色的也不会去检查它。

bool IsBalance()
{
	if (_root == nullptr)
		return true;
	if (_root->_col == RED)
		return false;
	
	return _Check(_root);
}

bool _Check(Node* root)
{
	if (root == nullptr)
	{
		return true;
	}
	if (root->_col == RED && root->_parent->_col == RED)
		return false;
	return _Check(root->_left, blacknum, ref)
		&& _Check(root->_right, blacknum, ref);
}

然后还剩一个, 我们要检查每条路径黑色结点数量是否相等, 存在不相等的情况就不符合。
那这个要如何检查呢？
我们可以先求出一条路径的黑色结点数量, 把它作为基准值, 然后再递归求出每条路径的黑色结点数量和它比较, 如果存在不相等的情况, 就不符合, 不用管这个基准值是不是正确的, 只要其他路径和这个值不相同, 那就不符合.

bool IsBalance()
{
	if (_root == nullptr)
		return true;
	if (_root->_col == RED)
		return false;
	
    //找基准值,这里以最左路为基准
	Node* cur = _root;
	int ref = 0;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			ref++;
		}
		cur = cur->_left;

	}
    //定义一个blacknum来记录路径的黑色结点数目
	int blacknum = 0;
	return _Check(_root, blacknum,ref);
}

bool _Check(Node* root,int blacknum, const int ref)
{
	if (root == nullptr)
	{
        //root为空说明该路径已经找完,开始比较blacknum和ref,不相等就不符合
		if (blacknum != ref)
			return false;
		return true;
	}
    //如果节点是黑的blacknum就++
	if (root->_col == BLACK)
		blacknum++;
    //结点是红色判断它与父亲结点是否为连续的红
	if (root->_col == RED && root->_parent->_col == RED)
		return false;
    //继续判断左右子树
	return _Check(root->_left, blacknum, ref)
		&& _Check(root->_right, blacknum, ref);
}

 注意这里的blacknum传递的非常巧妙, 因为每一层的blacknum都是独立的, 所以向下一层传递blacknum的后blacknum的修改不会影响上一层, 为什么不想去影响上一层呢? 因为上一层的blacknum传递给了左子树后还要传递给右子树进行判断, 在左子树中修改了上一层的值那再传给右子树就一定错了.

大量随机数构建红黑树进行测试 

int main()
{
	const int N = 10000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	cout << "Insert_time:" << end2 - begin2 << endl;
	cout << t.IsBalance() << endl;
	return 0;
}

 

插入和查找的时间测试: 

Node* Find(const pair<K, V>& kv)
{
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}
int main()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	size_t begin1 = clock();
		for (auto e : v)
		{
			t.Find(make_pair(e,e));
		}
	size_t end1 = clock();
	
	cout << "Find_time:" << end1 - begin1 << endl;
	cout << "Insert_time:" << end2 - begin2 << endl;
	cout << "是否平衡:"<<t.IsBalance() << endl;
	return 0;
}

 

插入相同数量随机数比较AVL树和红黑树的高度 

void test3()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand()+i);
	}

	RBTree<int, int> rbt;
	AVLTree<int, int> avlt;
	for (auto e : v)
	{
		rbt.Insert(make_pair(e, e));
		avlt.Insert(make_pair(e, e));
	}
	cout << "插入了" << rbt.Size() << "个值" << endl;
	cout << "红黑树高度: " << rbt.Height()<<endl;
	cout << "AVL树高度: " << avlt.Height() << endl;

}

当N为10w: 

插入10万个数据, 对产生的随机数都加个i(减少重复值), 我们看到就有一些差异了 

当N为100w:

 

100w个数据的差异就更大了, 还是红黑树要高一点

可以发现AVL树对平衡的控制是比较严格的, 而红黑树是相对宽松的。 

红黑树的删除

简单分析:

删除节点一定都在最后一到两层, 因为上层都可以替代下去.

结点有红色节点和黑色节点, 我们就以删除节点的颜色来区分删除操作的所有情况

删除红色节点

如果删除的节点是红色直接删除, 不用作任何调整。因为删除最后一层的红色节点, 并没有影响红黑树的任何性质。

删除黑色节点

有3种情况：

1. 拥有 2 个红色子节点的黑色节点

不可能被直接删除，因为会找它的子节点替代删除，因此不用考虑这种情况

2. 拥有 1 个红色子节点的黑色节点

修复步骤总结：

  1. 用删除节点的唯一子节点对其进行替代
  2. 将替代节点染成黑色

3. 黑色叶子节点

1. 删除节点为根节点, 直接删除该节点, 无需做其他操作。

2. 删除节点的兄弟节点为黑色 

2.1兄弟节点至少有1个红色子节点

        2.1.1 兄弟节点有一个右子节点：

        2.1.2 兄弟节点有一个左子节点：

        2.1.3 兄弟节点有两个左右子节点：

修复步骤总结：

        1 进行旋转操作

        2 旋转之后的中心节点继承父节点（删除节点的父节点）的颜色

        3 旋转之后的左右节点染为黑色

2.2 兄弟节点没有红色子节点

        2.2.1父节点为红色

        2.2.2父节点为黑色

修复步骤总结：

  1. 父节点向下与兄弟节点进行合并
  2. 将兄弟染成红色、父节点染成黑色即可修复红黑树性质
    • 如果父节点是黑色，直接将父节点当成被删除的节点处理，来修复父节点的下溢情况

3. 删除节点的兄弟节点为红色    

修复步骤总结：

  1. 兄弟节点染成 BLACK, 父节点染成染成 RED, 对父节点进行右旋
  2. 于是又回到兄弟节点是黑色的情况（侄子节点变为兄弟节点），继续使用兄弟节点为黑色的方法进行修复

 具体可查看:

【精选】【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树_小七mod的博客-CSDN博客

完整代码:

#pragma once
#include<assert.h>
enum COLOR
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _parent;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _left;
	pair<K,V> _kv;
	COLOR _col;

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

};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:
	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;
			}
		}

		cur = new Node(kv);
		//cur->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
			assert(false);
		
		//插入完成, 调整颜色
		parent的颜色是黑,不需要调整
		//if (parent->_col == BLACK)
		//{
		//	return true;
		//}
		//parent的颜色是红,需要调整
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			//parent在grandparent的左
			//		 g			      g
			//   p	u		   p 	  u
			//c					  c
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					//		 g
					//   p	u
					//c
					if (cur == parent->_left)
					{
						rotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					//		 g
					//   p	u
					//      c
					else if (cur == parent->_right)
					{
						rotateL(parent);
						rotateR(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK;
					}
				}
			}
			//parent在grandparent的左
			//		 g			      g
			//   u 	p		   u 	  p
			//				c			c
			else if (parent == grandparent->_right)
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					//		 g
					//   u		p
					//				c
					if (cur == parent->_right)
					{
						rotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					//		 g
					//   u		p
					//      c
					else if (cur == parent->_left)
					{
						rotateR(parent);
						rotateL(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK;
					}
				}
			}
			_root->_col = BLACK;
		}
		return true;
	}

	void InOrderPrint()
	{
		_InOrder(_root);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		
		Node* cur = _root;
		int ref = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				ref++;
			}
			cur = cur->_left;

		}
		int blacknum = 0;
		return _Check(_root, blacknum,ref);
	}

	Node* Find(const pair<K, V>& kv)
	{
		Node* cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	int Height()
	{
		return _Height(_root);
	}

private:
	Node* _root = nullptr;

	bool _Check(Node* root,int blacknum, const int ref)
	{
		if (root == nullptr)
		{
			if (blacknum != ref)
				return false;
			return true;
		}
		if (root->_col == BLACK)
			blacknum++;
		if (root->_col == RED && root->_parent->_col == RED)
			return false;
		return _Check(root->_left, blacknum, ref)
			&& _Check(root->_right, blacknum, ref);
	}

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

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

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

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

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

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

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

		subL->_right = parent;
		parent->_left = subLR;

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

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

 test.cpp:

#include <iostream>
#include <vector>
using namespace std;
#include "RBTree.h"
#include "AVL.h"

void test1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrderPrint();
	cout << endl;
	cout << t.IsBalance() << endl;
}

void test2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	size_t begin1 = clock();
	for (auto e : v)
	{
		t.Find(make_pair(e, e));
	}
	size_t end1 = clock();

	cout << "Find_time:" << end1 - begin1 << endl;
	cout << "Insert_time:" << end2 - begin2 << endl;
	cout << "是否平衡:" << t.IsBalance() << endl;
}

void test3()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand()+i);
	}

	RBTree<int, int> rbt;
	AVLTree<int, int> avlt;
	for (auto e : v)
	{
		rbt.Insert(make_pair(e, e));
		avlt.Insert(make_pair(e, e));
	}
	cout << "红黑树高度: " << rbt.Height()<<endl;
	cout << "AVL树高度: " << avlt.Height() << endl;

}
int main()
{
	test3();
	return 0;
}

 

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

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

相关文章

Vue23组件自定义事件 和 解绑事件

Vue23组件自定义事件 和 解绑事件

Vue2&3组件自定义事件 和 解绑事件 Vue2组件自定义事件 功能&#xff1a;父组件绑定数据&#xff0c;子组件触发事件。&#xff08;父绑子触发&#xff09; 实现步骤&#xff08;前三步在父组件实现&#xff0c;第四步在子组件实现&#xff09;&#xff1a; 第一步&#…
阅读更多...
测试用例的设计方法（黑盒）

测试用例的设计方法（黑盒）

1.基于需求的设计方法 比如针对网易邮箱进行测试&#xff1a;分为功能相关和非功能相关两大类 但是这么设计的话&#xff0c;有无数多个测试用例&#xff0c;我们现在看到的只是一些大概的测试用例&#xff0c;要想设计具体的测试用例&#xff0c;需要用到下面测试用例的方法…
阅读更多...
盘点双11！阿里妈妈助这些品牌短视频赢增长！

盘点双11！阿里妈妈助这些品牌短视频赢增长！

刚刚&#xff01;一年一度的双11落下帷幕&#xff0c;很多新变化值得回味。 尽管天气在变凉&#xff0c;但市场出现了逐渐回暖的迹象。在此背景下&#xff0c;大量商家特别关心如何在双11打一场漂亮的胜仗。 卖方如何行动&#xff0c;关键在于买方的变化。在阿里妈妈发布的《…
阅读更多...
神经网络（第二周）

神经网络（第二周）

一、简介 1.1 需求预测示例 1.1.1 逻辑回归算法 根据价格预测商品是否畅销。特征&#xff1a;T恤的价格&#xff1b;分类&#xff1a;销售量高1/销售量低0&#xff1b;使用逻辑回归算法进行分类&#xff0c;拟合效果如下图所示&#xff1a; 1.1.2 神经元和神经网络 将逻辑回…
阅读更多...
【LeetCode刷题-二分查找】--162.寻找峰值

【LeetCode刷题-二分查找】--162.寻找峰值

162.寻找峰值 方法一&#xff1a;寻找最大值 题目保证了nums[i]≠nums[i1]&#xff0c;所以数组nums中最大值两侧的元素一定严格小于最大值本身&#xff0c;因此最大值所在的位置就是一个可行的峰值位置 class Solution {public int findPeakElement(int[] nums) {int idx 0…
阅读更多...
分类网络搭建示例

分类网络搭建示例

搭建CNN网络 本章我们来学习一下如何搭建网络&#xff0c;初始化方法&#xff0c;模型的保存&#xff0c;预训练模型的加载方法。本专栏需要搭建的是对分类性能的测试&#xff0c;所以这里我们只以VGG为例。 请注意&#xff0c;这里定义的只是一个简陋的版本&#xff0c;后续一…
阅读更多...
什么是数据库事务、事务的ACID、怎么设置/禁止自动提交？

什么是数据库事务、事务的ACID、怎么设置/禁止自动提交？

数据库事务及ACID 数据库事务是指作为单个逻辑工作单元执行的一组操作。这组操作要么全部成功地执行&#xff0c;要么全部不执行&#xff0c;不允许出现部分执行的情况。数据库事务通常需要满足ACID属性&#xff0c;即原子性&#xff08;Atomicity&#xff09;、一致性&#x…
阅读更多...
第2关：还原键盘输入(list)

第2关：还原键盘输入(list)

题目&#xff1a; 知识点&#xff1a; 列表list相较于数组&#xff1a; 优势&#xff1a;可在任意指定位置插入或者删除元素而不影响列表其他地方 。 劣势&#xff1a;无法直接进行下标索引&#xff0c;需要迭代器it逐个遍历。 代码&#xff1a; #include <iostream>…
阅读更多...
企业级信息化系统 ERP、OA、CRM、EAM、WMS、MES、PM

企业级信息化系统 ERP、OA、CRM、EAM、WMS、MES、PM

微服务架构&#xff0c;前端采用微应用架构&#xff0c;可做到不同服务使用不同数据库独立运行。全平台采用基于模型驱动的设计模式&#xff0c;并在前后端留有大量的代码植入入口&#xff0c;方便开发者对平台进行改造扩充。企业信息中心开发ERP、OA、CRM、EAM、WMS、MES、PM等…
阅读更多...
R系组播调优方案

R系组播调优方案

修改/etc/sysctl.conf添加如下内容&#xff1a; Vim /etc/sysctl.con net.ipv4.ip_forward1 net.ipv4.ip_nonlocal_bind1 net.ipv4.conf.all.rp_filter0 net.ipv4.conf.default.rp_filter0 net.bridge.bridge-nf-call-arptables 0 net.bridge.bridge-nf-call-ip6tables 0 …
阅读更多...
【踩坑】Putty报错: Can’t agree a key change algorithm

【踩坑】Putty报错: Can’t agree a key change algorithm

原因可能是putty版本太老了&#xff0c;更新putty就好了 下载地址&#xff1a;https://www.chiark.greenend.org.uk/~sgtatham/putty/latest.html 根据需要选择自己想要下载的版本&#xff0c;我是下载的如下图所示的版本。 另外&#xff0c;了解了一下Putty是用来远程连接…
阅读更多...
用excel计算一个矩阵的逆矩阵

用excel计算一个矩阵的逆矩阵

假设我们的原矩阵是一个3*3的矩阵&#xff1a; 125346789 我们现在要求该矩阵的逆矩阵&#xff1a; 鼠标点到其它空白的地方&#xff0c;用来存放计算结果&#xff1a; 插入-》函数&#xff1a; 选择MINVERSE函数&#xff0c;这个就是求逆矩阵的函数&#xff1a; 点击“继续…
阅读更多...
怎么改变容易紧张的性格？

怎么改变容易紧张的性格？

容易紧张的性格是比较通俗的说法&#xff0c;在艾森克人格测试中&#xff0c;容易紧张的性格就属于神经症人格&#xff0c;神经质不是神-经-病&#xff0c;而是一种人格特征&#xff0c;这种特征包括&#xff1a;敏感&#xff0c;情绪不稳定&#xff0c;易焦虑和紧张。有兴趣的…
阅读更多...
中国电子学会2023年09月份青少年软件编程Python等级考试试卷六级真题(含答案)

中国电子学会2023年09月份青少年软件编程Python等级考试试卷六级真题(含答案)

2023-09 Python六级真题 分数&#xff1a;100 题数&#xff1a;38 测试时长&#xff1a;60min 一、单选题(共25题&#xff0c;共50分) 1. 以下选项中&#xff0c;不是tkinter变量类型的是&#xff1f;&#xff08;D　&#xff09;(2分) A.IntVar() B.StringVar() C.Do…
阅读更多...
Redis缓存穿透、击穿和雪崩

Redis缓存穿透、击穿和雪崩

文章目录 前言一、缓存穿透&#xff08;查不到&#xff09;1.概念2.解决方案布隆过滤器缓存空对象 二、缓存击穿&#xff08;量太大&#xff0c;缓存过期&#xff01;&#xff09;1.概述2.解决方案1.设置热点数据永不过期2.加互斥锁 三、缓存雪崩1.概念2.解决方案1.redis高可用…
阅读更多...
Xilinx DDR3 MIG系列——ddr3控制器的时钟架构

Xilinx DDR3 MIG系列——ddr3控制器的时钟架构

本节目录 一、ddr3控制器的时钟架构 1、PLL输入时钟——系统时钟system_clk 2、PLL输出时钟——sync_pulse、mem_refclk、freq_refclk、MMCM1的输入时钟 3、MMCM1的输入时钟和输出时钟 4、MMCM2的输入时钟和输出时钟一、ddr3控制器的时钟架构 对于FPGA开发来说，调用IP或者移植…
阅读更多...
PHP开源自动化平台CRUD代码生成器

PHP开源自动化平台CRUD代码生成器

生成CRUD&#xff08;创建、读取、更新、删除&#xff09;代码的实现方式有很多种&#xff0c; 一、实现方式 1. 定义数据模型&#xff1a;首先需要定义数据模型&#xff0c;包括表结构、字段以及数据类型等。 2. 自动生成数据库表&#xff1a;根据数据模型&#xff0c;使用数…
阅读更多...
利用爬虫采集外卖数据进行竞争对手分析

利用爬虫采集外卖数据进行竞争对手分析

目录 一、引言 二、准备工作 三、爬取数据 四、数据处理与存储 五、竞争对手分析 六、结论与展望 一、引言 在当今的数字化时代&#xff0c;数据已经成为企业成功的关键因素之一。对于餐饮外卖行业来说&#xff0c;数据的收集和分析尤为重要。通过对竞争对手的数据进行采…
阅读更多...
【LeetCode刷题笔记】滑动窗口

【LeetCode刷题笔记】滑动窗口

992. K 个不同整数的子数组 解题思路： 滑动窗口 ， 题目问题转化为： 求 「最多存在 K 个不同整数的子数组的个数」 与 「最多存在 K - 1 个不同整数的子数组的个数」 之差， 就是题目所求的 「恰好存在 K 个不同整数的子数组的个数」 ， 最终问题就变成求解滑动窗口内，以 R …
阅读更多...
webpack工作原理

webpack工作原理

目录 合并代码模块化webpack 的打包webpack 的结构webpack 的源码addEntry 和 _addModuleChainbuildModuleCompilation 的钩子产出构建结果 了解 webpack 实现原理&#xff0c;掌握 webpack 基础的工作流程&#xff0c;在平时使用 webpack 遇见问题时&#xff0c;能够帮助我们洞…
阅读更多...
最新文章

Copyright @ 2022~2023