[关闭]
@geek-sjl 2019-04-11T08:53:48.000000Z 字数 6742 阅读 524

二叉搜索树&&红黑树

二叉搜索树

中序遍历复杂度O(n)证明

  1. INORDER-TREE-WALK(x)
  2. if x!=NIL//cost=c
  3.     INORDER-TREE-WALK(x.left)
  4.     print x.key//cost=d
  5.     INORDER-TREE-WALK(x.right)

假设一棵树节点为n，那么可以肯定的是要且仅要调用n次第4行代码,即T(n)<=dn
同理对于每一个节点调用INORDER-TREE-WALK,都需要判断x非空，故T(n)<=dn+cn
假设该树的叶节点（没有左右孩子）有k个，则仍需要k次执行判断非空，故T(n)<=(d+c)n+kc
与书中所述的T(n)<=(c+d)n+c不符，是我哪里理解错了。

中序遍历的非递归

Binary Tree Inorder Traversal

  1. class Solution {
  2. public:
  3.     vector<int> inorderTraversal(TreeNode* root) {
  4.         vector<int> ans;
  5.         stack<TreeNode*> s;
  6.         TreeNode* now=root;
  7.         while(now||!s.empty()){
  8.             while(now){
  9.                 s.push(now);
  10.                 now=now->left;
  11.             }
  12.             if(!s.empty()){
  13.                 now=s.top();
  14.                 s.pop();
  15.                 ans.push_back(now->val);
  16.                 now=now->right;
  17.             } 
  18.         }
  19.         return ans;
  20.     }
  21. };

实际上计算机在执行函数调用的时候也需要用到栈来保存递归调用的过程，我们用栈按照遍历顺序模拟该过程即可获得遍历结果。
第7行的两个判断条件，now!=NULL对应于递归版本判断节点是否非空，如果为空则第12行代码从栈中取出栈顶节点，回退到父节点，如果非空则8-11行模拟INORDER-TREE-WALK(x.left)一直往左节点走的过程，对应的15行就是在输出了左节点和当前节点后往右节点走的过程。
如果now为NULL且栈空时，即已经走到了叶节点且前面路径中所有的节点已经输出完成，过程结束。

前序遍历的非递归

前序遍历非递归

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         vector<int> ans;
  5.         stack<TreeNode*> s;
  6.         TreeNode* now=root;
  7.         while(now||!s.empty()){
  8.             while(now){
  9.                 ans.push_back(now->val);
  10.                 s.push(now);
  11.                 now=now->left;
  12.             }
  13.             if(!s.empty()){
  14.                 now=s.top();
  15.                 s.pop();
  16.                 now=now->right;
  17.             } 
  19.         }
  20.         return ans;
  21.     }
  22. };

后继与前驱

求一个节点的后继即找出大于该节点的所有节点中最小的那一个节点。

  1. TREE-SUCCESSOR(x)
  2. if x.right != NIL
  3.     return TREE-MINIMUM(x.right)
  4. y=x.p
  5. while y!=NIL and x==y.right
  6.     x=y
  7.     y=y.p
  8. return y

如果该节点有右节点，那么在右节点中找最小的那个就是后继了。
如果没有就沿着父节点往上走，直到不满足该节点是父节点的右节点。（因为右节点比父节点和父节点的左节点都要大，当不满足该条件时，即该节点是父节点的左节点，那么父节点就比该节点大，至于为什么这是后继，是因为父节点的右节点都比该节点大，比该父节点都还要大。）

前驱同理。

节点的插入

  1. TREE-INSERT(T,z)
  2. y=NIL
  3. x=T.root
  4. while(x!=NIL)
  5.     y=x
  6.     if z.key<x.key
  7.         x=x.left
  8.     else x=x.right
  9. z.p=y
  10. if x==NIL
  11.     T.root=z
  12. elseif z.key<y.key
  13.     y.left=z
  14. else y.right=z

上面代码中10-14行就是在找到合适的插入位置后判断是插入到根节点还是左边或右边。主要看前面的查找过程。(12.3-2)
实际上这个查找过程和前面查找节点是否存在的过程很类似。基本思路是按照二叉树的结构特点一直往下走直到叶节点，然后叶节点的父节点就是所要查找的插入位置。
在上面插入节点的查找过程中，y的作用就是储存当前节点的父节点。

