前言

经过之前数据结构的学习,我们知道如果一个二叉树满足:

  • 若其左子树非空,则左子树上所有节点各自的值都小于根节点的值
  • 若其右子树非空,则右子树上所有节点各自的值都大于根节点的值
  • 其左右子树都是一棵二叉查找树。

则它是一个二叉搜索树(Binary Search Trees, BST)


遍历顺序

对树的遍历,我们来复习一下:

先序遍历

在先序遍历中,对节点的处理工作是在它的诸儿子节点被处理之前(pre)进行的。

先序遍历步骤为:访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。即根左右。

例如下面的这个树:

它遍历的顺序就是ABDECF

后续遍历

和先续遍历不同的是它的访问不是我们所想的从跟开始,而是从左开始:

后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即左右根。

例如之前的这个树:它遍历的顺序就是DEBFCA

因此我们可以发现,这个先和后,指的是跟的先后。

中序遍历

在二叉树中还有一种中序遍历,按照我们之前的说法,它是跟的中序:中

序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。即左根右。

故之前的那颗树的遍历顺序是:DBEAFC

如果我们使用设这个BST是T,x是二叉搜索树中的一个结点。如果y是左子树中的一个结点,那么 y.key ≤ x.key;如果y是右子树中的一个结点,那么 y.key ≥ x.key。那么中序遍历的伪代码为:

INORDER-TREE-WALK(x)
    if x ≠ NIL
        INORDER-TREE-WALK(x.left)
        print x.key
        INORDER-TREE-WALK(x.right)

INORDER-TREE-WALK(T.root)  //从根结点开始

如果x是一棵有n个结点的子树的根,那么调用INORDER-TREE-WALK(x)运行时间O(n),证明省略。


查找BST

二叉搜索树支持SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR等查询操作。在一棵高度为 h 的二叉搜索树上,SEARCH、MINIMUM、MAXIMUM、PREDECESSOR和SUCCESSOR的运行时间为 O(h)

查找(Searching)

TREE-SEARCH(x, k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else return TREE-SEARCH(x.right, k)

TREE-SEARCH(T.root, k)

TREE-SEARCH的运行时间为 O(h),其中 h 为树的高度。

关键字最小元素和关键字最大元素 (Minimum and maximum)

TREE-MINIMUM(x)
    while x.left ≠ NIL
        x = x.left
    return x

TREE-MAXIMUM(x)
    while x.right ≠ NIL
        x = x.right
    return x

TREE-MINIMUM和TREE-MAXIMUM的运行时间均为 O(h),其中 h 为树的高度.

后继和前驱(Successor and predecessor)

TREE-SUCCESSOR(x)
    if x.right ≠ NIL
        return TREE-MINIMUM(x.right)  // leftmost node in right subtree
    else // find the lowest ancestor of x whose left child is an ancestor of x
        y = x.p
        while y ≠ NIL and x == y.right
            x = y
            y = y.p
        return y

TREE-PREDECESSOR(x)
    if x.left ≠ NIL
        return TREE-MAXIMUM(x.left)  // rightmost node in left subtree
    else // find the highest ancestor of x whose right child is an ancestor of x
        y = x.p
        while y ≠ NIL and x == y.left
            x = y
            y = y.p
        return y

TREE-MINIMUM和TREE-MAXIMUM的运行时间均为 O(h),其中为树的高度。


插入和删除(Insertion and deletion)

具体插入与删除的解析,请见:

【数据结构】树 ——二叉树、查找树

插入和删除操作会引起二叉搜索树表示的动态集合的变化,但是二叉搜索树的性质保持不变。在一棵高度为 h的二又搜索树上,INSERT和DELETE的运行时间为 O(h)。

插入

向二叉搜索树T中插入结点z,其关键字为 z.key ,伪代码TREE-INSERT如下

TREE-INSERT(T, z)
    x = T.root  // node being compared with z
    y = NIL  // y will be parent of z
    while x ≠ NIL  // descend until reaching a leaf
        y = x
        if z.key < x.key 
            x = x.left
        else x = x.right
    z.p = y  // found the location - insert z with parent y
    if y == NIL
        T.root = z  // tree T was empty
    else if z.key < y.key
        y.left = z
    else y.right = z 

该过程保持跟踪指针(trailing pointer) y 记录 x 的父结点,TREE-INSERT的运行时间为O(h),其中h为的高度。

删除

从二叉搜索树 T 中删除结点 z 分三种情况

  • 情况一: 如果z没有孩子结点,直接删除, z 的父结点指向z的指针置为NIL。
  • 情况二: 如果z只有一个孩子结点,将这个孩子结点提升到z的位置,z 的父结点指向z的指针改为指向这个孩子结点。
  • 情况三: 如果z有两个孩子结点,找出z的后继 y,让y占据z的位置,z 的右子树变为 y的右子树,z 的左子树变为 y 的右子树。由于y是z的后继,所以y不可能有孩子。
    • 如果y 是z的右孩子,用y 替换z。
    • 如果y在2的右子树中且y 不是z 的右孩子,先用y 的右孩子结点替换 y,然后用y 替换 z。

子程序TRANSPLANT实现了用某子树原先父结点的指向该子树的指针指向另一棵子树,实现了子树的替换。伪代码如下:

TRANSPLANT(T, u, v)
    if u.p == NIL
        T.root = v
    else if u == u.p.left
        u.p.left = v
    else u.p.right = v
    if v ≠ NIL
        v.p = u.p
TREE-DELETE(T, z)
    if z.left == NIL
        TRANSPLANT(T, z, z.right)    // replace z by its right child
    else if z.right == NIL
        TRANSPLANT(T, z, z.left)    // replace z by its left child
    else y = TREE_MINIMUM(z.right)    // y is z's successor
        if y ≠ z.right    // is y farther down the tree?
            TRANSPLANT(T, y, y.right)    // replace y by its right child
            y.right = z.right    
            y.right.p = y    // z's right child becomes y's right child
        TRANSPLANT(T, z, y)    // replace z by its successor y
        y.left = z.left    
        y.left.p = y    // and give z's left child to y which had no left child

TREE-DELETE的运行时间为O(h),其中h为树的高度。


后记

本文介绍了二叉搜索树(Binary Search Trees, BST)的定义和遍历顺序,包括先序遍历、后序遍历和中序遍历。同时,还介绍了BST的查找操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR和SUCCESSOR等查询操作。文章还讲解了BST的插入和删除操作,包括向BST中插入结点和从BST中删除结点的实现方法。在一棵高度为 h 的BST上,SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE的运行时间均为 O(h)。