数据结构之二叉搜索树

马谦马谦马谦

615
文章

17
评论

2018 年 11 月 29 日 10:43:49数据结构和算法评论1,096字数 2455阅读 8 分 11 秒阅读模式

一、二叉搜索树

1.1 什么是二叉搜索树

算法导论中对二叉搜索树（Binary Search Tree, 简称 BST）的定义：

设 x 是二叉搜索树中的一个节点，如果 y 是 x 左子树中的一个节点，那么 y.key<=x.key 。如果 y 是 x 右子树中的一个节点，那么 y.key>=x.key 。

以下两棵树就是二叉搜索树：

数据结构之二叉搜索树-图片1

其中 a 是一个包含 6 个节点，高度为 2 的二叉搜索树。 b 是一个包含相同关键字、高度为 4 的低效二叉树。

注意：树中包含了两个相同的节点 5，在实际用途中，很少把相同的关键字放到二叉搜索树中。

二叉搜索树主要的操作：

SEARCH：查找某个节点在树中的位置
MINIMUM：求以指定节点为根的树中的最小元素
MAXIMUM：求以指定节点为根的树中的最大元素
PREDECESSOR：求指定节点的前驱节点
SUCCESSOR：求指定节点的后继节点
INSERT：在树中插入节点
DELETE：删除节点

定理：二叉搜索树中的以上各个操作都是在 O(h)时间内完成。

1.2 树节点定义

二叉搜索树的节点需要包含以下元素：

节点的键值，也就是 key
父节点和左右子节点的指针

假设 key 值类型为 int，那么树节点的结构应该为：

struct bst_tree_node_st {
    int key;
    struct bst_tree_node_st *lchild;
    struct bst_tree_node_st *rchild;
    struct bst_tree_node_st *parent;
};

struct bst_tree_node_st {

int key;

struct bst_tree_node_st *lchild;

struct bst_tree_node_st *rchild;

struct bst_tree_node_st *parent;

};

二、二叉树操作

2.1 查找操作 ( SEARCH)

通过二叉搜索树的性质很容易得到查找算法：从树根开始查找，沿着树的路径一直向下。对每个遇到的节点 x，比较关键字 k 和 x.key，如果两个关键字相等，查找终止。如果 k 小于 x.key，在 x 的左子树中继续查找。否则就在 x 的右子树中继续查找。

伪代码如下（来自《算法导论》)：

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(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)

上面采用了递归的方法来进行查找，递归最明显的特点就是简单，代码量小。但是在树高度很高时候，递归就会产生巨大的内存消耗和更多的 CPU 消耗，因为要频繁对函数及参数压栈，并且函数中栈是有大小限制的，不能无限递归。

大部分时候建议使用非递归查找，非递归查找的伪代码实现为：

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

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

非递归对应的 C 语言描述：

struct bst_tree_node_st *bst_tree_search(struct bst_tree_st *t, int key) {
    struct bst_tree_node_st *p = t->root;
    while (p != NULL && key != p->key) {
        if (key < p->key)
            p = p->lchild;
        else
            p = p->rchild;
    }
    return p;
}

struct bst_tree_node_st *bst_tree_search(struct bst_tree_st *t, int key) {

struct bst_tree_node_st *p = t->root;

while (p != NULL && key != p->key) {

if (key < p->key)

p = p->lchild;

else

p = p->rchild;

}

return p;

}

2.2 求最大元素 (MAXIMUM) 和最小元素 (MINIMUM)

根据二叉树的性质可知：最小的节点一定是最左边的节点，最大的节点一定是最右边的节点。

例如对下面这个二叉树而言，最小的元素是 2，最大的元素是 20 。

数据结构之二叉搜索树-图片2

找最小的元素只要一直在左子节点中查找，直到节点的左节点是 NULL 为止。相反，找最大的元素，只要在节点的右节点中查找，直到右节点是 NULL 为止。

/*
 * 得到某个子树中的最小元素节点
 * @root 待查找的子树根节点
 * @return 返回最小元素节点的指针，如果最小元素就是 node，那么返回 node
 */
struct bst_tree_node_st *bst_tree_minimum(struct bst_tree_node_st *root) {
    struct bst_tree_node_st *p = root;
    while (p != NULL && p->lchild != NULL)
        p = p->lchild;
    return p;
}

/*
 * 得到某个子树中的最大元素节点
 * @root 待查找的子树根节点
 * @return 返回最大元素节点的指针，如果最大的元素就是 node，那么返回 node
 */
struct bst_tree_node_st *bst_tree_maximum(struct bst_tree_node_st *root) {
    struct bst_tree_node_st *p = root;
    while (p != NULL && p->rchild != NULL)
        p = p->rchild;
    return p;
}

