字符画之画二叉搜索树

用字符“画”搜索树,包括二叉树、红黑树等。

此篇文章,以树的“搜索”为主线来讲解,因为无论是插入还是删除,均离不开搜索;而反过来,为了保证树的搜索性能,插入和删除均需要做一定处理。


Binary Tree

首先说二叉树(Binary Tree),毕竟,后面所讲的,都要基于二叉树。
从离散数学的角度来讲,树是由通过图结构来定义的,这里就直接讲二叉树了(当然,直接讲就不怎么严谨)。

基本概念

  • 二叉树节点
          D
         / \
        L   R
  D : 当前节点,称D为L和R的父节点;
  L : D的左孩子节点;
  R : D的右孩子节点;

  二叉树节点C式代码的实现:

struct Node{
    Data         data;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
    int     height;     // 节点高度
    int     color;      // 节点颜色,红黑树需要用到
};
  • 简单的二叉树
  -----            r           -----
 Depth(v)       /     \
  -----        v       u
             /   \    / \     Height(r)
 Height(v)  a     b  x   y
           / \   / \
  -----   al ar bl br          -----

  r         : 根节点;
  Height(r) : 树根节点r的高度,也称为树的高度;
  Depth(v)  : 子树根节点v的深度,根节点r的深度为0;
  Height(v) : 子树根节点v的高度,空树的高度取为-1;
  叶子节点  : 没有子节点(子节点为NULL)的节点,其高度为0;

  节点数为n,高度为h;
  二叉树     : h < n < 2^(h+1)  根根等比数列可求解;
  满二叉树   : n = 2^(h+1)      树中所有节点均含有2个孩子节点,或没有孩子节点;
  单链二叉树 : n = h + 1        树中所有节点均只有1个孩子节点,或没有孩子节点;

遍历算法

