二叉搜索树

二叉搜索树的概念

  • 一棵二叉搜索树是以一棵二叉树来组织的，这样一棵树可以使用一个链表数据结构来表示，其中每个结点就是一个对象。
  • 除了$key$和卫星数据之外，每个结点还包含$left$、$right$和$p$，它们分别指向结点的左孩子、右孩子和双亲。
  • 如果某个孩子结点和父结点不存在，则相应属性的值为$NIL$。
  • 根结点是树中唯一父指针为$NIL$的结点。

二叉搜索树.png

二叉搜索树的性质

设$x$是二叉搜索树中的一个结点。

  • 如果$y$是$x$左子树中的一个结点，那么$y.key \leq x.key$。
  • 如果$y$是$x$右子树中的一个结点，那么$y.key \geq x.key$。

简记：左小右大

二叉搜索树的查询

我们使用下面的过程在一棵二叉搜索树中查找一个具有给定关键字的结点。输入一个指向树根的指针和一个关键字$k$，如果这个结点存在，ITERATIVE-TREE-SEARCH返回一个指向关键字为$k$的结点的指针；否则返回$NIL$。

ITERATIVE-TREE-SEARCH(x,k)

while x != NIL and k != x.key 
    if k < x.key
        x = x.left
    else x = x.right
return x

  • 这个过程从树根开始查找，并沿着这棵树中的一条简单路径向下进行，对于遇到的每个结点$x$，比较关键字$k$与$x.key$。

    • 如果两个关键字相等，查找终止。
    • 如果$k$小于$x.key$，查找在左子树中继续，因为二叉搜索树性质蕴含了$k$不可能被存储在右子树中。
    • 对称地，如果$k$大于$x.key$，查找在右子树继续。
  • 从树根开始查询期间遇到的结点就形成了一条向下的简单路径，所以ITERATIVE-TREE-SEARCH的运行时间为$O(h)$，其中$h$是这棵树的高度。

二叉搜索树的插入

要将一个新值$v$插入到一棵二叉搜索树$T$中，需要调用过程TREE-INSERT。该过程以结点$z$作为输入，其中$z.key=v,z.left=NIL,z.right=NIL$。这个过程要修改$T$和$z$的某些属性，来把$z$插入到树中的相应位置上。

TREE-INSERT(T,z)

// 初始化
y = NIL
x = T.root

// 找到要插入的位置
while x != NIL
    y = x
    if z.key < x.key
        x = x.left
    else x = x.right

// 插入操作
z.p = y
if y == NIL
    T.root = z    // tree T was empty
elseif z.key < y.key
    y.left = z
else y.right = z

正如ITERATIVE-TREE-SEARCH一样，TREE-INSERT从树根开始，指针$x$记录了一条向下的简单路径，并查找要替换的输入项$z$的$NIL$。该过程需要遍历指针$y$作为$x$的双亲。

  • 初始化后，第8~12行的$while$循环使得这两个指针沿树向下移动，向左还是向右移动取决于$z.key$和$x.key$的比较，直到$x$变成$NIL$。
  • 这个$NIL$占据的位置就是输入项$z$要放置的位置。
  • 我们需要遍历指针$y$，这是因为找到$NIL$时要知道$z$属于哪个结点。
  • 第15~20行设置相应的指针，使得$z$插入其中。

与其他搜索树上的原始操作一样，过程TREE-INSERT在一棵高度为$h$的树上的运行时间为$O(h)$。

红黑树

红黑树的概念

红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是$RED$或$BLACK$。通过对任何一条从根到叶子的简单路径上各结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

  • 树中每个结点包含5个属性：$color$、$key$、$left$、$right$和$p$。
  • 如果一个结点没有子节点或父结点，则该结点相应指针属性的值为$NIL$。
  • 我们可以把这些$NIL$视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

（a）：显示了一个红黑树的例子。

（b）：为了便于处理红黑树代码中的边界条件，使用一个哨兵来代表$NIL$。对于一棵红黑树$T$，哨兵$T.nil$是一个与树中普通结点有相同属性的对象。它的$color$属性为$BLACK$，而其他属性$p$、$left$、$right$和$key$可以设为任意值。所有指向$NIL$的指针都用指向哨兵$T.nil$的指针替换。

（c）：我们通常将注意力放在红黑树的内部结点上，因为它们存储了关键字的值，所画的红黑树可以忽略叶结点。