* 得到某个子树中的最小元素节点

* @root 待查找的子树根节点

* @return 返回最小元素节点的指针，如果最小元素就是 node，那么返回 node

struct bst_tree_node_st *bst_tree_minimum(struct bst_tree_node_st *root) {

struct bst_tree_node_st *p = root;

while (p != NULL && p->lchild != NULL)

p = p->lchild;

return p;

}

* 得到某个子树中的最大元素节点

* @root 待查找的子树根节点

* @return 返回最大元素节点的指针，如果最大的元素就是 node，那么返回 node

struct bst_tree_node_st *bst_tree_maximum(struct bst_tree_node_st *root) {

struct bst_tree_node_st *p = root;

while (p != NULL && p->rchild != NULL)

p = p->rchild;

return p;

}

2.3 求前驱 (PREDECESSOR) 和后继 (SUCCESSOR)

节点 x 的前驱节点是指中序遍历中顺序在 x 之前的元素，节点 x 的后继节点指中序遍历中顺序在 x 之后的元素。

以 2.3 节中的二叉树为例，其中序遍历的结果为：2 3 4 6 7 9 13 15 17 18 20 。对于元素 6 而言，它的前驱节点是 4，后继节点是 7 。

数据结构之二叉搜索树-图片3

求前驱节点的过程：

如果节点有左子节点，那么前驱节点一定是左子树中的最大元素。例如 6 的前驱是 4，15 的前驱是 13
如果节点没有左子节点，那么它的前驱就是以它或者以它任一祖先为右儿子的节点，例如上图中节点 9 的前驱是 7，节点 7 的前驱是 6

求后继节点的过程：

如果节点有右子节点，那么后继节点一定是右子树中最小的元素。例如 15 的后继节点是 17，18 的后继节点是 20
如果节点没有右子节点，那么它的后继就是以它或者以它任一祖先为左儿子的节点，例如上图中的 13 的后继节点是 15，17 的后继节点是 18

可以得到的一个结论：树中最小的元素没有前驱节点，树中最大的元素没有后继节点。

求前驱节点和后继节点的 C 语言描述：

/*
 * 求树中某个节点的后继节点
 * @node 当前节点，如果没有后继节点，返回 NULL
 */
struct bst_tree_node_st *bst_tree_successor(struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x = node, *p;
    if (x->rchild)
        return bst_tree_minimum(x->rchild);

    p = x->parent;
    while (p != NULL && p->rchild == x) {
        x = p;
        p = x->parent;
    }
    return p;
}

/*
 * 求树中某个节点的前驱节点
 * @node 当前节点，如果没有前驱节点，返回 NULL
 */
struct bst_tree_node_st *bst_tree_predecessor(struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x = node, *p;
    if (x->lchild)
        return bst_tree_maximum(x->lchild);

    p = x->parent;
    while (p != NULL && p->lchild == x) {
        x = p;
        p = p->parent;
    }
    return p;
}

* 求树中某个节点的后继节点

* @node 当前节点，如果没有后继节点，返回 NULL

struct bst_tree_node_st *bst_tree_successor(struct bst_tree_node_st *node) {

struct bst_tree_node_st *x = node, *p;

if (x->rchild)

return bst_tree_minimum(x->rchild);

p = x->parent;

while (p != NULL && p->rchild == x) {

x = p;

p = x->parent;

}

return p;

}

* 求树中某个节点的前驱节点

* @node 当前节点，如果没有前驱节点，返回 NULL

struct bst_tree_node_st *bst_tree_predecessor(struct bst_tree_node_st *node) {

struct bst_tree_node_st *x = node, *p;

if (x->lchild)

return bst_tree_maximum(x->lchild);

p = x->parent;

while (p != NULL && p->lchild == x) {

x = p;

p = p->parent;

}

return p;

}

2.4 插入节点 (INSERT)

插入节点和搜索节点的工作方式一样，先根据元素大小找到合适的位置，然后作为子节点插入，每次插入的节点必定是叶子节点。

例如在下面的树中插入元素 13，首先要找到它的父节点 15，然后作为它的左子节点插入：

数据结构之二叉搜索树-图片4

C 语言实现：

/*
 * 在树中插入节点
 * @t 树
 * @node 新节点
 */
void bst_tree_insert(struct bst_tree_st *t, struct bst_tree_node_st *node) {
    struct bst_tree_node_st *x, *y;
    y = NULL;
    x = t->root;
    // 找到合适的插入位置
    while (x != NULL) {
        y = x;
        if (node->key < x->key)
            x = x->lchild;
        else
            x = x->rchild;
    }
    node->parent = y;
    if (y == NULL)
        t->root = node;
    else if (node->key < y->key)
        y->lchild = node;
    else
        y->rchild = node;
}