二叉树的遍历主要包括深度优先遍历(先序、中序、后序)和广度优先遍历(层次遍历)。
深序优先遍历递归式的算法就不说了,太简单了,这里主要说下迭代式的算法。

  (1) 基本顺序
      D
     / \
    L   R
  先序遍历: D --> L --> R

  (2) 实现
           d
         /   \
       l1    r1 /
      / \      / => 对任何以d为根节点的子树,执行以下过程(称之为DLR过程):
    l2  r2    /     因为先访问D(即d,l1,l2),所以在访问D的过程中,将R(r1,r2)按斜线方向入栈;
                    之后将出栈的节点R,当成新的子树d节点,执行DLR过程;

  先序遍历    : d - l1 - l2 - r2 - r1
  d - l1 - l2 : 从d开始,沿着left一直visit下去(注意将right入栈);
  r2 - r1     : 看成一个Stack,r2最后入栈,但最先访问;
                访问r2时,同样从r2开始,沿着left一直visit下去(注意将right入栈);
  (1) 基本顺序
      D
     / \
    L   R
  先序遍历: L --> D --> R

  (2) 通过迭代实现:
         /    d
        /   /   \
       /  l1    r1
      /  / \
     / l2  r2
    / => 对任何以d为根节点的子树,执行以下过程(称之为LDR过程):
         因为需要访问完L后才能访问D,故先将L(d,l1,l2)按斜线方向入栈(即沿left入栈);
         然后每个出栈的节点,先访问,再转向R(r2,r1),再将R当成新子树的根节点d,执行LDR过程;

  中序遍历  : l2 - l1 - r2 - d - r1
  Stack示例 : 将L一直入栈,直至栈为 [d - l1 - l2>,然后弹出l2,访问l2,转向l2->right;
              l2->right为nullptr,故不需要将L入栈,继续弹出l1,访问l1,转向l1->right;
              l1->right不为nullptr,故需要将L入栈,然后......;
              一直重复上述过程即可;
  (1) 基本顺序
      D
     / \
    L   R
  先序遍历: L --> R --> D

  (2) 通过迭代实现:
         /    d
        /   /   \
       /  l1    r1
      /  / \
     / l2  r2
    / => 对任何以d为根节点的子树,执行以下过程(称之为LRD过程):
         因为需要访问完L后才能访问R,访问完R后才能访问D,故先将L(d,l1,l2)按斜线方向入栈(即沿left入栈);
         对每个出栈的节点:
            <1>如果:没有右子树,或者右子树已经访问完毕,则访问之,然后继续弹出节点,继续<1>过程;
            <2>否则:转向R(r2,r1),再将R当成新子树的根节点d,执行LRD过程;

  后序遍历 : l2 - r2 - l1 - r1 - d
  层次遍历即是“一行接一行”地遍历;
              d
            /   \
          l1    r1
         / \
       l2  r2

  层次遍历  : d - l1 - r1 - l2 - r2
  将遍历的顺序,看成一个队列:d最先入队,故最先访问;
                              r2最后入队,故最后访问;

二叉树接口

二叉树的基本操作,可以沿用至接下来要讲的Binary Search Tree等,这里列个表总结下。

内容 接口
二叉树节点 Binary Node
节点高度 Binary Node Height()
树节节点 Binary Tree Root()
先序遍历 Binary Tree PreOrder()
中序遍历 Binary Tree InOrder()
后序遍历 Binary Tree PostOrder()
层次遍历 Binary Tree LayerOrder()

Binary Search Tree

二叉搜索树(BST),着重于查找,而且是快速的查找。

查找节点

  • 查找的优势
  为了快速查找,做如下约定:
          D
         / \
        L   R
  对于二叉树的任何一个节点,有大小关系: L <= D <= R,即BST的中序遍历是有序的;
  这样,二叉搜索树的查找,每经过一次比较,就能减小一半的查找范围(和二分查找法类似了)。

  简单C式的代码实现:

Node* Search (Node* x, Data ele)
{
    if (!x || x->data == ele)
        return node;
    return Search(x->data < ele ? x->left : x->right);
}
  • 查找的不足

    对于单链二叉树,二叉搜索树的查找优势就没了,如:
     r
      \
       r1
         \
          r2
          ...
    二叉搜索树就成了线性查找了。
    

基于二叉搜索树的优势与不足,我们需要做如下思考:
为了保证二叉搜索树的优势,对于树中的每一个节点,需要使得


(1). 左子树与右子树尽可能接尽满二叉树;

(2). 左子树与右子树的高度尽可能接尽;

接下来的AVL Tree、Splay Tree、RebBlack Tree均是为尽可能达到上述两点,一般统称为平衡二叉树(Balanced Binary Search Tree, BBST)。

插入节点

        r
      /   \
     a     b
    / \   / \
   w   x y   z
      /
     *(NULL)

  根据二叉搜索树的Search算法,最终查找得到的是一个节点,或是已存在的节点,或是NULL节点。
  如:查找一个位于(a,x)区间的数据,最终返回的就是x的left节点,
      即 '*' 所表示的NULL节点,将新数据插入到x->left处即可。

删除节点

  • 直接后继节点

因为要保证二叉树的有序性,删除节点比插入节点稍麻烦点,需要先明白什么是节点的直接后继。

  节点r在中序遍历下,其后面的节点d即为r的直接后继,如下所示:
  根据有无右子树,可做如下判定,
  (1)有右子树:r为当前节点,d为r的直接后继,即r右子树中最靠左(最小)的节点;
     r
    / \
   L   a
      / \
     d   c
      \
       b

  (2)无右子树:r为当前节点,d为r的直接后继,即“将r包含于其左子树中的最低祖先节点”;
         e
        / \
       d  R
      / \
     b   c
    / \
   a   r
      /
     L
  • 删除节点

删除节点麻烦的原因就是,删除节点后,需要找到顶替原来位置的新节点,并且能够保证中序遍历的有序性。所以,直接后继就是一个理想的顶替节点,如下所示:

  待删除的节点为d,根据d的孩子节点,可以如下判定,
  (1) 没有孩子节点 : 直接删除d即可

  (2) 只有左孩子节点 或 只有右孩子节点
    a                a
   / \              / \
  T0  b            T0  b
     / \     =>       / \
    T1  d            T1  c (d)
       /
      c
  将d->right和d->left顶替在d的位置;

  (3) 同时有左右孩子节点
     d                  c
   /   \              /   \
  T0    b            T0    b
      /   \     =>       /   \
     c     T1           d     T1
      \   / \            \   / \
       a T2 T3            a T2 T3
  节点c为节点d直接后继,交换c和d,然后按情况(1)或(2)删除d;

通过以上图解,可以看到,直接后继节点的作用是将有两个孩子的节点,转化成最多只有一个孩子的节点。其实接替节点也可以使用如下节点:待删除节点左子树中最大的节点,或右子树中最小的节点。

BST接口

BST的查找等基本操作,各种二叉搜索树均可以沿用,这里列个表总结下。

特点 内容
查找节点 BST Search()
插入节点 BST Insert()
删除节点 BST Remove()
旋转调整(后面会讲) BST Rotate()

AVL Tree

AVL Tree即也称为AVL平衡树。这里所谓的平衡,就是直接从上一节(Binary Search Tree)中“查找节点”的(1)(2)出发,使得二叉搜索树的“形状”尽可能的接尽“等腰三角形”。

AVL平衡定义

  对任一节点v,平衡的相关定义如下
  理想平衡 : height(v->left) = height(v->right)     即左子树树高与右子树树高相等
  平衡因子 : height(v->left) - height(v->right)     即左子树树高与右子树树高的差
  AVL平衡  : -2 < 平衡因子 < 2                      即平衡因子的范围为[-1,1]

  AVL平衡树,即是树中所有节点均达到AVL平衡,如以下等形式:
    r          r          r
   / \        / \        / \
  a   b      a   b      a   b
            /          / \
           c          c   d

失衡与复衡

  • 插入节点引起AVL失衡
  (1)插入节点,引起树失衡的基本情况共4种:
         (1)     (2)          (3)       (4)
          g       g            g         g
         / \     / \          / \       / \
        p   t   t   p        p   t     t   p
       /             \        \           /
      v               v        v         v
     /               /        /         /
    i               i        i         i

  g,p,v,t四个节点原本可以达到AVL平衡,但插入节点i做为v的子节点后,就会引起节点g失衡;
  (因为插入节点i,使得g的高度变化,从而引起g的平衡因子超范围,即引起g失衡)。

  这里估且设定 g->parent 节点为 x;

  (2)恢复平衡的方法,即将g,p,v三个基本节点调整到以下形状:
        (1)      (2)          (3)       (4)
         p        p            v         v
        / \      / \          / \       / \
       v   g    g   v        p   g     g   p
      /     \  /   /          \   \   / \
     i      t t   i            i   t t   i

  需要注意的是:
  恢复平衡后,g所在位置(即现在的p,v节点处)节点的高度也会同样恢复;
  所以从 x 节点以上的所有祖先节点高度均不会变化,即全树恢复平衡。
  • 删除节点引起AVL失衡
  (1)插入节点,引起树失衡的基本情况共4种:
         (1)     (2)          (3)       (4)
          g       g            g         g
         / \     / \          / \       / \
        p   t   t   p        p   t     t   p
       /             \        \           /
      v               v        v         v

  g,p,v,t四个节点原本可以达到AVL平衡,但删除节点t后,就会引起节点g失衡;
  (因为删除节点t,使得g的高度变化,从而引起g的平衡因子超范围,即引起g失衡)。

  这里估且设定 g->parent 节点为 x;

  (2)恢复平衡的方法,即将g,p,v三个基本节点调整到以下形状:
        (1)      (2)          (3)       (4)
         p        p            v         v
        / \      / \          / \       / \
       v   g    g   v        p   g     g   p

  需要注意的是:
  恢复平衡后,g所在位置(即现在的p,v节点处)节点的高度可能再次发生变化,可能引起g->parent失衡;
  所以,需要自 x 节点开始,沿着 parent 方向,检测所有祖先节点是否发生失衡,直至树根节点Root;

旋转调整

旋转调整(BST Rotate)是BST的基本过程,不仅可以使得AVL树恢复平衡,还可以保证AVL树中序遍历的有序性,之后的RedBlack Tree也会用到。

参考代码

  示意图如下(包括对称情况):
  (1)单旋:
  zag(旋转gp)                       | zig(旋转gp)
    g                       p       |        g                       p
  /   \                   /   \     |      /   \                   /   \
 T0    p       =>        g     v    |     p    T3    =>           v     g
      / \               / \   / \   |    / \                     / \   / \
     T1  v             T0 T1 T2 T3  |   v  T2                   T0 T1 T2 T3
        / \                         |  / \
       T2 T3                        | T0 T1

  (2)双旋:
  zig-zag(先zig旋转pv,再zag旋转gv) | zag-zig(先zag旋转pv,再zig旋转gv)
    g                       v       |      g                       v
  /   \                   /   \     |    /   \                   /   \
 T0    p                 g     p    |   p    T3                 p     g
      / \               / \   / \   |  / \                     / \   / \
     v  T3     =>      T0 T1 T2 T3  | T0  v          =>       T0 T1 T2 T3
    / \                             |    / \
   T1 T2                            |   T1 T2

  (3) 代码实现思路
  先根据g,p,v之间的父子节点关系,分清是哪种类型,然后代入a,b,c的位置;
  同样,子节点T0~T3则代入w,x,y,z的位置。
          b
        /   \
       a     c
      / \   / \
     w   y x   z

时间复杂度

AVL平衡树的查找、插入、删除操作,最坏情况下的时间复杂度均为O(logn),这里的n为节点数。但AVL平衡的维持,需要额外借助高度或者说平衡因子,以及旋转操作。特别地,删除/插入节点后的旋转操作,增加了算法时间消耗。

操作 时间复杂度
查找 O(logn)
插入 O(logn)
删除 O(logn)

Splay Tree

伸展树(Spaly Tree)是通过间接的方式,使得二叉树接尽平衡。

伸展过程

伸展树的核心即是伸展,伸展过程,是基于一个这样的考量,如下图所示:
经常访问的节点,移到树根节点Root处;这样,随着时间的推移,在Root附近将聚集越来越多的经常访问的节点,可以加快了搜索速度。同时,伸展过程最好能控制好树的高度。

      *       -----
     / \      Root附近聚集了经常访问的节点,可以加快搜索速度
    /   \     -----
   /     \
  /__     \
     \__   \  访问底层的节点仍需要较长时间,最长的时间和树的高度有关,所以需要控制好树的高度
        \___\ -----
  • 伸展原理

查看代码

  伸展的目的是通基本伸展过程,使目标节点v向上移,直至成为根节点Root;
  原则是优先双层伸展,直至最后只剩下一层,才使用单层伸展。
  (1)双层伸展
  zag-zag(先zag旋转gp,再zag旋转pv) | zig-zig(先zig旋转gp,再zig旋转pv)
    g                       v       |        g                  v
  /   \                   /   \     |      /   \               / \
  T0   p       =>        p    T3    |     p    T3     =>     T0   p
      / \               / \         |    / \                     / \
     T1  v             g  T2        |   v  T2                   T1  g
        / \           / \           |  / \                         / \
       T2 T3         T0 T1          | T0 T1                       T2 T3
                                    |
  (与AVL旋转相同)                   | (与AVL旋转相同)
  zig-zag(先zig旋转pv,再zag旋转gv) | zag-zig(先zag旋转pv,再zig旋转gv)
  双旋:                             |  双旋:
    g                       v       |      g                       v
  /   \                   /   \     |    /   \                   /   \
  T0   p                 g     p    |   p    T3                 p     g
      / \               / \   / \   |  / \                     / \   / \
     v  T3     =>      T0 T1 T2 T3  | T0  v           =>      T0 T1 T2 T3
    / \                             |    / \
   T1 T2                            |   T1 T2

  (2)单层伸展
  zig:                              | zag:
      p                   v         |     p                   v
     / \                 / \        |    / \                 / \
    v  T2      =>       T0  p       |   T0  v       =>      p  T2
   / \                     / \      |      / \             / \
  T0  T1                  T1 T2     |     T1  T2          T0 T1
  • 伸展效果
  伸展过程既可以使目标节点聚在Root附尽,也控制好树的高度。
  查找'1':
  伸过数次伸展,'1'成为了根节点,而树的高度也减小了一半;
                8              8            8             8             1
               /              /            /             /      =>       \
              7              7            7             1   (伸展1,8)     8
             /              /            /               \               /
            6              6            6                 6             6
           /              /            /     =>          / \           / \
          5              5            1  (伸展1,6,7)    4   7         4   7
         /              /              \               / \           / \
        4              4     =>         4             2   5         2   5
       /              /  (伸展1,4,5)   / \             \             \
      3              1                2   5             3             3
     /       =>       \                \
    2   (伸展1,2,3)    2                3
   /                    \
  1                      3

  查找'3':
  伸过数次伸展,'3'成为了根节点,'1'仍在根节点附近,树的高度再度减小一半;
       1                   1                 1                   3
        \                   \                 \        =>     /     \
         8                   8                 3  (伸展1,3)  1       6
        /                   /                 / \             \    /   \
       6                   6        =>       2   6             2  4     8
      / \                 / \  (伸展3,6,8)  /   \               \      /
     4   7               3   7             4     8               5    7
    / \        =>       / \                 \   /
   2   5  (伸展3,2,4)  2   4                 5 7
    \                   \
     3                   5

查找、插入、删除

查找过程中刚查找的节点,插入过程中新插入的节点,删除过程中待删除的节点,均可认为是经常访问的节点。值得注意的是,伸展树的查找、插入、删除,依靠查找操作均会改变树的拓扑结构(因为都会进行伸展过程)。

  • 插入与删除节点
         a            r
        / \            \
       b   c            a
      / \       =>     / \
     d   e    Splay   d   c
    /                  \
   r                    b
                         \
                          e

  若插入的节点x(x<r):先查找x,最终会到达r节点,之后将r伸展到根节点,然后将x作为r的左孩子插入树中。
  若要删除节点r: 同样先查找r,最终会到达r节点,之后将r伸展到根节点,然后删除r,重新合并r的左右子树。

相对于AVL平衡树,伸展树不需要平衡因子,更易编程实现,而伸展树查找、插入、删除的时间复杂度同样为O(logn),与AVL平衡树相当。

操作 时间复杂度
查找 O(logn)
插入 O(logn)
删除 O(logn)

RebBlack Tree

红黑树,顾名思义,就是节点有颜色的二叉搜索树。

基本性质

红黑树约定:

  • 1.树根:必为黑;
  • 2.外部节点(NIL节点):均为黑(外部节点,或说NIL节点,即是一个为NULL的黑色叶子节点);
  • 3.其余节点:若为红,则子节点只能为黑;
  • 4.从任一节点到其每个(子孙)外部节点:途中路径经过的黑节点数相同;

红黑树的查找沿用BST的Search即可;不过,对于红黑树的每次插入/删除节点,均要保证上述4点仍然成立。

AVL树为了保证平衡因子在[-1,1]之间,失衡时需要进行较多的旋转操作。红黑树相对于AVL树来说,牺牲了部分平衡性,以换取减少插入/删除时旋转操作,整体性能优于AVL树。

插入节点

插入节点需要先用BST Search得到新节点插入的位置。新插入的节点均初始化为红色(如果设为黑色,就会导致根节点到NIL节点的路径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能会导致出现两个连续红色节点的冲突,那么可以通过颜色调换和树旋转来调整)。根据临近节点的颜色,进行相应的调整。
插入节点示意图:

  设新插入节点为x,x的父节点为p,p的父节点为g,x的叔父节点为u(也即p的兄弟节点);
  带有R的节点为红,未做特殊说明则为黑;

  x为红,p为黑,则节点插入完成;
  x为红,p也为红,即为双红冲突问题。
       (1)        (2)        (3)        (4)
        g          g          g          g
       / \        / \        / \        / \
      pR  u      pR  u      u   pR     u   pR
     /            \            /            \
    xR             xR         xR             xR
  双红问题普遍情况有以上4种,且均是两两对称形式,调整方法是类似的;
  还有特殊情况就是,新插入的节点x就是根节点。

针对不同的情况,进行相应的调整(以第(1)(2)种情况为例,(3)(4)情况对称,调整类似):

  • (RR1)x是Root节点
  xR => xB
  将x染成黑色即可。
  • (RR2)p为红(则g必为黑),u为黑(子树T3的根节点为u)
  p,x均为红,违返了约定3;直接将x染成黑,则违反了约定4。

  先用BST Rotate的单旋zig,再重染色 | 先用BST Rotate的双旋zig-zag,再重染色
        g                           |       g
       / \              p           |      / \              x
      pR T3[u]        /   \         |     pR T3[u]        /   \
     / \        =>   xR    gR       |    / \        =>   pR    gR
    xR T2           / \   / \       |   T0 xR           / \   / \
   / \             T0 T1 T2 T3(u)   |     / \          T0 T1 T2 T3(u)
  T0 T1                             |    T1 T2

  调整前,T0~T3向上的第一个黑节点为子树根节点g;
  变换后,T0~T3向上的第一个黑节点为仍为子树根节(p或x),同时满足约定3和4;
  故调整前后,子树根节点到(子孙)外部节点所经过的黑节点数不变。
  • (RR3)p为红(则g必为黑),u为红(子树T3的根节点为u)
  重染色,递归检测g的双红问题
         g                   gR      |     g                   gR
       /   \               /   \     |    / \                 / \
      pR   T3[uR]         p    T3[u] |   pR T3[uR]           p  T3[u]
     / \          =>     / \         |  / \          =>     / \
    xR T2               xR T2        | T0 xR               T0 xR
   / \                 / \           |   / \                 / \
  T0 T1               T0 T1          |  T1 T2               T1 T2

  调整前后,pu变黑,但g变红,故从g到其每个(子孙)外部节点上的黑节点数量仍不变;
  但因为g的父节点可能为红,故需要继续对g进行双红检测。

删除节点

删除节点同样需要先用BST Search得到待删除节点的位置,然后用BST Remove删除节点。之后再根据删除节点和接替节点的颜色,进行相应的调整。
删除节点示意图:

  设x为待删除的节点,r为接替x所在位置的节点(且r为其所在子树的根节点),p为x父节点,s为x兄弟节点;
  带有R的节点为红,未做特别说明则为黑;
  根据BST Remove算法,在删除x时,x必定最多只有一个子树分支。

    x红,r黑,p黑         |  x黑,r红,p红或黑
     p            p       |    p            p
    / \          / \      |   / \          / \
   s   xR   =>  s   T[r]  |  s   x    =>  s   T[r]
        \                 |       \
         T[r]             |        T[rR]
  若x和r只有一个为红,则将r染黑即可;
  若x和r均为黑,删除节点x后,节点p-r所在路径的黑节点数少了1,此即为双黑问题。
  双黑调整原理:通过旋转和染色,使得节点p-r所在路径黑节点数加1,
                              或使得节点p-s所在路径黑节点数减1,再递归调整。

针对不同的双黑情况,进行相应的调整:

  • (BB1)s为黑,且s至少有一个红子节点,p可黑可红
  先BST Rotate,再染色:
  s继承p的颜色,tp变黑              | t继承p的颜色,sp变黑
        p                           |     p
       / \                s         |    / \                t
      s   T3[r]         /   \       |   s  T3[r]          /   \
     / \          =>   t     p      |  / \          =>   s     p
    tR T2             / \   / \     | T0  tR            / \   / \
   / \               T0 T1 T2 T3[r] |    / \           T0 T1 T2 T3[r]
  T0 T1                             |   T1 T2

  调整前后,T0~T3到子树根节点经过的黑节点如下所示:
  T0 - s - p          T0 - t - s    | T0 - s - p          T0 - s - t
  T1 - s - p    =>    T1 - t - s    | T1 - s - p    =>    T1 - s - t
  T2 - s - p          T2 - p - s    | T2 - s - p          T2 - p - t
  T3 - x - p          T3 - p - s    | T3 - x - p          T3 - p - t
  可以看到,在调整后,节点p-r所在路径黑节点数加了1(即节点s或t)。
  且不改变T0~T2所在路径黑节点的数量。
  • (BB2.1)s为黑,且s两个子节点均为黑,p为红
  重染色:s变红,p变黑
      pR                    p
     / \                   / \
    s  T2[r]      =>      sR T2[r]
   / \                   / \
  T0 T1                 T0 T1
  s变红,p-s所在路径黑节点数减1;
  p变黑,p-s和p-r所在路径黑节点数均加1;
  最终,p-s和p-r所在路径黑节点数不变;
  • (BB2.2)s为黑,且s两个子节点均为黑,p为黑
  重染色(s变红),再递归对p进行双黑检测;
      p                     p
     / \                   / \
    s  T2[r]      =>      sR T2[r]
   / \                   / \
  T0 T1                 T0 T1
  s变红,p-s所在路径黑节点数减1;
  p颜色不变,所以p-s和p-r所在路径的黑节点数均减1,故需要对p继续进行双黑检测。
  • (BB3)s为红,则p必为黑,s子节点必为黑
  先旋转:t选取与s同侧的(s为p的左子节点,则t也选s的左子节点),这样只需要一次旋转;
  再染色:s变黑,p变红;
  再对r进行双黑检测:因为p为红,故以pR-T2-T3形成的子树必为(BB1)或(BB2.1)情况。
        p
       / \                s
      sR T3[r]    =>    /   \
     / \               t     pR
    t  T2             / \   / \
   / \               T0 T1 T2 T3[r]
  T0 T1
  p变红,p-r所在路径黑节点数再次减少了1,共减少了2;
  s变成p的父节点,p-r所在路径黑节点数加1,共减少了1,故需要对r继续进行双黑检测。

附:代码实现


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 [ yehuohan@gmail.com ]

文章标题:字符画之画二叉搜索树

本文作者:Yehuohanxing

发布时间:2018-01-15, 17:35:07

最后更新:2018-04-03, 23:26:42

原始链接:http://yehuohan.github.io/2018/01/15/笔记/字符画之画二叉搜索树/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录