手撕红黑树——C++高阶数据结构详解

目录

    • 传统艺能
    • 概念
    • 五大特性
    • 节点定义
    • 红黑树插入
    • 插入调整
      • 情况一
      • 情况二
        • 具体情况一
        • 具体情况二
        • 具体情况三
    • 验证红黑树
    • 红黑树查找
    • 红黑树的删除
    • 谁是一代宗师

传统艺能

小编是双非本科大一菜鸟不赘述,欢迎各位指点江山(期待~)(QQ:1319365055)
此前博客点我!点我!请搜索博主 【知晓天空之蓝】

非科班转码社区诚邀您入驻
小伙伴们,打码路上一路向北,彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是和梦想合伙人组建的社区,诚邀各位有志之士的加入!!
社区用户好文均加精(“标兵”文章字数2000+加精,“达人”文章字数1500+加精)
直达: 社区链接点我


手撕红黑树——C++高阶数据结构详解_第1张图片


红黑树是对树结构的一种高度综合运用,涉及到多叉树,树平衡调整,节点旋转等等,这些是对数据结构基本功的最佳历练,也是面试场上令人闻风丧胆的冷面一刀。能否给出完整的定义,能否介绍自己对红黑树的认识,能否通过旋转,染色等操作在给定的场景下对一颗红黑树进行调整使其符合定义…这些才是我们应该在学习后得到的信息

概念

红黑树也是一种二叉搜索树,但是每个节点都存储了一个颜色,该颜色可以为黑可以为红,因此也叫红黑树。

红黑树和 AVL 树的区别就是红黑树属于近似平衡,他并不是完全平衡,红黑树不会像 AVL 树一样做到严密的平衡(高度差控制在 1 ),他是依靠每条路径上红黑节点的排布与限制,确保最长路径长度不超过最短路径长度的 2 倍.

手撕红黑树——C++高阶数据结构详解_第2张图片

五大特性

红黑树有着标志性的五大特性

  1. 根节点一定为黑色
  2. 一个节点只能是红或黑
  3. 节点为红色,则该节点的两个子节点都为黑色
  4. 对于每个节点,从根节点到叶子结点的简单路径上,黑色节点个数相等
  5. 每个叶子结点(即空节点)都是黑色

那么问题来了,仅仅依靠这五大特性是如何确保最长路径长度 < 最短路径长度的 2 倍?

根据第 3,4 特性,我们不妨思考一下极端场景,最短可能路径其实就是全黑的情况,假设此时有 n 个节点,长度就为 n:

手撕红黑树——C++高阶数据结构详解_第3张图片

而最长可能路径就是在红色节点存在的条件下,以一红一黑的方式进行排列,此时假设依然有 n 个黑色节点,那么红色节点数目与黑色相同,则长度为 2n,以此证明。

节点定义

这里和 AVL 树一样我们直接实现 KV 模型,为了方便后序的旋转操作,将红黑树的结点定义为三叉链结构,将 AVL 树中的平衡因子换成了新成员——结点的颜色。

因为节点颜色是贯穿的,我们可以直接定义成全局变量,并用枚举变量来给颜色赋予逻辑:

enum Color 
{
   Red, //0
   Black  //1
};

接下来就可以定义节点了:

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv, Color color = Red)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _color(color)
	{}

	RBTreeNode<K,V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;//三叉链结构
	pair<K,V> _kv;//存储键值对
	Color _color;//节点颜色
};

注意这里有个细节:为什么构造结点时,默认将结点的颜色设置为红色?

因为我们要考虑插入场景,不论此时根节点为黑色还是红色,我们插入黑色节点,那么他一定会破坏性质 4 ,某条路径上的黑色节点一定会增加一个,那么为了维护结构,我们岂不是要给其他所有路径都加上一个黑色节点?但如果此时插入的是红色节点,如果根节点为红色,那么又会破坏性质 3 出现了连续的红色节点,但是如果根节点为黑色,就不需要进行调整。

这就是一个简单的伤害最小化理论:插入黑节点,一定会破坏性质 4,必须进行调整;插入红节点,可能破坏性质 3,可能进行调整,因此我们选择将插入节点定为红色。