红黑树

红黑树的性质

一个红黑树是满足下面红黑性质的二叉搜索树：

  1. 每个结点或是红色的，或是黑色的。
  2. 根结点是黑色的。
  3. 每个叶子结点（$NIL$）是黑色的。
  4. 如果一个结点是红色的，则它的两个子结点都是黑色的。
  5. 对于每个结点，从该结点到其后代叶结点的简单路径上，均包含相同数目的黑色结点。

旋转

为了维护红黑树的性质，必须要改变树中某些结点的颜色以及指针结构。指针结构的修改是通过旋转来完成的，这是一种能保持二叉搜索树性质的搜索树局部操作。当在某个结点$x$上做左旋时，假设它的右孩子为$y$而不是$T.nil$；$x$可以为其右孩子不是$T.nil$结点的树内任意结点。左旋以$x$到$y$的链为“支轴”进行。它使$y$成为该子树新的根结点，$x$成为$y$的左孩子，$y$的左孩子成为$x$的右孩子。

旋转.png

在LEFT-ROTATE的伪代码中，假设$x.right \neq T.nil$且根结点的父结点为$T.nil$。

LEFT-ROTATE(T,x)

// set y
y = x.right

// turn y's left subtree into x's right subtree
x.right = y.left
if y.left != T.nil
    y.left.p = x

// link x's parent to y
y.p = x.p
if x.p == T.nil
    T.root = y
elseif x== x.p.left
    x.p.left = y
else x.p.right = y

// put x on y's left
y.left = x
x.p = y

左旋

红黑树的插入

我们可以在$O(lg_n)$时间内完成向一棵含$n$个结点的红黑树中插入一个新结点。为了做到这一点，可用二叉搜索树的TREE-INSERT过程的一个略作修改的版本来将结点$z$插入树$T$内，就好像$T$是一棵普通的二叉搜索树一样，然后将$z$着为红色。为保证红黑性质能继续保持，我们调用一个辅助程序RB-INSERT-FIXUP来对结点重新着色并旋转。调用RB-INSERT(T,z)在红黑树$T$内插入结点$z$，假设$z$的$key$属性已被事先赋值。

RB-INSERT(T,z)

// 初始化
y = T.nil
x = T.root

// 找到要插入的位置
while x != T.nil
    y = x
    if z.key < x.key
        x = x.left
    else x = x.right

// 插入操作
z.p = y
if y == T.nil
    T.root = z    // tree T was empty
else if z.key < y.key
    y.left = z
else y.right = z

// 维护z的属性，可在调用前做
z.left = T.nil
z.right = T.nil
z.color = RED

// 维护红黑树
RB-INSERT-FIXUP(T，z)

RB-INSERT-FIXUP结论

将红黑树重新涂色共有6种情况，但根据对称性可以分成两类，下面列举了当$z$的父结点$z.p$是左孩子的情况，右孩子可镜像推出。

  1. 当$z$、$z$的父结点$z.p$、$z$的叔结点$y$都是红色时，将$z$的父结点$z.p$和$z$的叔结点$y$涂成黑色、$z$的祖父结点$z.p.p$涂成红色，然后$z$上跳两层。
  2. 当$z$和$z$的父结点$z.p$是红色、$z$的叔结点$y$是黑色、$z$是右孩子时，将$z$上跳一层然后左旋。
  3. 当$z$和$z$的父结点$z.p$是红色、$z$的叔结点$y$是黑色、$z$是左孩子时，将$z$的父结点$z.p$涂成黑色、$z$的祖父结点$z.p.p$涂成红色，然后$z$的祖父结点$z.p.p$右旋，注意这里$z$是不动的。
RB-INSERT-FIXUP(T，z)

while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED
            z.p.color = BLACK        // case 1
            y.color = BLACK            // case 1
            z.p.p.color = RED        // case 1
            z = z.p.p                // case 1
        else if z == z.p.right
            z = z.p                    // case 2
            LEFT-ROTATE(T,z)        // case 2
        z.p.color = BLACK            // case 3
        z.p.p.color = RED            // case 3
        RIGHT-ROTATE(T,z.p.p)        // case 3
    else (same as then clause with "right" and "left" exchanged)
T.root.color = BLACK

重着色

RB-INSERT-FIXUP分析

<u>To be updated</u>

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/172/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：March 31st, 2021 at 01:13 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