节点的删除

删除的话分三种情况讨论，分别是没有子节点，有左或右一个子节点，以及有两个子节点。
前面三种较为简单，就是用NIL，左节点，或右节点代替原父节点的位置。
以只有左节点为例，说明代替父节点的位置能够维持二叉树的性质。
设代删除的节点为z，左节点为l,如果z是z.p的左节点，那么l以及l的子节点也小于z.p，反之亦然。
而z又没有右节点，l在原先的基础上又是满足二叉树性质的，那么l代替z后二叉树性质保持不变。

代替过程的函数如下

  1. TRANSPLANT(T,u,v)
  2.     if u.p==NIL
  3.         T.root=v
  4.     elseif u==u.p.left
  5.         u.p.left=v
  6.     else u.p.right=v
  7.     if v!=NIL
  8.         v.p=u.p

接下来讨论删除有两个子节点的节点
假设原有的节点为z，两个子节点分别为l,r，把z删除后l,r的父节点也应满足(l<=z<=r),z的后继就满足这一条件。
假设寻找新的父节点y的时候经过的路径为r->y1->y2->y3->...yn->y
如果r=y,也就是说z的右节点就是它的后继，那么用y替换掉z后再处理一些细节的关系即可。下面说明这种处理能够保证维持二叉树的性质。
首先因为y是z的后继，所以y的左节点比为NIL，在[z,y]中不存在其他元素
由l 那么如果r!=y处理呢。
我们可以想办法转化为r=y先。
因为r->y1->y2->y3->...yn->y，即yr，所以维持了二叉树的性质。那么y原先的右节点怎么办呢？接到yn后面。我们知道yny，即x>yn，二叉树的性质仍然维持，而我们已经把情况转化为了一开始的那样。接着用一开始的方法处理就ok了。

具体的代码如下

  1. TREE-DELETE(T,z)
  2. if z.left==NIL
  3.     TRANSPLANT(T,z,z.right)
  4. elseif z.right==NIL
  5.     TRANSPlANT(T,z,z.left)
  6. else y=TREE-MINIMUM(z.right)
  7.     if y.p!=z
  8.         TRANSPLANT(T,y,y.right)
  9.         y.right=z.right
  10.         y.right.p=y
  11.     TRANSPLANT(T,z,y)
  12.     y.left=z.left
  13.     y.left.p=y

复杂度的话寻找后继有可能会遍历到每一层，其余为常数，所以为O(h)

两个子节点分别为l,r，把z删除后l,r的父节点也应满足(l<=z<=r),z的后继就满足这一条件。
前驱也满足?选前驱还是后继好呢。
我的理解是因为算法的复杂度主要出在遍历层级上，所以前驱和后继看遍历哪一个层级少用哪个。但是，我们在没有执行算法前貌似又没有办法知道哪一个层级少..不如..轮流？没想到好的方法。（红黑树可以解决这个问题）

二叉树建树的不确定性

n个元素有n!种排列可能，最理想和最糟糕情况的二叉树分别会是怎样的呢。
以整数集{7,4,3,2,5,6,15,8,9，10,11,12,1,14,13}为例，最糟糕的一种情况是按照如下顺序插入
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，在这种情况下二叉树退化为一个链表（0(n^2))

  1.              1
  2.             /
  3.            2
  4.           /
  5.          3
  6.         /
  7.        4
  8.       /
  9.      ...
  10.     /
  11.   15

最理想的一种情况是按照如下顺序插入，这种情况下除最后一层，每一层都是满的。
{8,4,12,2,6,10,14,1,3,5,7,9,11,13,15}

  1.                  8
  2.             /         \
  3.            4          12
  4.           / \        / \
  5.          2   6      10  14
  6.         / \  / \   / \ /  \
  7.        1  3  5  7 9 11 13 15

随机构建二叉树的期望高度的尝试证明

红黑树

红黑树最长路径不超过最短路径的两倍证明

红节点的上面不可能是红节点。
实际上红节点的存在的意义之一就是为了尽可能的满足性质五
尽可能的长，又要满足性质五，那么就一边红黑相间，一边只有黑，即证。

