C/C++教程

2-3 树/红黑树(red-black tree)

本文主要是介绍2-3 树/红黑树(red-black tree),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2-3 tree

<img src="https://i.imgur.com/oKdeq5j.jpg" width=800 height=160 /> **2-3树节点**: 1. null节点,null节点到根节点的距离都是相同的,所以2-3数是平衡树 2. 2叉节点,有两个分树,节点中有一个元素,左树元素更小,右树元素节点更大 3. 3叉节点,有三个子树,节点中有两个元素,左树元素更小,右树元素更大,中间树介于两个父元素之间。 ![2叉节点](https://i.imgur.com/rfAJOPK.png) ![3叉节点](https://i.imgur.com/aqNFC10.png) 插入操作如下图所示 ![2-3tree插入操作](https://i.imgur.com/MkuZR33.png)

红黑树

红黑树可以理解为实现了2-3树的BST(binary search tree),它是一个自平衡树,保证在最坏的情况下的操作也是O(lg(n)) <font color='#FF0000' face='黑体'>特性:</font>

  1. 每个节点有一个颜色属性(红或黑)
  2. 根节点是黑色的
  3. 所有的null节点都是黑色的,从任何null节点到根节点所经过的黑色节点数目相同

查找操作与BST是相同的 插入规则如下:

  • 按BST的插入方法在null节点上建立新节点,新节点的颜色为红色
  • 如果有右子节点为红色,则左旋,右子节点变为父节点
  • 如果左子节点与左孙节点都为红色,则进行右旋,左字节的变为父节点
  • 如果两个节点的颜色都为红色,则翻转反色

操作流程如下图所示:

<img src="https://i.imgur.com/QqrUI06.jpg" width=780 height=450 />

  • 图左为插入节点c,先标记为红,因为a、c都为红节点,故颜色反转
  • 中间插入节点a,由于插入后a、b节点都为红色,按第3条规则需要进行右旋操作,b变成了新的父节点
  • 图右插入节点b,由于b在a的右边,故先进行左旋,然后又发现a、b同为红色,再进行右旋

<font color='#FF0000' face='黑体'>左旋:</font>

<img src="https://i.imgur.com/OWUbNFO.jpg" width=330 height=256 /> <img src="https://i.imgur.com/rwYXXvw.jpg" width=300 height=256 />

左图为左旋前,右图为左旋后,代码如下所示:

private Node rotateRight(Node h){
	assert isRed(h.right);
	Node x = h.right;		// 复制h的 右子树 为节点x
	h.right = x.left;		// 将x的左子树移动到h的右节点上(替代)
	x.left = h;				// 将修改后的h节点作为x的左节点(替代)
	x.color = h.color;		// x继承h的颜色
	h.color = RED;			// 将h节点的颜色设置为红色
	return x;				// 返回x节点作为新的父节点
}

右旋操作与之类似

<font color='#FF0000' face='黑体'>颜色反转:</font>

<img src="https://i.imgur.com/1Rz9ysY.jpg" width=340 height=210 /> <img src="https://i.imgur.com/dCvUf0P.jpg" width=340 height=210 />

左图为颜色翻转前,右图为操作之后,代码如下所示:

private void flipColors(Node h){
	assert !isRed(h);
	assert isRed(h.left);
	assert isRed(h.right);
	h.color = RED;				// 将父节点颜色改为红色
	h.left.color = BLACK;		// 将左右子节点颜色改为黑色,
	h.right.color = BLACK;
}

此处只实现了查找与插入,如要完整实现所有功能(还有删除),可以采用**左倾红黑树**(LLRB, Left-leaning red–black tree) 红黑树显示的demo


Reference

  1. wikipedia Red–black tree
这篇关于2-3 树/红黑树(red-black tree)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!