搜索树1-二叉搜索树

继续是《数据结构算法与应用：C++语言描述》的笔记，这是第11章搜索树的内容。

本节首先介绍的是二叉搜索树的内容。

基本概念

在跳表&散列1-字典&跳表介绍了抽象数据类型Dictionary，从中可以发现当用散列来描述一个字典时，字典操作（包括插入、删除和搜索）所需要的平均时间是$\theta(1)$。而这些操作最坏情况下的时间正比于字典中的元素个数$n$。如果扩充字典的抽象数据类型描述，增加以下操作，那么散列将不能再提供比较好的评价性能：
1) 按关键值的升序输出字典元素；
2）按升序找到第k个元素；
3）删除第k个元素。

为了执行操作1），需要从表中取出数据，将它们排序后输出。如果使用除数是D的链表，那么能在$\theta(D+n)$的时间内取出元素，在$O(nlogn)$时间内完成排序和$\theta(n)$时间内输出，因此共需时间$O(D+nlogn)$。如果对散列使用线性开型寻址，则取出元素所需时间是$\theta(b)$,b是桶的个数，这时需要时间是$O(b+nlogn)$。
如果使用链表，操作2）和3）可以在$O(D+n)$的时间内完成，如果使用线性开型寻址，它们可以在$\theta(b)$时间内完成。

如果使用平衡搜索树，那么对字典的基本操作（搜索、插入和删除）能够在$O(logn)$的时间内完成，操作1）能在$\theta(n)$的时间内完成。通过使用带索引的平衡搜索树，也能够在$O(logn)$的时间内完成操作2）和3）。

在学习平衡树之前，首先来看一种叫做二叉搜索树的简单结构。

定义 [二叉搜索树] 二叉搜索树(binary search tree)是一棵可能为空的二叉树，一棵非空的二叉搜索树满足以下特征：
1）每个元素有一个关键值，并且没有任意两个元素有相同的关键值；因此，所有的关键值都是唯一的。
2）根节点左子树的关键值（如果有的话）小于根节点的关键值。
3）根节点右子树的关键值（如果有的话）大于根节点的关键值。
4）根节点的左右子树也都是儿茶搜索树。

下图11-1给出3个含有不同关键值的二叉树，其中11-1a的二叉树满足了上述特征1-3，但是不满足特征4，而11-b和11-c的二叉树则是二叉搜索树。

在放弃二叉搜索树中所有元素必须拥有不同关键值的要求，然后用小于等于代替特征2）中的小于，用大于等于代替特征3）中的大于，这样就可以得到一棵有重复值的二叉搜索树。

带索引的二叉搜索树源于普通的二叉搜索树，它只是在每个节点中添加一个LeftSize域，这个域的值是该节点左子树的元素个数加1。下图11-2是两棵带索引的二叉搜索树。注意，LeftSize同时给出了一个元素在子树中的排名。

类BSTree

可以从二叉树的基本概念和实现中介绍的类BinaryTree中派生类BSTree,这样可以大大简化类BSTree的设计，实现如下程序所示。另外，为了访问BinaryTree类的私有成员root，需要将类BSTree定义为BinaryTree的友元。

template<class E,class K>
class BSTree : public BinaryTree<E>{
public:
    bool Search(const K&k, E& e) const;
    BSTree<E, K>& Insert(const E& e);
    BSTree<E, K>& Delete(const K&k, E& e);
    void Ascend(){ InOutput(); }
};

下面给出搜索元素的代码实现：

template<class E,class K>
bool BSTree<E, K>::Search(const K&k, E &e) const{
    // 搜索与k匹配的元素
    BinaryTreeNode<E> *p = root;
    while (p){
        if (k < p->data)
            p = p->LeftChild;
        else if (k>p->data)
            p = p->RightChild;
        else{
            // 找到元素
            e = p->data;
            return true;
        }
    }
    return false;
}