最长结果不超过2lg(n+1)

满二叉树时为lg(n+1),又要满足红黑树最长路径不超过最短路径的两倍，那么只能在满二叉树的基础上调整使得红黑相间，即不会超过2lg(n+1)。

NIL节点的引入

在二叉搜索树中，我们将叶节点指向空指针，但是在红黑树的实现中这么做会使一些情况变得复杂，所以定义一个NIL节点，设定其颜色为黑色以满足性质3。

旋转

  1. LEFT-ROTATE（T,x)
  2.     y=x.right
  3.     x.right=y.left
  4.     if y.left!=T.nil
  5.         y.left.p=x
  6.     y.p=x.p
  7.     if x.p==T.nil
  8.         T.root=y
  9.     elseif x==x.p.left
  10.         x.p.left=y
  11.     else x.p.right=y
  12.     y.left=x
  13.     x.p=y

以上为左旋的伪代码，假设有节点a,b，a

旋转的意义

给定一组n个数，二叉树的形态可以有很多种。最坏的一种情况为链表，在此基础上，我们旋转连接这n个数的n-1条边，就可以构造出满足二叉树性质的其他形态。而通过合适的方法，则进一步可以通过旋转构造出较优的二叉树。

插入

  1. RB-INSERT(T,z)
  2.     y=T.nil
  3.     x=T.root
  4.     while x!=T.nil
  5.         y=x
  6.         if z.key<x.key
  7.         x=x.left
  8.         else x=x.right
  9.     z.p=y
  10.     if y==T.nil
  11.         T.root=z
  12.     elseif z.key<y.key
  13.         y.left=z
  14.     else y.right=z
  15.     z.left=T.nil
  16.     z.right=T.nil
  17.     z.color=RED
  18.     RB-INSERT-FIXUP(T,z)

插入过程与二叉树基本一致，不同主要体现在1、我们用NIL节点替换了NULL；2、给新节点增加了着色过程；3、调用了辅助过程维持红黑树的性质。

为什么着为红色不着为黑色？着为黑色破坏性质五，着为红色破坏性质二或性质四。
破坏性质五（多了一个黑节点）不好修复，因为把任意一个黑节点换成红节点，红节点下面跟的要是黑节点，会引发“连锁反应”，不好处理

  1. RB-INSERT-FIXUP(T,z)
  2.     while z.p.color==RED
  3.         if z.p==z.p.p.left
  4.             y=z.p.p.right
  5.             if y.color==RED//case1
  6.                 z.p.color=BLACK
  7.                 y.color=BLACK
  8.                 z.p.p.color=RED
  9.                 z=z.p.p
  10.              else if z=z.p.right//case2
  11.                 z=z.p
  12.                 LEFT-ROTATE(T,z)
  13.             z.p.color=BLACK//case3
  14.             z.p.p.color=RED
  15.             RIGHT-ROTATE(T,z.p.p)
  16.         else(same as then clause with "right" and "left" exchanged)
  17.     T.root.color=BLACK

首先按照待删除节点的父节点为其左、右节点分为两大类，这两大类的处理方式其实是对称的。

z的含义
以z为根节点的子树满足红黑树的性质
我们通过不断提升z直到它的父节点为黑色
因为我们只可能破坏性质2或者性质4,而父节点为黑色的时候性质2或性质4都可以确保没有被破坏（T.root.p=T.NIL的精妙之处之一）

以左节点一类作为讨论，可分为三种情况

情况1 z的叔节点为红色

由y是红色可以知道z一定不为红色（即一定为黑色),在此前提下又因为性质4的限定，z的父节点也不能使黑色（必定为红色），那么就可以把z的祖先节点的黑色下放到左右节点，所以性质都没有破坏。

z节点可以往上走两步

情况2 z的叔节点y是黑色的且z是一个右孩子

左旋统一为左孩子情况处理
左旋后z向上走一步
（z为根的子树满足红黑树性质，左旋后一个黑节点（因为它本身为红节点）代替它原来的位置，而它自身通过左旋成为了原父节点的父节点，为红色。）

情况3 z的叔节点y是黑色的且z是一个左孩子

z.p为红，z.p.p必为黑，则让z.p成为z和z,z.p.p的父节点，同时着为黑色，黑高不变，也确保了性质四

