目录

红黑树那点事儿

前置知识:二叉查找树、B树,本文不多做介绍。

0. 写在前面

在观察和思考红黑树时,一定要牢记:红黑树是一颗平衡二叉查找树,我们所赋予红黑树的一切行为,都是为了使其能够保持平衡性。

红黑树是由2-3-4树(4阶B树)等价过来的(当然也有由2-3树等价来的左倾或右倾红黑树),而这层等价关系,是我们用以维持红黑树平衡性的根本。

https://i.loli.net/2021/05/06/h6DA5UabVoznLRC.jpg

在红黑树中,我们以黑色来标识对应B树里的2-结点,而红色结点表示其parent到自己的链接是一条红链接(向上融合后对应B树中的3-结点,若兄弟结点也是红色则一起向上融合对应4-结点

接下来我们来看看红黑树的五大性质:

  • 结点为红色或黑色
  • 根为黑色
  • NULL叶子结点均为黑色
  • 每个叶子结点到根的路径上不能有两个连续的红色结点
  • 完美黑色平衡

通过前面展示的等价关系,要推导出这几条性质不成问题。

1. 旋转以及颜色翻转的本质

首先我们要明确一个概念:旋转是作用于红链接的操作。那么,旋转操作到底给我们的红黑树带来了怎样的影响呢?

Ⅰ. 旋转

旋转分为左旋(left-rotate)和右旋(right-rotate):

  • 左旋:将右红链接转换为左红链接
  • 右旋:将左红链接转换为右红链接

https://i.loli.net/2021/05/06/PGNnhry5dsOc2D8.jpg

可以看到:在经过旋转操作后,我们可以调节某一侧黑色结点的平衡,而对应的2-3-4树结点并未发生任何变化。

Ⅱ. 颜色翻转(flip-color)

颜色翻转其实对应的是2-3-4树4-结点需要分裂时的情况:一个新的KEY想要加入4-结点,会导致原有的4-结点分裂,原来中间的KEY会提到上层进行融合。

https://i.loli.net/2021/05/06/AbkSlQLrFh2OIV1.jpg

当我们插入d时,会形成一个临时5-结点,这时原先的4-结点将分裂,将b提上去进行融合(标为红色),当然,若此时b已经成为根节点,则进一步标为黑色。可以看到,我们通过简单的颜色翻转即可达到2-3-4树中结点分裂的效果。

2. 平衡性维持

在我们按照二叉查找树的规则做完插入或删除操作之后,就要通过观察对应2-3-4树中的变化,对我们的红黑树进行等价的操作从而恢复对应关系(即维持红黑树的平衡性)。

Ⅰ. 插入后的平衡性维持

新的结点作为红色叶子结点插入到树中,无非为以下4种情况:

a. 新增一个2-结点

https://i.loli.net/2021/05/06/Zdvp5jHaSq8JYEc.jpg

如果新增的2-结点将作为根节点,则将其进一步标为黑色。

b. 与一个2-结点合并成为3-结点

https://i.loli.net/2021/05/06/JFkmLxbgrQTlit8.jpg

即新结点的parent结点为黑色,无需调整。

c. 与一个3-结点合并成为4-结点

https://i.loli.net/2021/05/06/bJQ1nCwpxGOEVHI.jpg

  • 图中黑色虚线方框内是插入新节点时其parent结点以及grandparent结点可能的情形
  • 橙色三角标所指表示我们新插入的结点的位置

可能会出现连续两条红链接的情况,这时需要通过旋转操作进行调整(为上图下半部分的形式)。

d. 与一个4-结点进行合并, 4-结点需要分裂(颜色翻转)

https://i.loli.net/2021/05/06/jwYiLDSHAP2huCB.jpg

Ⅱ. 删除后的平衡性维持

删除操作同BST大体相同,不过在我们的代码实现里,被删除的永远是一个替代结点。因为红黑树由2-3-4树等价而来,我们要充分对其性质进行利用。

那么替代结点究竟如何得到呢?我们先查找到指定删除的结点d,如果该结点有两个孩子,则替代结点为其前驱或后继结点;如果该结点只有一个孩子,该孩子就是替代结点;若d没有孩子(即d为根结点),则替代结点就是其本身。

因为2-3-4树的完美平衡性质,我们可以得到一个结论:真正被删除的元素一定是2-3-4树中的叶子节点中的KEY,也即在红黑树中删除的(替代结点)一定是叶子节点或者叶子结点上面的双亲结点(最多只有一个孩子)。

进一步得出以下推论:若替代结点的左孩子不为空,则替代结点一定是一个前驱结点;反之,是一个后继结点。删除后用其子节点替代自己的位置。

而这又对应了2-3-4树中叶子结点的状况:

  • 2-结点:删除后兄弟够借,经过双亲借;兄弟不够,啃老来凑
  • 2-结点:自己足够,直接删除

而后我们的删除策略就变成了(以用前驱结点替代为例):

  • 若删除的替代结点有孩子,且替代结点为黑色,将孩子变为黑色来替代自己
  • 删除的是一个叶子节点,且这个替代结点为黑色,在删除前先进行平衡修复(避免提前删除导致信息丢失)

接下来讨论上述第二种情况:需要平衡修复的情况。

a. 兄弟够借

向兄弟结点借之前得先知道兄弟手里够不够吧,所以需要找到真正的兄弟结点,因为若当前替代结点的兄弟是红色结点的话,对应2-3-4树,在红黑树中根本不是真正的兄弟结点。如下图第二种情况(图中p表示parent结点哦):

https://i.loli.net/2021/05/06/ovUeGrXcxKSFwu5.jpg

这时我们只需对替代结点的parent结点做一次旋转操作即可(出现红链接了),如下所示:

https://i.loli.net/2021/05/06/jgHPDvSGsUh86Ip.jpg

找到真正的兄弟结点之后,如果兄弟结点的孩子中有红色结点,就对应了2-3-4树中非2-结点可借的情况。

既然兄弟够借,那么对应2-3-4树中,就是兄弟中KEY最接近自己的上去顶替parentparent下来顶替被删的结点。

为了实现起来简单,这里有一个小trick:通过旋转将兄弟与兄弟孩子结点达到某种关系后,再旋转parent结点。这样做可以达到在对应2-3-4树中如果有兄弟有两个孩子就从兄弟那里借两个来的效果,而且可以大大的简化我们的代码。

例如被删结点是其parent的左孩子,找到其真正的右兄弟后,如果右兄弟有两个红色子节点,直接旋转parent,这样,兄弟结点中只会留下右孩子(较大的KEY),兄弟结点上升代替parentparent与兄弟左孩子下来代替删除的结点,左孩子没有的话也没关系;另一种需要提前调整的情况是,右兄弟只有一个左孩子可借,这时候我们对右兄弟进行右旋后再对parent进行左旋即可。

然而我们前面说:旋转操作是针对红链接的。然而我们在这里其实很幸运地跳出了这个规则的束缚,只需做小许额外的步骤:

  • parent旋转之后, 兄弟顶上去替代parent的位置, 兄弟被染成了parent原来的颜色 —— 上去顶替,没毛病

  • parent变成了红色,不过因为parent是下来顶替被删的黑色结点,故需将其染成黑色

  • 最后,将兄弟结点之前的右孩子标为黑色 —— 只剩下它了,作为一个2-结点

若被删结点是其parent的右孩子,把上面的逻辑反过来左右对调即可。

如果真兄弟结点的两个孩子均为黑色,就对应了2-结点、不可借的情况,我们将在下面继续进行讨论。

b. 兄弟不够

兄弟无法借过来,对应2-3-4树中,兄弟就得找parent合并。所以直接将兄弟结点变成红色,交由上层解决。若parent也是红色,就把parent变成黑色。若parent本身就是黑色,就得让parent再找他自己的兄弟结点借。

https://i.loli.net/2021/05/08/ElLRvKUJpHVMZmk.jpg

3. 代码实现

  1package rbt
  2
  3const (
  4	RED   = true
  5	BLACK = false
  6)
  7
  8type (
  9	// KeyType is the type with CompareTo behavior.
 10	KeyType interface {
 11		CompareTo(c interface{}) int
 12	}
 13
 14	// KeyTypeInt is the int that implements the KeyType interface.
 15	KeyTypeInt int
 16
 17	// node is the red-black tree node
 18	node struct {
 19		Key    KeyType
 20		Val    interface{}
 21		Color  bool
 22		Left   *node
 23		Right  *node
 24		Parent *node
 25	}
 26
 27	// RBT is the red-black tree
 28	RBT struct {
 29		root *node
 30		size int
 31	}
 32)
 33
 34// CompareTo implementation for type KeyTypeInt
 35func (k KeyTypeInt) CompareTo(c interface{}) int {
 36	return int(k) - int(c.(KeyTypeInt))
 37}
 38
 39// isRed returns whether a node is in red color, nil is black
 40func isRed(n *node) bool {
 41	if n == nil {
 42		return BLACK
 43	}
 44	return n.Color
 45}
 46
 47// NewRBT returns a red-black tree
 48func NewRBT() *RBT {
 49	return &RBT{}
 50}
 51
 52// treeMin find the minimum node in n's sub-tree
 53// func (n *node) treeMin() *node {
 54// 	for n.Left != nil {
 55// 		n = n.Left
 56// 	}
 57// 	return n
 58// }
 59
 60// treeMax find the maximum node in n's sub-tree
 61func (n *node) treeMax() *node {
 62	for n.Right != nil {
 63		n = n.Right
 64	}
 65	return n
 66}
 67
 68// predecessor returns n's predecessor node
 69func (n *node) predecessor() *node {
 70	if n == nil {
 71		return nil
 72	}
 73
 74	if n.Left != nil {
 75		return n.Left.treeMax()
 76	} else {
 77		p := n.Parent
 78		lc := n
 79		for p != nil && lc == p.Left {
 80			lc = p
 81			p = p.Parent
 82		}
 83		return p
 84	}
 85}
 86
 87// successor returns n's successor node
 88// func (n *node) successor() *node {
 89// 	if n == nil {
 90// 		return nil
 91// 	}
 92
 93// 	if n.Right != nil {
 94// 		return n.Right.treeMin()
 95// 	} else {
 96// 		p := n.Parent
 97// 		lc := n
 98// 		for p != nil && lc == p.Right {
 99// 			lc = p
100// 			p = p.Parent
101// 		}
102// 		return p
103// 	}
104// }
105
106// LeftRotate left rotate the node n, acting on a red link
107//
108//    p               p
109//    |               |
110//    n               m
111//   / \             / \
112//  nl  m    ==>    n  mr
113//     / \         / \
114//    ml mr       nl ml
115//
116func (t *RBT) leftRotate(n *node) {
117	m := n.Right
118	n.Right = m.Left
119	if m.Left != nil {
120		m.Left.Parent = n
121	}
122	m.Parent = n.Parent
123	if n.Parent == nil {
124		t.root = m
125	} else if n == n.Parent.Left {
126		n.Parent.Left = m
127	} else {
128		n.Parent.Right = m
129	}
130	m.Left = n
131	n.Parent = m
132	// repaint color
133	m.Color = n.Color
134	n.Color = RED
135}
136
137// RightRotate right rotate the node n, acting on a red link
138//
139//     p                p
140//     |                |
141//     n                m
142//    / \              / \
143//   m  nr    ==>     ml  n
144//  / \                  / \
145// ml mr                mr nr
146//
147func (t *RBT) rightRotate(n *node) {
148	m := n.Left
149	n.Left = m.Right
150	if m.Right != nil {
151		m.Right.Parent = n
152	}
153	m.Parent = n.Parent
154	if n.Parent == nil {
155		t.root = m
156	} else if n == n.Parent.Left {
157		n.Parent.Left = m
158	} else {
159		n.Parent.Right = m
160	}
161
162	m.Right = n
163	n.Parent = m
164	// repaint color
165	m.Color = n.Color
166	n.Color = RED
167}
168
169func (t *RBT) flipColors(n *node) {
170	n.Color = RED
171	n.Left.Color = BLACK
172	n.Right.Color = BLACK
173}
174
175// Search returns the node by the given key if it exists
176func (t *RBT) Search(key KeyType) *node {
177	root := t.root
178	for root != nil {
179		cmp := key.CompareTo(root.Key)
180		if cmp < 0 {
181			root = root.Left
182		} else if cmp > 0 {
183			root = root.Right
184		} else {
185			return root
186		}
187	}
188	return root
189}
190
191// Insert inserts a key with associated data(val) to a place in the red-black
192// tree by compare the keys, and if the key exists, update it with the new val.
193func (t *RBT) Insert(key KeyType, val interface{}) {
194	if t.root == nil {
195		t.root = &node{Key: key, Val: val}
196		t.size = 1
197		return
198	}
199
200	// find parent node to attach
201	root := t.root
202	var p *node
203	for root != nil {
204		p = root
205		cmp := key.CompareTo(root.Key)
206		if cmp < 0 {
207			root = root.Left
208		} else if cmp > 0 {
209			root = root.Right
210		} else {
211			root.Val = val
212			return
213		}
214	}
215
216	newnode := &node{Key: key,
217		Val:    val,
218		Color:  RED,
219		Parent: p,
220	}
221
222	cmp := key.CompareTo(p.Key)
223	if cmp < 0 {
224		p.Left = newnode
225	} else {
226		p.Right = newnode
227	}
228
229	t.insertFix(newnode)
230	t.size++
231}
232
233func (t *RBT) insertFix(n *node) {
234	var u *node // n's uncle node
235	for n.Parent != nil && isRed(n.Parent) {
236		if n.Parent == n.Parent.Parent.Left {
237			u = n.Parent.Parent.Right
238			if u != nil && isRed(u) {
239				n = n.Parent.Parent
240				t.flipColors(n)
241			} else {
242				if n == n.Parent.Right {
243					n = n.Parent
244					t.leftRotate(n)
245				}
246				t.rightRotate(n.Parent.Parent)
247			}
248		} else {
249			u = n.Parent.Parent.Left
250			if u != nil && isRed(u) {
251				n = n.Parent.Parent
252				t.flipColors(n)
253			} else {
254				if n == n.Parent.Left {
255					n = n.Parent
256					t.rightRotate(n)
257				}
258				t.leftRotate(n.Parent.Parent)
259			}
260		}
261	}
262	// root should be black node at the end
263	t.root.Color = BLACK
264}
265
266// Remove delete a node by the given key if it exits
267func (t *RBT) Remove(key KeyType) {
268	d := t.Search(key)
269
270	if d == nil {
271		return // not found
272	}
273
274	// find replacement node
275	// in our code, if finally the rpl hold a child node, the rpl must be a
276	// predecessor or successor
277	rpl := d
278	if rpl.Left != nil && rpl.Right != nil {
279		// rpl = rpl.successor()
280		rpl = rpl.predecessor()
281	} else {
282		if rpl.Left != nil {
283			rpl = rpl.Left
284		} else if rpl.Right != nil {
285			rpl = rpl.Right
286		}
287	}
288	// delete replacement node
289	if rpl != t.root {
290		if d != rpl { // d is not a leaf node
291			d.Key = rpl.Key
292			d.Val = rpl.Val
293		}
294
295		if rpl.Left != nil { // rpl is a predecessor
296			if !isRed(rpl) {
297				rpl.Left.Color = BLACK
298			}
299
300			rpl.Left.Parent = rpl.Parent
301			if rpl == rpl.Parent.Left {
302				rpl.Parent.Left = rpl.Left
303			} else {
304				rpl.Parent.Right = rpl.Left
305			}
306			// unlink rpl
307			rpl.Parent = nil
308			rpl.Left = nil
309		} else {
310			// rpl is a leaf node
311			// fix
312			if !isRed(rpl) {
313				t.removeFix(rpl)
314			}
315			// then delete
316			if rpl == rpl.Parent.Left {
317				rpl.Parent.Left = nil
318			} else {
319				rpl.Parent.Right = nil
320			}
321			// unlink rpl
322			rpl.Parent = nil
323		}
324	} else { // single node tree
325		t.root = nil
326	}
327	t.size--
328}
329
330// fixAfterRemove do fix if the deleted node is in black color
331func (t *RBT) removeFix(n *node) {
332	for n != t.root && !isRed(n) {
333		if n == n.Parent.Left {
334			rBro := n.Parent.Right
335			// find real brother node
336			if isRed(rBro) {
337				t.leftRotate(n.Parent)
338				rBro = n.Parent.Right
339			}
340			if !isRed(rBro.Left) && !isRed(rBro.Right) { // can't borrow
341				rBro.Color = RED
342				n = n.Parent
343			} else { // can borrow
344				// 3-node
345				if !isRed(rBro.Right) {
346					t.rightRotate(rBro)
347					rBro = n.Parent.Right
348				}
349				t.leftRotate(n.Parent)
350				// since we pull down n's parent to replace n and
351				// we borrow two n's bro's childern, we need repaint
352				n.Parent.Color = BLACK
353				rBro.Right.Color = BLACK
354				n = t.root
355			}
356		} else {
357			lBro := n.Parent.Left
358
359			if isRed(lBro) {
360				t.rightRotate(n.Parent)
361				lBro = n.Parent.Left
362			}
363			if !isRed(lBro.Left) && !isRed(lBro.Right) {
364				lBro.Color = RED
365				n = n.Parent
366			} else {
367				if !isRed(lBro.Left) {
368					t.leftRotate(lBro)
369					lBro = n.Parent.Left
370				}
371				t.rightRotate(n.Parent)
372				n.Parent.Color = BLACK
373				lBro.Left.Color = BLACK
374				n = t.root
375			}
376		}
377	}
378	n.Color = BLACK
379}

4. Do something fun:红黑树可视化

graphviz库(需自行安装dot工具包)给我们的红黑树实现了Visualize方法:

 1func (t *RBT) Visualize() {
 2	G := visuzlizeTree(t.root)
 3	G.GenerateImage("dot", "rbt.svg", "svg")
 4}
 5
 6func visuzlizeTree(root *node) *graphviz.Graph {
 7	G := &graphviz.Graph{}
 8	addSubTree(root, G)
 9	G.DefaultNodeAttribute(graphviz.Shape, graphviz.ShapeCircle)
10	G.DefaultNodeAttribute(graphviz.FontName, "JetBrainsMono Nerd Font")
11	G.GraphAttribute(graphviz.NodeSep, "0.3")
12	G.DefaultNodeAttribute(graphviz.Style, graphviz.StyleFilled)
13	G.DefaultNodeAttribute(graphviz.FillColor, "#B7BBBC")
14	// G.MakeDirected()
15	return G
16}
17
18func addSubTree(root *node, G *graphviz.Graph) int {
19	if root == nil {
20		null := G.AddNode("")
21		G.NodeAttribute(null, graphviz.Shape, graphviz.ShapePoint)
22		return null
23	}
24	rootnode := G.AddNode(fmt.Sprint(root.Key))
25	if root.isRed() {
26		G.NodeAttribute(rootnode, graphviz.Style, graphviz.StyleFilled)
27		G.NodeAttribute(rootnode, graphviz.FillColor, "#F8BCC2")
28	}
29	leftnode := addSubTree(root.Left, G)
30	rightnode := addSubTree(root.Right, G)
31	G.AddEdge(rootnode, leftnode, "")
32	G.AddEdge(rootnode, rightnode, "")
33	return rootnode
34}

调用生成rbt.svg

https://i.loli.net/2021/05/06/Pe5RWiYyrMhl1Gj.png

5. 总结

本文沿着红黑树同2-3-4树的关系脉络来讨论了红黑树里的插入及删除操作,其可能涉及的情况十分繁多,本文亦不能做到面面俱到。手绘的图也只展示了部分情况,力图通过简单的梳理来理解红黑树平衡性的本质。假如如果你此前对于B树已有很深入的理解的话,相信理解红黑树也不会花费太多时间。