本文共 7616 字,大约阅读时间需要 25 分钟。
二叉查找树(Binary Search Tree)是指一棵空树或者是具有下列性质的二叉树:
一棵由n个节点随机构造的二叉查找树的高度为logn,所以一般操作的执行时间复杂度为O(logn)。但是二叉树若退化成了一棵具有n个结点的线性链表后,则此些操作最坏情况运行时间为O(n)。
红黑树(R-B Tree)是一种特殊的二叉查找树,它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn),一棵含有n个节点的红黑树的高度至多为2log(n+1)。红黑树主要用来存储有序数据,例如Java集合包中的TreeMap和TreeSet,以及Linux虚拟内存的管理都是基于红黑树去实现的。
红黑树的特性:
叶结点即指树尾端NIL指针或NULL结点)
是黑色;以上5条性质使得一棵n个结点是红黑树始终保持了logn的高度。
红黑树示意图如下:
红黑树的旋转
当我们在对红黑树插入或删除等操作时,可能会破坏红黑树的性质。此时我们可以通过对结点进行重新着色,以及对树进行相关的旋转操作,即修改树中某些结点的颜色及指针结构,来达到对红黑树进行插入或删除结点等操作后,继续保持它的性质或平衡。
树的旋转分为左旋和右旋。
左旋
对pivot进行左旋意味着将pivot变成一个左节点。
伪代码如下:
LEFT-ROTATE(T, x) 1 y ← right[x] ▹ Set y. 2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree. 3 p[left[y]] ← x 4 p[y] ← p[x] ▹ Link x's parent to y. 5 if p[x] = nil[T] 6 then root[T] ← y 7 else if x = left[p[x]] 8 then left[p[x]] ← y 9 else right[p[x]] ← y 10 left[y] ← x ▹ Put x on y's left. 11 p[x] ← y
右旋和左旋相似,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。
通过树的旋转,能保持就只有原树的搜索性质,而原树的红黑性质不能保持。
红黑树的插入
二叉查找树的插入
如果要在二叉查找树中插入一个结点,首先要查找到结点插入的位置,然后进行插入。假设插入的结点为z的话,插入的伪代码如下:
TREE-INSERT(T, z) 1 y ← NIL 2 x ← root[T] 3 while x ≠ NIL 4 do y ← x 5 if key[z] < key[x] 6 then x ← left[x] 7 else x ← right[x] 8 p[z] ← y 9 if y = NIL10 then root[T] ← z ⊹ Tree T was empty11 else if key[z] < key[y]12 then left[y] ← z13 else right[y] ← z
可以看到,如果插入结点z小于当前遍历到的结点,则到当前结点的左子树中继续查找,如果z大于当前结点,则到当前结点的右子树中继续查找。当找到待插入的位置,如果z依然比此刻遍历到的新的当前结点小,则z作为当前结点的左孩子,否则作为当前结点的右孩子。
红黑树的插入和插入修正
红黑树的插入操作是在二叉查找树的基础上为了恢复平衡,增加了修正操作。假设插入的结点为z的话,插入的伪代码如下:
RB-INSERT(T, z) 1 y ← nil[T] 2 x ← root[T] 3 while x ≠ nil[T] 4 do y ← x 5 if key[z] < key[x] 6 then x ← left[x] 7 else x ← right[x] 8 p[z] ← y 9 if y = nil[T] 10 then root[T] ← z 11 else if key[z] < key[y] 12 then left[y] ← z 13 else right[y] ← z 14 left[z] ← nil[T] 15 right[z] ← nil[T] 16 color[z] ← RED 17 RB-INSERT-FIXUP(T, z)
可以看出,RB-INSERT(T, z)前面的第1-13行代码基本就是二叉查找树的插入代码,然后第14-16行代码把z的左孩子、右孩子都赋为叶结点nil,再把z结点着为红色,最后为保证红黑性质在插入操作后依然保持,调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色,并旋转。
换言之,
但当遇到下述3种情况时:
就需要根据红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP(T,z)所示操作进行:
RB-INSERT-FIXUP(T,z) 1 while color[p[z]] = RED 2 do if p[z] = left[p[p[z]]] 3 then y ← right[p[p[z]]] 4 if color[y] = RED 5 then color[p[z]] ← BLACK ▹ Case 1 6 color[y] ← BLACK ▹ Case 1 7 color[p[p[z]]] ← RED ▹ Case 1 8 z ← p[p[z]] ▹ Case 1 9 else if z = right[p[z]] 10 then z ← p[z] ▹ Case 2 11 LEFT-ROTATE(T, z) ▹ Case 2 12 color[p[z]] ← BLACK ▹ Case 3 13 color[p[p[z]]] ← RED ▹ Case 3 14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 15 else (same as then clause with "right" and "left" exchanged) 16 color[root[T]] ← BLACK
红黑树的删除
二叉查找树的删除
待删除的节点按照儿子的个数可分为三种情况:
二叉查找树删除节点的伪代码如下:
TREE-DELETE(T, z) 1 if left[z] = NIL or right[z] = NIL 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ NIL 5 then x ← left[y] 6 else x ← right[y] 7 if x ≠ NIL 8 then p[x] ← p[y] 9 if p[y] = NIL10 then root[T] ← x11 else if y = left[p[y]]12 then left[p[y]] ← x13 else right[p[y]] ← x14 if y ≠ z15 then key[z] ← key[y]16 copy y's satellite data into z17 return y
红黑树的删除和删除修正
红黑树结点删除的算法实现是:
RB-DELETE(T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ nil[T] 5 then x ← left[y] 6 else x ← right[y] 7 p[x] ← p[y] 8 if p[y] = nil[T] 9 then root[T] ← x 10 else if y = left[p[y]] 11 then left[p[y]] ← x 12 else right[p[y]] ← x 13 if y ≠ z 14 then key[z] ← key[y] 15 copy y's satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return y
在删除结点后,原红黑树的性质可能被改变,如果删除的是红色结点,那么原红黑树的性质依旧保持,此时不用做修正操作,如果删除的结点是黑色结点,原红黑树的性质可能会被改变,我们要对其做修正操作。那么哪些树的性质会发生变化呢,如果删除结点不是树唯一结点,那么删除结点的那一个支的到各叶结点的黑色结点数会发生变化,此时性质5被破坏。如果被删结点的唯一非空子结点是红色,而被删结点的父结点也是红色,那么性质4被破坏。如果被删结点是根结点,而它的唯一非空子结点是红色,则删除后新根结点将变成红色,违背性质2。
删除修正伪代码:
RB-DELETE-FIXUP(T, x) 1 while x ≠ root[T] and color[x] = BLACK 2 do if x = left[p[x]] 3 then w ← right[p[x]] 4 if color[w] = RED 5 then color[w] ← BLACK ▹ Case 1 6 color[p[x]] ← RED ▹ Case 1 7 LEFT-ROTATE(T, p[x]) ▹ Case 1 8 w ← right[p[x]] ▹ Case 1 9 if color[left[w]] = BLACK and color[right[w]] = BLACK 10 then color[w] ← RED ▹ Case 2 11 x ← p[x] ▹ Case 2 12 else if color[right[w]] = BLACK 13 then color[left[w]] ← BLACK ▹ Case 3 14 color[w] ← RED ▹ Case 3 15 RIGHT-ROTATE(T, w) ▹ Case 3 16 w ← right[p[x]] ▹ Case 3 17 color[w] ← color[p[x]] ▹ Case 4 18 color[p[x]] ← BLACK ▹ Case 4 19 color[right[w]] ← BLACK ▹ Case 4 20 LEFT-ROTATE(T, p[x]) ▹ Case 4 21 x ← root[T] ▹ Case 4 22 else (same as then clause with "right" and "left" exchanged) 23 color[x] ← BLACK
上面的修复情况看起来有些复杂,下面我们用一个分析技巧:我们从被删结点后来顶替它的那个结点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的结点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父结点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。
如果是以下情况,恢复比较简单:
如果是以下情况:
此时,我们需要调用RB-DELETE-FIXUP(T, x),来恢复与保持红黑性质的工作。
转载地址:http://uptmi.baihongyu.com/