13-3.4
根节点是黑的

删除

  1. while x!=T.root and x.color=BLACK
  2.     if x==x.p.left
  3.         w=x.p.right
  4.         if w.color==RED//case1
  5.             w.color=BLACK
  6.             x.p.color=RED
  7.             LEFT-ROTATE(T,x.p)
  8.             w=x.p.right
  9.         if w.left.color==BLACK and w.right.color==BLACK//case2
  10.             w.color=RED
  11.             x=x.p
  12.         elseif w.right.color=BLACK//case3
  13.                 w.left.color=BLACK
  14.                 w.color=RED
  15.                 RIGHT-ROTATE(T,w)
  16.                 w=x.p.right
  17.             w.color=x.p.color//case4
  18.             x.p.color=BLACK
  19.             w.right.color=LBACK
  20.             LEFT-ROTATE(T,x.p)
  21.             x=T.root
  22.         else (左右对称）
  23.     x.color==BLACK

删除操作相较于二叉树的删除操作，多维护了两个信息
y-original-color和x节点
x节点理解为可能引起红黑树性质改变的最低的那个节点，也是y节点原先的位置
y为待改变或删除的节点（x的父节点？）——好像把y节点删掉一样，实际上是先移动了y

讨论一下第12-13行
当替代待删除节点的节点要从该节点的后继中找时，x.p一般情况下指向y.p(替代了y.p原有的位置，具体在14行替换中实现），但是当后继的父节点是待删除节点时，不能将x.p指向y.p，因为y.p是z，待删除节点，指向了没用，而这个时候可以指向y，因为y替代了z的位置，而x与y的父子关系不变。

再讨论一下y-original-color为RED时不需要执行恢复操作。
首先删除的是红节点，性质五不受影响。
至于性质四受不受影响，首先考虑没有左或右孩子的情况，显然不受影响。
再考虑有左右节点的情况，y替换了z的位置同时也保持了它原来的颜色，即y处性质不受影响。
原有的后继处的节点则和待删除节点没有左或右孩子时的情况类似，也不受影响。

接下来讨论y-original-color为BLACK时的恢复操作。
我们首先把x的节点赋予一个特殊的含义——多一层黑色。即原来是红的，在性质五计算时+1，原来是黑的，+2
由于x要替代原来删除的位置，所以给它多一层黑色之后就好像原来y的那个黑色还在，性质五不被破坏。至于性质二和性质四，我们在考虑x的特殊含义时仍把它看成原来的颜色，因而仍然成立。

现在的问题是性质1，之前说好了一个节点只能是红的或黑的，那么我们接下来要做的就是想办法把x中多出来的“黑”推给某个“红节点”，让它变为黑的，就可以保持性质1了
把多出来的“黑”推到一个“红”节点是我们的最终目的，那么修复过程的边界条件也就确定了。当节点为红时，把它染黑，就可以退出循环。

接下来讨论以上所述的具体过程。
依旧分左右两大类，以左边一类为例
分四种情况讨论。

x的兄弟节点w是红色的

统一处理为是黑色的情况（具体看代码，这是一个容易理解但自己实现却难以想到的过程）

x的兄弟节点w是黑色的，且w的两个子节点都是黑色的

两兄弟同时少一层黑色，w变为红，x变为黑，然后把原有的“黑”提到父节点
（x和w的父节点必为红，推给它不会导致双重颜色）

x的兄弟节点w是黑色的，w的左孩子是红色，右孩子是黑色的

统一处理为情况四（也是容易理解，不容易想）

x的兄弟节点是黑色的，w的右孩子是红色的

这里之所以要强调右孩子是红色的，其实是为了左旋后D成了父节点，B,E成了D的子节点，确保把D的黑下放给E时不会出现双重黑。注意，B的黑不是由D下放出来的，而是A的双重黑给了一个给B，为什么之前不能给现在可以？因为之前B既在B——A路径上，又在B-D-E路径上，给了之后破坏性质五。现在B只在A、B路径上，不影响右边情况。

为什么情况2不能确保一定终止而情况4可以？
因为情况2 B颜色不确定，情况4 B颜色确定

13.4-6
x.p为红，则w为p，不会进入情况1.

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注