红黑树插入

插入逻辑依然和二叉搜索树差不多,三步走:

  1. 按二叉搜索树的插入方法,找到待插入位置。
  2. 将待插入结点插入到树中。
  3. 若插入结点的父结点是红色的,则需要对红黑树进行调整。

插入的关键就在于这里的第三步,这调整里面有大学问。

插入调整

我们给出一个基本模型(可以是一个完整的树,也可以是一个子树):

手撕红黑树——C++高阶数据结构详解_第4张图片

并约定:

cur :当前节点
p:parent,父节点
g:grandfather,祖父节点
u:uncle,叔叔节点
a,b,c,d,e:子树

顺便提一下,树的路径不是一路走到叶子结点算一条,要走到空节点(NIL 节点)算一条:

手撕红黑树——C++高阶数据结构详解_第5张图片

比如上图中该红黑树的有效路径不是 4 条而是 9 条。

情况一

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

手撕红黑树——C++高阶数据结构详解_第6张图片

首先你需要知道,红黑树的调整关键看叔叔,因为节点的颜色是固定的,祖父存在且一定为黑,为什么?因为父节点为红色那么他一定不会是根,他一定有一个父节点且为黑,只有 u 节点不知道嘛情况。

我们调整并不是像 AVL 一样旋转,这里是进行变色,首先将叔叔变黑,此时就没有连续的红节点了,但是为了保持黑节点数目不变父亲也要变黑,万事大吉了吗?没有,紧接还要将祖父变红,为什么呀!?不要忘了,这里可能只是一个子树,叔叔父亲变黑了那么路径上黑节点就会多出一个,对整个结构必然有影响,所以还需要将祖父变红保持黑色数量不变。

手撕红黑树——C++高阶数据结构详解_第7张图片
最后不要忘了将祖父当成 cur 节点继续向上调整,因为在上一层父亲的颜色不知道,祖父改变可能违反规则还会继续调整。这种情况我们左右方向,翻转过来处理方法一样,只变色不旋转。

具体代码表示:

			while (parent != _pHead && parent->_color == Red)
			{
				Node* grandfather = parent->_parent;
				assert(grandfather);   //祖父节点有效性
				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right; //情况一叔叔在祖父右
					if (uncle && uncle->_color == Red) //叔叔在右且为红
					{
						parent->_color = Black;
						uncle->_color = Black; 
						grandfather->_color = Red; 
						cur = grandfather; //继续向上调整
						parent = cur->_parent;
					}
					else //叔叔为黑情况二
					{
                        ……
					}
				}
				else
				{
					Node* uncle = grandfather->_left;//左右翻转(叔叔在祖父左)不影响情况一,和上面一样处理
					if (uncle && uncle->_color == Red)
					{
						parent->_color = Black;
						uncle->_color = Black;
						grandfather->_color = Red;
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
                        ……
					}
				}
			}
		}

情况二

具体情况一

cur 为红,p 为红,g 为黑, u 存在且为黑
手撕红黑树——C++高阶数据结构详解_第8张图片

其实这里的 a,b,c 的情况就只有 4 种情况,只要有一个黑节点就能满足:

手撕红黑树——C++高阶数据结构详解_第9张图片

这种情况的 cur 节点一定不是新插入节点,cur 原来是黑色,他是第一种情况向上调整过程中,祖父节点形成的 cur 节点,为什么呢?

手撕红黑树——C++高阶数据结构详解_第10张图片

如上图所示,根据性质 4 假设祖父上面有 x 个黑节点,那么左子树(含祖父)现在是 x +1 个,右子树(含祖父)是 x + 2 + y 个,很明显 x + 2 + y > x + 1,因此在插入结点前就已经不满足要求了,所以说叔叔结点存在且为黑这种情况,一定是由情况一往上调整过程中才会出现的!

此时单纯使用变色已经无法处理了,这时我们需要进行旋转处理。若祖孙三代的关系是直线(cur、parent、grandfather这三个结点为一条直线),则一波 AVL 树里经典的旋转又来辣!这里左偏所以选择右单旋,再进行颜色调整,颜色调整后这棵被旋转子树的根结点是黑色的,且黑节点数量不变,因此无需继续往上进行处理。