* 在树中插入节点

* @t 树

* @node 新节点

void bst_tree_insert(struct bst_tree_st *t, struct bst_tree_node_st *node) {

struct bst_tree_node_st *x, *y;

y = NULL;

x = t->root;

// 找到合适的插入位置

while (x != NULL) {

y = x;

if (node->key < x->key)

x = x->lchild;

else

x = x->rchild;

}

node->parent = y;

if (y == NULL)

t->root = node;

else if (node->key < y->key)

y->lchild = node;

else

y->rchild = node;

}

2.5 删除节点 (DELETE)

2.5.1 删除节点的基本操作

相对来说，删除节点要比插入节点复杂许多，它有三种不同的情况：

如果待删除节点 z 没有孩子节点，那么直接把它删除，修改父节点指针即可完成。
如果待删除节点 z 只有一个孩子，那么将这个孩子替换到 z 的位置，修改 z 的父节点指针，指向 z 的子节点。
如果待删除节点 z 有两个孩子，找到 z 的后继节点 y，让 y 占据 z 的位置，同时还要让 y 的右子节点（如果有的话）占据 y 的位置。

前面两种情况相对简单，甚至可以被合并成一种情况。而第三种情况最为复杂，它还能继续向下分解：

z 的后继节点 y 就是 z 的右子节点
z 的后继节点 y 不是 z 的右子节点，这种情况下可以推断出 y 一定不含左子节点，但此时 y 的右子节点 x 又有两种情况：
- x 为空
- x 不为空

下面分别对以上几种情况进行讨论：

2.5.2 删除节点只有一个儿子

只有左子节点的情况

数据结构之二叉搜索树-图片5

只有右子节点的情况

数据结构之二叉搜索树-图片6

不管是左儿子，还是右儿子，直接替换原删除节点即可。

2.5.3 删除节点有两个儿子且后继节点是右儿子

对应情况：

数据结构之二叉搜索树-图片7

只需要把 z 的位置替换成 y 就可以了。

2.5.4 删除节点有两个儿子且后继节点不是右儿子

后继节点 y 不是 z 的右儿子，那么 y 必定没有左儿子（如果 y 有左儿子的话，那么 z 的后继节点肯定就是 y 的左儿子而不会是 y）。

情况对应下图：

数据结构之二叉搜索树-图片8

此时要做的两步操作：

将 y 的右儿子（不管是否为 NULL）替换成 y
将 y 替换成 z

2.5.4 删除节点的代码

添加一个辅助操作 TRANSPLANT，英文意思是移植，表示把一个节点用另一个节点代替：

static void transplant(struct bst_tree_st *t,
    struct bst_tree_node_st *old_node,
    struct bst_tree_node_st *new_node) {
    if (old_node->parent == NULL)
        t->root = new_node;
    else if (old_node == old_node->parent->lchild)
        old_node->parent->lchild = new_node;
    else
        old_node->parent->rchild = new_node;
    
    // 如果替换新节点不是 NULL，设置新节点的父指针指向
    if (new_node != NULL)
        new_node->parent = old_node->parent;

static void transplant(struct bst_tree_st *t,

struct bst_tree_node_st *old_node,

struct bst_tree_node_st *new_node) {

if (old_node->parent == NULL)

t->root = new_node;

else if (old_node == old_node->parent->lchild)

old_node->parent->lchild = new_node;

else

old_node->parent->rchild = new_node;

// 如果替换新节点不是 NULL，设置新节点的父指针指向

if (new_node != NULL)

new_node->parent = old_node->parent;

然后在 TREE_DELETE 操作中调用 TRANSPLANT 完成删除操作：

/*
 * 删除节点
 * @t 树
 * @node 待删除的节点
 */
void bst_tree_delete(struct bst_tree_st *t, struct bst_tree_node_st *node) {
    struct bst_tree_node_st *y;
    if (node->lchild == NULL || node->rchild == NULL)
        // 至少有一个子节点为空，直接用子节点替换
        _transplant(t, node, node->lchild ? node->lchild : node->rchild);
    else {
        // 得到右子树中的最小节点，即节点在右子树中的后继节点
        y = bst_tree_minimum(node->rchild);
        if (y->parent != node) {
            // y 不是删除节点的子节点，用 y 的右节点替换 y
            _transplant(t, y, y->rchild);
            y->rchild = node->rchild;
            y->rchild->parent = y;
        }
        // 用 y 替换删除节点
        _transplant(t, node, y);
        y->lchild = node->lchild;
        y->lchild->parent = y;
    }
}