I see a brand new
node I want to paint it black
We need a balanced
tree, we've got to paint it black.I want
to find my key in log n time--that's
all.
Rotating sub-trees' round sure
can be a ball.
I see a brand new node I want to paint it
black.
Can't have a lot of red nodes, we must
paint them black.
Unfortunately, coding them can be a bitch.
If we
had half a brain to splay trees we could switch.
I see a brand new node I want to paint it black.No
time for AVL trees we must paint it black.
大家好，数据结构与算法这一讲的内容， Hello everyone! Welcome to this lecture of data structure and algorithm.
我们继续学习第十一章索引中的红黑树。 We now continue to learn Red black tree in the 11th chapter, index.
红黑树它主要是对内存的，比较小规模的数据进行索引。 RB tree is mainly used for small scale data structure refined in the memory.
在外存里面我们还是采用前面介绍的静态多分树以及B树，B+树等等 While we use static tree or B tree when disks are involved.
而且在内存里面，如果数据规模比较大的情况下，我们也往往采用B树。 But when the data is so large in memory, we also use B tree.
在我们内存里面常用的索引结构，其实就是BST BST is the most useful indexing data structure in memory,
BST，它最主要的就是有一个比较好的检索性能。 for its comparative good feature
如果我们 树高接近于log n的情况下，它的插入删除和查找 都是log n量级的。 that we can insert or delete nodes in log n when the height of tree is near log n.
但是它依赖于我们输入的顺序，如果我的输入是一个比较随机的情况， But it depends on the order of our input. When we input keys randomly, there is no problem.
没问题。但如果是输入是一个，例如是上升序列，或者是下降序列也类似， 我们就会退化成一个单线的 Yet ascending or descending input sequence will led to the reverse to a list structure, which is O(N)
一个链接的形式。就会是ON的代价。 我们有很多对BST的平衡策略， 其中红黑树是一种非常有效的平衡策略。 We have a lot of BST balance strategy, of which the red-black tree is a very effective balance strategy.
我们下面来看红黑树的相关定义。 We are here to see the definition of a red-black tree.
红黑树，首先就是它，是一个扩充的BST。 Red and black tree, for the first characteristic, is an extension of BST.
也就是我们对原来这种外部的空指针都给它扩充上叶的结点。 We expand original external null pointers to leaf nodes.
另外， 我们对整个这个树进行着色。 In addition, we have the whole this tree colored.
首先就是根，还有这个外部的叶，都是黑色。 The root and external nodes will be black.
其他的内部结点，它可以是红，可以是黑。 Others can be red or black.
但是，我们要限制这个不能够有两个连续的红， But we want to limit this will not be able to have two consecutive red node.
而且，我们从一个结点出发， 到叶结点的这个路径上， 它所经过的这个黑色的结点个数，都是相同的。 Moreover, when we set off from one node to the leaf nodes through the path, the node number of black is the same.
从根来说也是满足这样的一个定义。 From the root, also meet such a definition.
在路径上头的这个黑色的结点数，其实就是它的一个概念叫做阶。 The number of black nodes is the concept, rank.
我们来看这个每一个结点的阶，其实也可以把它叫做黑色高度。 Let’s see the rank of each node, actually, we can call it black height, too.
我首先把自己遮掉，然后我们看一下从它的一个分支出发， 到这个外部的叶结点有几个黑。 Firstly, we cover the node itself, then start from one of its branches to the external leaf node and count black nodes.
这个结点2就是它的阶为1，结点4阶为2，这个根它的结点阶是2。其实这也是我们整个红黑树的阶， So the rank of node 2 is 1, node 4’s is 2, root node’s is 2, and it’s the rank of the whole RBT.
红黑树它首先是一个BST，然后它是扩充的满二叉树。 RBT is a BST, an expended full BST.
它的这个空的叶结点，在我们后面考虑的时候也把它看作是结点。 We regard its empty leaf node as a normal node.
阶为K的这个红黑树，它的路径的长度，最短的情况下就是K。其实也就是说，我们中间没有任何的红的结点，像9到15，到这个外部空。 The length of the path of a RBT with rank K, in the shortest possible cases, is K, namely, there is no red node between, like form 9 to 15, the external empty node.
最长的情况，就是2K。 While in the longest cases, it’s duple K.
就是我们从这个9到4，6，7，然后外部空。就是黑红黑红 黑，这样相间的一条路径。 Like 9-4-6-7, and then the external empty node, it’s black-red-black-red-black, an interphase path.
相应于这个路径，我们其实还有个树高的概念，树高其实就是这个路径的长度加1。 Corresponding to the path, we have the concept of tree height, and the tree height is actually the path length plus 1.
路径我们可以看作是这个边的个数，然后这个树高，其实可以看作是结点的个数。 We regard path length as the number of edges, tree height as the number of nodes.
我们再来看一下红黑树的内部结点个数，最少是多少，它最多又是多少。 Then let’s see the maximum and minimum of inside node number of RBT.
最少的情况下就是它完全没有红结点，这个时候，它的这个结点个数就会是2, k减1，这么多个。 When there is no red node at all, the RBT have the fewest nodes, and the number of nodes is 2*k-1.
如果是对于n个结点的这样的一个红黑树，它的这个树的高度是多少？ What’s the tree height of a RBT with n nodes?
我们可以通过这个性质二和性质三来推导，首先我们假设它的阶是k，然后它的树高是h。 We can deduce with nature Ⅱ and nature Ⅲ, firstly we assume its rank is k, the tree height is h.
我们由这个性质二，我得到h和k的这么一个关系。 And we get the relation of h and k through nature Ⅱ.
然后我由这个性质三，我又得到了这个n和k的这个关系我把这个k给约掉，我们就得到了h和n的关系，也就是说我们这么一个红黑树，它如果有n个结点，它的输入的高度会是log以2为底，n+1的对数，然后是乘2，然后再加1. Then we get the relation of n and k, lose k, and we get the relation of h and n. That is to say, the tree height of a RBT with n nodes is 2*log (n+1)+1.
也就是说我们这个树高是在log n到2倍的log n之间。 So the tree height is between log n and 2*log n.
我们怎么维护红黑树的这样的性质， Then how to maintain this nature of a RBT?
其实红黑树的这个性质能够保证的情况下，它的性能也就能得到保障， In fact, when the nature of a RBT is guaranteed, its performance can be guaranteed, too.
我们来看，首先，它是BST。 First of all, a RBT is a BST.
因此，插入算法我们先遵循这个BST的这个插入算法，就是找到这个外部的失败结点，然后，我们再把这个结点插入，插入以后，我们显然不能对它着黑色。 So the insert algorithm follow BST’s, that is, after finding the external failure node, we insert the node, and apparently, we can’t make it black.
因为黑色是起到一个阶的一个控制作用。 For black nodes control the rank.
我们只能着红色，然后再看看怎么样进行调整。 We can only make it red, then let’s see how to adjust it.
如果是插入了以后，它原来这个父结点是黑色，我们就完成了这样一个插入操作。 If after inserting a new node, its father node is black, we accomplish such an insert operation.
如果原来父结点是红色，像这个例子，3和4是双红冲突，我们就需要进行一个红红的调整。 If its father node is red, like this, for example, No.3 and No.4 is duple red conflict, and we need a red-red adjust.
红红调整主要分成两类， There are 2 kinds of red-red adjust.
第一类就是说它的这个叔父结点，是黑色。这样的话我们经过一个旋转，可以把这个红色给它调过去，然后就完成了这样的一个操作。 Firstly, its uncle node is black, then we can move the red node there through a spin, and we accomplish the operation.
像这个结构，我们经过一个旋转以后可以看到，我把这个原来左边的这样的双红，也就移到这个右边这个分支了。我再把相应的其他的这些信息，给挂接上，就完成了调整。 For this structure, we can see, after a spin, the duple red in the left turns to the branch in the right, after linking other relevant information, we fulfill the target to adjust
对于红黑树它的这样的一个插入以后，需要调整的情况，其实我们分成这四种。 There are 4 circumstances when we need to adjust after an insert in the RBT.
这四种，这个左边两种 先右再左，或者先左再右这样的一个之字型的，然后这个右边两种就是这边左边顺或者右边顺的一字型的。 The left two circumstance are right-left or left-right “N” style, while the right two are left-smooth or right-smooth “I” style.
调完以后都是这样的一个比较对称的这个支架型的。 After adjustment, they will all be symmetrical holder-like structure.
它们的共同特点就是保持这个BST它原来的这样的一个中序下有序的这个性质。 The common feature is that they all maintain the nature of maintaining order in middle order.
如果是这个插入结点x它的叔父是红色，也就是说它经过调整没有把这个颜色给它均衡一下的这个余地。 If the uncle node of our inserted node x is red, that is, there will be no room for us to balance colors after the adjustment.
这个时候，我们就对父和祖进行换色。 Then we exchange colors between the father and the grandfather node.
换色了以后，原来这个祖先，它一定是黑的。 After changing the color, the original grand node is fixed to be black.
这个时候我把它变成了红的，这个时候，我们的当前结点就换到了祖先这个结点。 Now we change it to red, and the current node is exchanged to the grand node.
这个祖先结点，它继续往上面看，然后检查红红冲突，然后如果有的话就调整，如果没有就完成了这个插入操作。 For the grand node, we check if there is duple red conflict upward, and we adjust it if there is, or accomplish the insert operation if there is not.
我们来看一个例子。我们在这里插入4，4就会在5的外部失败的空着节点，插入以后，么看到4它的叔父8也是红色，因此父祖换色，把7换成红色，然后5和8标成黑色，这个7跟它的这个自己的父2，是红红冲突。 Let’s see an example. We insert 4 here, 4 is a failure empty node outside 5, then we find that 4’s uncle, 8, is red, too, so 4’ father and grandfather exchange colors, we change 7 to red, make 5 and 8 black, this 7 and its father 2 is duple red conflict.
我们看到，7的叔父是黑色，我们有这个旋转调整的余地。我们进行一个重构选段以后，它就完成了这个插入的操作。 As we can see, 7’s uncle is black, so we get room of spin adjustment. After rebuilding, we accomplish the insert operation.
删除，它也是在BST的这样的一个性质下的删除， Deletion is under the nature of BST.
如果是说这个节点，它的这个左右孩子里面有一个空，我们就把这个非空挂接上，就完成了这样的一个删除。 If left or right son of the node is empty, we link the node that is not empty, then we accomplish the deletion.
如果是它的左右子节点都不空，我们就需要找到左里面的最大或者是右里面的最小，然后替代这个待删的节点，然后我们再从比较靠近叶的个替代的位置删掉，然后再继续进行操作。 If both of its node are not empty, we find the largest in the left or the smallest in the right to replace the node to be deleted, then we delete the place near leaf, and we can continue our operation.
在这个红黑树里面，我们如果是删除节点8，可以看到，删掉以后，我们用这么一个外部的这个空叶节点来替到这个8这个位置， In this RBT, if we delete node 8, we can see, after deletion, we replace 8 with an outside empty leaf node.
这个时候，这个删掉了以后在我们这样的一个，待操作的节点， X，它就是变成了一个双黑的这么一个节点。也就是说，这里它其实承担着两层黑颜色的重任， 我们需要进行双黑的调整。 Now, after deletion, the node waiting operation, x, change to a duple black one, that is to say, it bears the responsibility of duple black, we need duple black adjust.
如果是被删的这个节点它如果是红色的，因为它不影响阶，删完红节点，我们其实是不需要进行调整了，就直接完成了删除操作。 If the deleted node is red, for it doesn’t influence rank, we don’t need to adjust after deleting a red node to accomplish deletion.
我们来看，对于双黑的调整，有哪几类？ Let’s see, how many cases of duple black adjustment there are.
情况1和情况2它其实，，都是可以进行调整的。它们的共同特点，就是这个删掉以后替换的个X节点，它的一个兄弟节点，是黑色， Case 1 and case 2 are both can be adjusted, their common character is that one of the brother nodes of the exchanged x nodes after deletion is black.
在这个情况1里面，它的这个侄子节点有红色，这样的话，我们就可以做一些重构把这个颜色，给迁移过去，然后完成这样的一个调整。 In case 1, there is red nodes in its nephew nodes, this way, we can make some reconstruction to migrate the color, then we accomplish the adjustment.
但是如果是情况2，它的这个侄子节点都是黑色，么我们就没有办法通过这个重构来转移颜色， But for case 2, its nephew nodes are all black, so we cannot migrate colors through reconstruction.
这个时候我们需要进行换色操作，而且这个换色可能往祖先的方向传递。 Now, we need to change color, and the color may move to its ancestor.
情况3的表现就是它的兄弟节点还是红色的，这个时候兄弟节点它的子节点一定是黑色的，因为否则我们就有双红冲突了。 What case 3 looks like is that its brother nodes are red, so its nephew nodes are fixed to be black, otherwise there will be duple red conflict.
这个时候我们进行一下选段，选完以后，我们使得X节点它的兄弟，就可以变成是黑色的情况，也就是说我们化解为前面的两类情况，然后再继续调整。 Now we can extract blocks, after that we change some x’s blocks to black ones, that is, we get former 2 cases, then we adjust it accordingly.
我们来看后面具体的这个操作的例子。 Let’s see a specific example of operation.
首先，就是情况1， 而且这是情况1里面，第一种分支。 Firstly, case 1, and it is the first kind of branches in case 1.
X它有红色的侄子，而且这个侄子跟它是像一个8字形撇开的，这个时候，把它进行这么一个一字型的旋转，整个原来是这个右撇的，我把它变成一个左撇的形状，然后 D这个侄子标成黑色。 X has a red nephew, and the nephew along with it is like an “8”, so we make a spin like “1”, and we change the right-leaning form into a left-leaning one, then make the nephew, “D”, black.
原来这个B它的颜色，我们就给它还放在这个新的跟C的这个颜色上面，也就是说，C继承原来这个B的颜色， We color C, the new node, with the color of B, the old node, that is, C inherits B’s color.
然后大家可以看到，我其实通过这样一个旋转，我们把原来这个X的这个双黑里面的个黑， 我给它用这个D来平衡了，就完成了这样的一个调整操作。 As you can see, in fact, we just make a spin to balance the duple black of X with D and accomplish the adjustment.
第二类的这个分支情况是类似，它只是说这个侄子这个红色个，是在跟它同边顺的，这样的一个情况，我们也是进行一个调整。 The branch form of case 2 is similar, what is special is only that the red nephew is on the same edge, and we adjust it.
调完以后，这个D这个红色的侄子它成为根，而且，它继承原来这个B的颜色，我们把这个B，一定是给它作为黑色，在这样的一个分支下，我们可以看到，这两个子数，就是调整前的子数，和调整后的子数，他们的这个接的情况，是保持不变的， After adjustment, the red nephew, D, becomes a root, and it inherits B’s color, and we are fixed to make B black, and under such a branch, as we can see, the rank of these two son trees—before and after adjustment are the same.
而且对上面来说，我们这个其他的这个红黑树里面的分支，不受这边的这个局部调整的影响。 Besides, other branches in the RBT will not be influenced by this partly adjustment.
对于第二类情况，就是它的这个兄弟的节点，没有红色的孩子。 For case 2, when its brother nodes don’t get red sons,
这个时候，我们就没有办法把它这个黑色给它迁移，因此，我需要进行一个， 换色的操作。 we need to move black, so we need the operation of exchanging colors.
我把这个兄弟节点标成红色，我把自己的这样的一个，双黑的这么一个颜色，我在它的这个父节点里面加重一下，这个时候，我们的这个需要调整的当前节点就迁移到这个父节点，然后父节点继续往上面进行双黑的调整。 We make this brother node red, as for the node itself, the duple black one sharpen it in its father node, now the node need adjusting move to the father node, then we adjust duple black upward from the father node.
对于情况3，如果是X它的兄弟节点是红色的，这个时候，我们没有办法把它的这个双黑迁移到这边的这个子数里面，因此，我就需要进行一个调整。 As for case 3, if X’s brother is red, we are not able to move its duple to the son tree, so we need to adjust it.
这个调整， 因为C它的父节点以及它的子节点一定都是黑色的， We can adjust for C’s father and son are fixed to be black.
我们调完以后，C上升为这个新的这个子数根， After our adjustment, C promote to new son tree root.
然后，我把这个B的颜色换成红色，从颜色上，它是平衡了。 Then, we change B’s color to red, and it’s balanced form color.
然后，我可以看到，因为原来alpha这个子根结点它一定是黑色的，因此，这个X节点它的兄弟一定是黑色的情况，就化解为前面的两类这个情况继续操作。 Then, as we can see, because the son root node of alpha is fixed to be black, the case where X’s brother is fixed to be black can be changed to the former two cases.
我们来看一下这个例子。首先就是我删除了90，删90的时候我可以直接把90这个节点删掉，然后，这个外部的这个叶节点，它是一个双黑的情况。 Let’s see this example, at first we delete 90,we can delete the node 90 when deleting 90, the outside the leaf node, it’s duple black.
这个双黑了以后，我们就来看，它的这个兄弟也是一个黑节点，然后它的兄弟节点里面是没有红色的这个分支的，我们就是要进行换色。 The duple-black’s brother is a black node, too, and there is no red branch in other brother nodes, and we need to change the color.
换色了以后，因为原来这个80是红色的，现在换成黑色，我们就已经达到平衡了， After changing colors, because 80 was once red, now it is black, we get balanced.
把这个双黑就给它化解掉了，这个调整完成。 After resolving this duple black, we accomplish the adjustment.
接着我们继续删除70，因为70它就是个红节点，红节点删掉以后完全不影响接，我们就不需要任何的调整。 Then we go on to delete 70, it’s a red node, so deleting it makes no influence, and we don’t need any adjustment.
我们继续删除80，删完以后，这个又是出现一个双黑的节点， 而它的这个兄弟节点，是红色的情况，我就需要进行一个旋转，然后旋转成情况1和情况2来继续调整。 Now we go on to delete 80, and we will get a duple black node, ad its brother node is red, so we need a spin to change it to case 1 or case 2.
我们旋转完了以后，我们发现这个X节点它是有这样的一个红色的侄子，我们进行一个重构，就可以完成这个调整。我们看这个结构是一个之字形的，我们把它重构以后成为一个支架形的这样一个平衡的结构，这个调整就完成了。 After spinning, we find that X has a red nephew, and we only need a reconstruction to accomplish the adjustment. As we see, the structure is “N” style, and after the reconstruction we change it to a holder-like balanced structure, then the operation is accomplished.
红黑树的检索时间显然是log n的，然后它的插入、删除，是基于检索进行， 这个检索的部分是log n的， 插入删除它需要调整的时候是从叶往根的方向来调整， The retrieval time of RBT is log n, and its insertion, and deletion are based on retrieval, and time for retrieval is log n, and when insertion and deletion need adjustment, it’s from leaf to root.
而且每次调整都是一个局部的一段分支。因此，我们最坏情况下即使到根，也就是log n的代价，因此，它的所有操作都是能够 在log n的这个时间内完成。 And every adjustment influences a branch in a part, thus the worst case—moving to the root, the cost is merely log n, so every operation of RBT can be accomplished in log n.
我们最后给大家留下思考： At last, I have something for you to think about:
首先就是红黑树的构造，红黑树它是一种BST， Firstly, the construction of RBT; RBT is a kind of BST.
BST我们重要的有3个域，就是数据域，然后左指针，右指针。 And there are 3 important regions—data domain, left and right pointer.
红黑树它还要加一个颜色的标记，另外就是我们在调整的时候经常会回溯到这个父指针， RBT also needs a color marker, besides we need to recall the father pointer
因此我们父指针域，如果加上以后，它操作会更方便。 If we add this father domain, it’s more convenient to operate.
当然如果你要写算法的时候是从上到下 这样的一个递归来进行的，也是可以不写父指针的，大家看一下这两种情况，它的具体的实现有什么不同。 Of course, if you write algorithm downward through a recursion and we don’t need to write father pointer, you analyze these two cases and find the difference in concrete operation.
还有就是这个红黑树它跟我们前面介绍过的B树它是有一个对应关系，其实就是对应到4阶的B树，我们也称为2-3-4树。 Besides, RBT is corresponding to B tree, which we introduced before, actually it is linked to B tree of 4 ranks, which is also called 2-3-4 tree.
看这个图，给大家提醒一下就是 Look at this picture, I give you some hints.
我们在这样的一个红黑树里面我都是把这个红色的节点，我给它吸收到父节点，我就把它变成了一个这样的4阶的B树。 当然，如果是4阶B树换成红黑树也是可以的，大家继续思考。 We absorb all red nodes in a RBT into father nodes, and we change it to a B tree of 4 ranks. Of course, we can change a B tree of 4 ranks into a RBT, please continue your thinking.
谢谢大家！ Thank you!