手撕红黑树——C++高阶数据结构详解_第11张图片
但是此时翻转就不能像情况一一样一概而论了,反转过来偏右就要使用左单旋了。因此红黑树抽象逻辑就强在这里,能和 AVL 树契合到位的同时还能有机调整,AVL 树要是天才的话那么红黑树我只能叫他一声 lord 。

具体情况二

cur 为红,p 为红,g 为黑,u 不存在

手撕红黑树——C++高阶数据结构详解_第12张图片

在这种情况下的 cur 结点一定是新插入的结点,而不可能是由情况一变化而来的,因为叔叔不存在那么 parent 的下面也不可能再挂黑结点了。

既然产生了连续的红节点那就必须把其中一个变黑,总不能把插进去的红节点变黑吧,不然就变成插黑节点了,因此就在只能把 parent 变黑,但是这样子树就会多出黑节点有会破坏结构,怎么办呢?

和具体情况一同理了,祖孙三代在一条直线上偏左,一波右单旋安排,接着根节点变成 parent 后调整颜色,父亲变黑,祖父变红,一波完美升级后续也不需要再向上调整(黑节点数目不变,根节点颜色正常)。

手撕红黑树——C++高阶数据结构详解_第13张图片

具体情况三

该情况是具体情况一的区别版本,情况一是三世同堂即一条直线,这里是一条折线,他和情况二的区别就是情况二 p 在 g 的左,而 cur 是 p 的左 ,情况三 cur 在 p 的右:

手撕红黑树——C++高阶数据结构详解_第14张图片
那么不必多言,从 AVL 树过来的小伙伴一眼就明白该干什么了,没错,说白了就是单旋变双旋:

手撕红黑树——C++高阶数据结构详解_第15张图片

