数据结构和算法

算法导论 - 二叉搜索树（BST）

2018-12-12  本文已影响0人  Longshihua

二叉搜索树

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

1.png

二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：

设x是二叉搜索树中的一个结点，如果y是x的左子树中的一个结点，那么y.key \leq x.key。如果y是x的右子树中的一个结点，那么y.key \geq x.key

如图（a）中，树根的关键字是6，在其左子树中有关键字2、5和5，它们均不大于6；而其右子树中有关键字7和8，它们均不小于6。所以这个性质在树中的每个结点都成立。

二叉搜索树的性质允许我们通过一个简单的递归算法来按序输出二叉搜索树中的所有关键字，算法是我们熟悉的中序遍历

typedef struct Node
{
    struct Node *p;
    struct Node *left;
    struct Node *right;
    int key;
} Node;

void InorderTreeWalk(Node *x) // 中序遍历树x
{
    if (x != nullptr) {
        InorderTreeWalk(x->left); // 递归左孩子
        cout<<x->key<<endl; // 输出根节点关键字
        InorderTreeWalk(x->right); // 递归右孩子
    }
}

遍历一棵有n个结点的二叉搜索树，需要耗费O(n)的时间，因为初次调用后，对于树中的每个结点这个过程恰好要自己调用两次；一次是它的左孩子，另一次是它的右孩子

查询二叉搜索树

2.jpeg

我们经常需要查找一个存储在二叉搜索树中的关键字，下面将讨论并且说明在任何高度为h的二叉搜索树上，如何在O(h)时间内完成每个操作

查找

使用下面的代码在一棵二叉搜索树中查找一个具有给定关键字的结点，输入一个指向树根的指针和一个关键字k，如果这个节点存在，那么返回关键字为k的指针，否则为nil

Node * TreeSearch(Node *x, int k)
{
    if (x == nullptr || k == x->key) {
        return x;
    }

    if (k < x->key)
    {
        return TreeSearch(x->left, k);
    }
    else
    {
        return TreeSearch(x->right, k);
    }
}

除了递归方式，采用迭代方式是效率更高的方式