若在二叉搜索树中插入一个新元素e，首先要验证e的关键值与树中已有元素的关键值是否相同，这可以通过用e的关键值对二叉树进行搜索来实现。如果搜索不成功，那么新元素将被插入到搜索的中端点，下面给出插入函数的代码实现：

template<class E, class K>
BSTree<E, K>& BSTree<E, K>::Insert(const E& e){
    // 如果不出现重复，则插入e
    BinaryTreeNode<E> *p = root, *pp = 0;   // p是搜索节点，pp是p的父节点
    // 寻找插入点
    while (p){
        pp = p;
        if (e < p->data)
            p = p->LeftChild;
        else if (e>p->data)
            p = p->RightChild;
        else
            // 出现重复
            throw BadInput();
    }

    BinaryTreeNode<E> *r = new BinaryTreeNode<E>(e);
    if (root){
        if (e < pp->data)
            pp->LeftChild = r;
        else
            pp->RightChild = r;
    }
    else
        root = r;

    return *this;
}

对于删除操作，对包含被删除元素的节点p有三种情况：1）p是叶节点；2）p只有一个非空子树；3）p有两个非空子树。

对于第一种情况可以采用直接丢弃叶节点的方法来处理。

对于第二种情形，如果p没有父节点，即p是根节点，则将p丢弃，p的唯一孩子成为新的搜索树的根节点；如果p有父节点pp，则修改pp的指针，使其指向p的唯一孩子，然后删除节点p。

最后，对于第三种情形，只需要将元素替换成它的左子树中的最大元素或者右子树中的最小元素。注意，必须确保右子树中的最小元素以及左子树中的最大元素即不会在没有子树的节点中，也不会在只有一个子树的节点中。可以按下述方法来查找到左子树中的最大元素：首先移动到子树的根，然后沿着各节点的右孩子指针移动，直到右孩子指针为0为止。类似地，也可以找到右子树的最小元素：首先移动到子树的根，然后沿着各节点的左孩子指针移动，直到左孩子指针为0为止。

下面程序给出删除操作实现，它一般使用左子树的最大元素来进行替换。

template<class E,class K>
BSTree<E, K>& BSTree<E, K>::Delete(const K& k, E& e){
    // 删除关键值是k的元素，并将其放入e

    // 将p指向关键值是k的节点
    BinaryTreeNode<E> *p = root, *pp = 0;

    while (p && p->data != k){
        pp = p;
        if (k < p->data)
            p = p->LeftChild;
        else
            p = p->RightChild;
    }
    if (!p)
        throw BadInput();

    e = p->data;
    // 对树进行重构，处理p有两个孩子的情形
    if (p->LeftChild && p->RightChild){
        // 转换成有0或1个孩子的情形，在p的左子树中寻找最大元素
        BinaryTreeNode<E> *s = p->LeftChild, *ps = p;
        while (s->RightChild){
            ps = s;
            s = s->RightChild;
        }

        // 将最大元素从s移动到p
        p->data = s->data;
        p = s;
        pp = ps;
    }

    // 对于p最多有一个孩子
    BinaryTreeNode<E> *c;
    if (p->LeftChild)
        c = p->LeftChild;
    else
        c = p->RightChild;

    // 删除p
    if (p == root)
        root = c;
    else{
        if (p == pp->LeftChild)
            pp->LeftChild = c;
        else
            pp->RightChild = c;
    }
    delete p;

    return *this;
}

类DBSTree

若二叉搜索树中的不同元素可以包含相同的关键值，则称这种树是DBSTree。在实现该类的时候，只需要把BSTree::Insert的while循环改成如下所示即可：

while (p){
    pp = p;
    if (e < p->data)
        p = p->LeftChild;
    else if (e>p->data)
        p = p->RightChild;
}

更完整的例子可以查看二叉搜索树的实现

小结

本节内容就简单介绍了二叉搜索树的代码实现。