以上情况的完整如下:

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若红黑树为空树,则插入结点直接作为根结点
	{
		_root = new Node(kv);
		_root->_col = BLACK; //根结点必须是黑色
		return make_pair(_root, true); //插入成功
	}
	//找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			//key值小于当前结点的走左子树
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			//key值大于当前结点的走右子树
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值=当前结点
		{
			return make_pair(cur, false); //插入失败
		}
	}

	//插入到树中
	cur = new Node(kv); //构造结点
	Node* newnode = cur; //记录新插入的结点(便于后序返回)
	if (kv.first < parent->_kv.first)
	{
		//新结点的key值小于parent插入到左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		//新结点的key值大于parent插入到右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//若插入结点的父结点是红色的,则需要对红黑树进行调整
	while (parent&&parent->_col == RED)
	{
		Node* grandfather = parent->_parent; //parent是红色,则其父结点一定存在
		if (parent == grandfather->_left) //parent是grandfather的左孩子
		{
			Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
			if (uncle&&uncle->_col == RED) //情况1:uncle存在且为红
			{
				//颜色调整
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else //情况2+情况3:uncle不存在 + uncle存在且为黑
			{
				if (cur == parent->_left)
				{
					RotateR(grandfather); //右单旋

					//颜色调整
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else //cur == parent->_right
				{
					RotateLR(grandfather); //左右双旋

					//颜色调整
					grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break; 
			}
		}
		else //parent是grandfather的右孩子
		{
			Node* uncle = grandfather->_left; //uncle 是 grandfather 的左孩子
			if (uncle&&uncle->_col == RED) //情况1:uncle存在且为红
			{
				//颜色调整
				uncle->_col = parent->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else //uncle不存在/ uncle存在且为黑
			{
			    //         g
				//     p       u
				// cur
				if (cur == parent->_left)
				{
					RotateRL(grandfather); //右左双旋

					//颜色调整
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//        g
				//    u       p
				//        cur
				else 
				{
					RotateL(grandfather); //左单旋

					//颜色调整
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				break; //子树旋转后,该子树的根变成了黑色,无需继续往上进行处理
			}
		}
	}
	_root->_col = BLACK; //暴力处理根节点颜色,防止向上处理根节点变红
	return make_pair(newnode, true);
}

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	//建立subRL与parent之间的联系
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	//建立parent与subR之间的联系
	subR->_left = parent;
	parent->_parent = subR;

	//建立subR与parentParent之间的联系
	if (parentParent == nullptr)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}
}

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* parentParent = parent->_parent;

	//建立subLR与parent之间的联系
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	//建立parent与subL之间的联系
	subL->_right = parent;
	parent->_parent = subL;

	//建立subL与parentParent之间的联系
	if (parentParent == nullptr)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}
		subL->_parent = parentParent;
	}
}

//左右双旋
void RotateLR(Node* parent)
{
	RotateL(parent->_left);
	RotateR(parent);
}

//右左双旋
void RotateRL(Node* parent)
{
	RotateR(parent->_right);
	RotateL(parent);
}

(对旋转有疑惑的小伙伴请走传送门:手撕 AVL 树)

注意,最后根节点我们暴力处理颜色设为黑色,防止向上调整时将根节点变为了红色的情况。

验证红黑树

还是老套路,先来一手中序遍历看这棵树是否满足二叉搜索树性质:

void Inorder()
{
	_Inorder(_root);
}

void _Inorder(Node* root)
{
	if (root == nullptr)//空树也是红黑树
		return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}

然后要验证红黑树的整体结构,灵魂就在于是否满足五大特性

	Node* GetRoot()//取根节点函数
	{
		return _pHead->_parent;
	}
	
	bool IsValidRBTRee()
	{
		Node* pRoot = GetRoot();//取根节点
		if (pRoot == nullptr)//空树也是红黑树
			return true;
		if (pRoot->_color != Black)
		{
			cout << "违反性质一:根节点是黑色" << endl;
			return false;
		}
		size_t count = 0;
		Node* cur = pRoot;
		while (cur)//取最左路径的黑节点个数为验证标准
		{
			if (cur->_color == Black)
				count++;
			cur = cur->_left;
		}
		size_t pathB = 0;//记录需验证路径的黑节点个数
		return _IsValidRBTRee(pRoot, count, pathB);//封装函数进行递归验证
	}
		
		bool  _IsValidRBTRee(Node* pRoot, size_t count, size_t pathB)
		{
			if (pRoot == nullptr)
				return true;
			if (pRoot->_color == Black)
				pathB++;
			Node* parent = pRoot->_parent;//遇到红节点检查其父亲(红节点一定存在父亲)
				if (parent->_color == Red && parent != _pHead && pRoot->_color == Red)
				{
					cout << "违反性质3:不能存在连在一起的红色节点" << endl;
					return false;
				}
			if (pRoot->_left == nullptr && pRoot->_right == nullptr)
			{
				if (pathB != count)
				{
					cout << "违反性质4:每条路径中黑色节点个数均相同" << endl;
					return false;
				}
			}
			return _IsValidRBTRee(pRoot->_left, count, pathB) && _IsValidRBTRee(pRoot->_right, count, pathB);
		}

红黑树查找

红黑树的查找函数与二叉搜索树的查找方式一模一样,四步走:

若树为空树,则查找失败,返回nullptr。
若key值小于当前结点的值,则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值,则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值,则查找成功,返回对应结点。

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

红黑树的删除

还是在 AVL 树说的,高阶数据结构概不展示删除部分,过于打脑壳有兴趣的自行查阅即可。

手撕红黑树——C++高阶数据结构详解_第16张图片

谁是一代宗师

AVL 树和红黑树都是平衡二叉树的两个老大哥,他们增删查改的时间复杂度都是 O(logN),到底谁更技高一筹?

其实在大数据的场景下,比如百万级量化数据,AVL 需要构建大约 20 多层,同时红黑树需要构建大约 40 多层,毕竟红黑树是近似平衡的二叉搜索树。

但是我们知道 20 和 40 在 CPU 运算速度面前并没有什么差别,虽然 AVL 树在效率上会略胜红黑树一点点,但是生活中红黑树的运用却比 AVL 树更为广泛,因为 AVL 树的效率是有代价的,是充分牺牲结构进行不断旋转得到的,而红黑树大大降低了旋转次数会更安全因此,换来了更优的性能

aqa 芭蕾 eqe 亏内,代表着开心代表着快乐,ok 了家人们。

你可能感兴趣的