Node * InteractiveTreeSearch(Node *x, int k)
{
    while (x != nullptr && k != x->key) {
        if (k < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    return x;
}

最大关键字元素和最小关键字元素

通过从树根开始沿着left孩子指针直到遇到一个nil，

Node *TreeMinimum(Node *x)
{
    while (x->left != nullptr) {
        x = x->left;
    }
    return x;
}

二叉树的性质保证了上面查找的正确性。

如果结点x没有左子树，那么由于x的右子树中的每个关键字都至少大于或等于x.key，则以x为根的子树中的最小关键字是x.key。如果结点x有左子树，那么由于其右子树中没有关键字小于x.key，且在左子树中的每个关键字不大于x.key，则以x为根的子树中的最小关键字一定在以x.left为根的子树中

最大元素一定是沿着right孩子指针不断向下查找，直到遇到第一个空指针；

Node *TreeMaxmum(Node *x)
{
    while (x->right != nullptr) {
        x = x->right;
    }
    return x;
}

这两个过程在一棵高度为h的树上均能在O(h)的时间内执行完。

后继和前驱

给定一棵二叉搜索树，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个结点x的后继是大于x.key的最小关键字的结点

后继

Node *TreeSuccessor(Node *T, int t)
{
    // 查找结点
    Node *x = TreeSearch(T, t);
    Node *y = nullptr;

    // 右子树非空，即查找最小关键字
    if (x->right != nullptr) {
        y = TreeMinimum(x->right);
        return y;
    }

    // 查找结点的父指针
    y = x->p;
    while (y != nullptr && x == y->right) {
        x = y;
        y = y->p;
    }
    return y;
}

如果结点x的右子树非空，那么x的后继恰好是x右子树中的最左结点。也可以理解为最小关键字

2.jpeg

如果结点x的右子树为空并有一个后继y，那么y就是x的最底层祖先，并且y的左孩子也是x的一个祖先（比如：上图中关键字为13的结点的后继是关键字为15的结点）。为了找到y，只需要简单地从x开始沿树而上直到遇到这样一个结点：这个结点是它的双亲的左孩子

前驱

Node *TreePredecessor(Node *T, int t)
{
    // 查找元素t
    Node *x = TreeSearch(T, t);
    Node *y = nullptr;

    // 左子树非空
    if (x->left != nullptr)
    {
        return  TreeMaxmum(x->left);
    }

    // 查结点的父指针
    y = x->p;
    while ( y != nullptr && x == y->left) {
        x = y;
        y = y->p;
    }
    return y;
}

对于树的后继和前驱的查找，运行时间为O(h)

插入和删除

插入和删除操作会引起由二叉搜索树表示的动态集合的变化。所以一定要修改数据结构来反映这个变化，但修改要保持二叉搜索树性质的成立

插入

向一个二叉搜索树中插入一个x结点，只需要不断比较x.key与当前结点z.key的大小，若小于，则肯定是向z的左子树插入，否则向z的右子树插入，循环比较，直到遇到当前结点的左/右子树为空为止。这时候已经找到了要插入的结点的父结点的位置，最后判断是左子树还是右子树即可

Node * TreeInsert(Node *root, Node *z)
{
    Node *y = nullptr;
    Node *x = root;

    // 节点非空，看是左子树还是右子树插入
    while (x != nullptr) {
        y = x;
        if (z->key < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }

    z->p = y;
    if (y == nullptr) // 建立第一个节点
    {
        root = z;
    }
    else if (z->key < y->key) // 小于父结点即位左子树
    {
        y->left = z;
    }
    else // 大于即为右子树
    {
        y->right = z;
    }

    return root;
}
3.jpeg

比如：上图插入结点，关键字为13，可以对照代码和图形理解

删除

从一棵二叉搜索树T中删除一个结点z，存在3种情况：

1、如果z没有孩子结点，那么只是简单地将它删除，并修改父结点，用nil作为孩子来替换z
2、如果z只有一个孩子，那么将孩子提升到树中z的位置，并修改z的父结点，用z的孩子来替换z
3、如果z有两个孩子，那么找z的后继y（一定在z的右子树中），并让y占据树中z的位置。z的原来右子树部分成为y的新的右子树，并且z的左子树成为y的新的左子树

对照图来理解上面几种情况

屏幕快照 2018-12-12 上午9.16.42.png 屏幕快照 2018-12-12 上午9.16.50.png 屏幕快照 2018-12-12 上午9.17.03.png 屏幕快照 2018-12-12 上午9.17.19.png

在二叉搜索树内移动子树，它是用另一棵子树替换一棵子树并成为其双亲的孩子结点

移动子树

void Transplant(Node **T, Node *u, Node *v) // 用结点v替换结点u
{
    if (u->p ==  nullptr) // 父结点不存在,那么u为根结点
    {
        *T = v;
    }
    else if (u == u->p->left) // u为左孩子,那么将v作为左孩子
    {
        u->p->left = v;
    }
    else // u为右孩子,那么将v作为右孩子
    {
        u->p->right = v;
    }

    if (v != nullptr) // v不为nil，那么更新父结点
    {
        v->p = u->p;
    }
}

删除结点

Node * TreeDelete(Node *T, int k)
{
    Node *z = TreeSearch(T, k); // 查找结点z
    Node *y = nullptr;

    if (z->left == nullptr) // 结点z没有左孩子
    {
        Transplant(&T, z, z->right);
    }
    else if (z->right == nullptr) // 结点z没有右孩子
    {
        Transplant(&T, z, z->left);
    }
    else // 结点z有两个孩子
    {
        y = TreeMinimum(z->right); // 找右子树的最小结点

        if (y->p != z) { // y的父结点不是z
            Transplant(&T, y, y->right);
            y->right = z->right;
            y->right->p = y;
        }

        Transplant(&T, z, y);
        y->left = z->left;
        y->left->p = y;
    }
    return T;
}

简单使用

// 创建搜索二叉树
Node * TreeEstablish(int *a, int length)
{
    Node *root = nullptr;
    for (int i=0 ; i < length; i++) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->key = a[i];
        node->p = nullptr;
        node->left = nullptr;
        node->right = nullptr;
        root = TreeInsert(root, node);
    }
    return root;
}

int main(int argc, const char * argv[]) {
    int a[] = {2,3,4,6,15,7,18,17,20,13,9};
    int length = sizeof(a)/sizeof(a[0]);

    Node *T;
    T = TreeEstablish(a, length); // 建立二叉搜索树
    InorderTreeWalk(T);  // 中序遍历打印
    cout<<"6 successor is "<<TreeSuccessor(T, 6)->key<<endl; // 后继查找
    cout<<"18 predecessor is "<<TreePredecessor(T, 18)->key<<endl; // 前驱查找
    T = TreeDelete(T, 2); // 删除结点
    TreeInorderPrint(T); // 删除结点之后的二叉搜索树
    return 0;
}

参考

《算法导论》

上一篇 下一篇

猜你喜欢

热点阅读