一、二叉搜索树

1.1 什么是二叉搜索树

算法导论中对二叉搜索树(Binary Search Tree, 简称BST)的定义:

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

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

其中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;
};

二、二叉搜索树操作

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)

上面采用了递归的方法来进行查找,递归最明显的特点就是简单,代码量小。但是在树高度很高时候,递归就会产生巨大的内存消耗和更多的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

非递归对应的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;
}

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

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

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

图2.2.1

找最小的元素只要一直在左子节点中查找,直到节点的左节点是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;
}

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

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

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

图2.2.1

求前驱节点的过程:

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

求后继节点的过程:

  • 如果节点有右子节点,那么后继节点一定是右子树中最小的元素。例如15的后继节点是1718的后继节点是20
  • 如果节点没有右子节点,那么它的后继就是以它或者以它任一祖先为左儿子的节点,例如上图中的13的后继节点是1517的后继节点是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;
}

2.4 插入节点(INSERT)

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

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

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;
}

2.5 删除节点(DELETE)

2.5.1 删除节点的基本操作

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

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

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

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

    • x为空
    • x不为空

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

2.5.2 删除节点只有一个儿子

只有左子节点的情况

只有右子节点的情况

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

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

对应情况:

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

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

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

情况对应下图:

此时要做的两步操作:

  1. y的右儿子(不管是否为NULL)替换成y
  2. 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;

然后在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;
    }
}
最后修改:2019 年 04 月 29 日
喜欢就给我点赞吧