二叉搜索树：BST模板类、查找、插入、删除操作 (C++)

男娘i 2022-05-17 12:12 222阅读 0赞

## 二叉搜索树 ##

1.顺序性

**任一节点r的左(右)子树，所有节点均不大于（小于）r**

![70][]

2.中序遍历序列

![70 1][]

对二叉搜索树做一次中序遍历，即可将该树转换为一个线性序列，且该序列中的节点严格按照其大小次序排列。

**任何一棵二叉树是二叉搜索树,当且仅当其中序遍历序列单调非降**

3.BST模板类

二叉搜索树属于二叉树的特例，故自然可以基于BinTree模板类

#include "../BinTree/BinTree.h" //引入BinTree
    
    template <typename T> class BST : public BinTree<T> { //由BinTree派生BST模板类
    protected:
        BinNodePosi(T) _hot; //BST::search()最后访问的非空(除非树空)的节点位置
        BinNodePosi(T) connect34( //按照“3 + 4”结构,联接3个节点及四棵子树
            BinNodePosi(T), BinNodePosi(T), BinNodePosi(T),
            BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T));
        BinNodePosi(T) rotateAt(BinNodePosi(T) x); //对x及其父亲、祖父做统一旋转调整
    public: //基本接口:以virtual修饰,强制要求所有派生类(BST变种)根据各自的规则对其重写
        virtual BinNodePosi(T) & search(const T& e);    //查找
        virtual BinNodePosi(T) insert(const T& e);    //插入
        virtual bool remove(const T& e);            //删除
    };

按照二叉搜索树的接口规范定义,这里新增了三个标准的对外接口search()、insert()和remove(),分别对应于基本的查找、插入和删除操作。

4.查找算法及其实现

二叉搜索树的查找算法,亦采用了减而治之的思路与策略,其执行过程可描述为:

**从树根出发,逐步地缩小查找范围,直到发现目标(成功)或缩小至空树(失败)**

![70 2][]

searchIn()算法与search()接口:

template <typename T> //在以v为根的(AVL、SPLAY、rbTree等)BST子树中查找关键码e
    static BinNodePosi(T) & searchIn (BinNodePosi(T)& v, const T& e, BinNodePosi(T)& hot) {
        if (!v || (e == v->data)) return v; //递归基:在节点v(或假想的通配节点)处命中
        hot = v; //一般情况:先记下当前节点,然后再
        return searchIn(((e < v->data) ? v->lChild : v->rChild), e, hot); //深入一层,递归查找
    } //返回时,返回值指向命中节点(或假想的通配哨兵),hot指向其父亲(退化时为初始值NULL)

template <typename T> BinNodePosi(T) & BST<T>::search(const T& e)
    //在BST中查找关键码e
    { return searchIn(_root, e, _hot = NULL); } //返回目标节点位置的引用,以便后续插入、删除操作

若查找成功,则searchIn()以及search()的返回值都将如图7.6(a)所示,指向一个关键码为e且真实存在的节点;若查找失败,则返回值的数值虽然为NULL,但是它作为引用将如图(b)所示,指向最后一次试图转向的空节点。对于后一情况,不妨假想地将此空节点转换为一个数值为e的哨兵节点——如此,无论成功与否,查找的返回值总是等效地指向“命中节点”。

![70 3][]

5.插入算法及其实现

![70 4][]

insert()接口的实现

template <typename T> BinNodePosi(T) BST<T>::insert(const T& e) { //将关键码e插入BST树中
        BinNodePosi(T) & x = search(e); if (x) return x; //确认目标节点不存在(留意对_hot的设置)
        x = new BinNode<T>(e, _hot); //创建新节点x:以e为关键码,以_hot为父
        _size++; //更新全树规模
        updateHeightAbove(x); //更新x及其历代祖先的高度
        return x; //新插入的节点,必为叶子
    } //无论e是否存在于原树中,返回时总有x->data == e

6.删除算法及其实现

![70 5][]

remove()接口和removeAt()算法：

template <typename T> bool BST<T>::remove(const T& e) { //从BST树中删除关键码e
        BinNodePosi(T) & x = search(e); if (!x) return false; //确认目标节点存在(留意对_hot的设置)
        removeAt(x, _hot); _size--; //实施删除
        updateHeightAbove(_hot); //更新_hot及其历代祖先的高度
        return true;
    } //删除成功与否,由返回值指示

首先调用search()查找e。若返回位置x为空,则说明树中不含目标节点,故删除操作随即可以失败返回。否则,调用removeAt()删除目标节点x。

/*********************************************************************************
        * BST节点删除算法:删除位置x所指的节点(全局静态模板函数,适用亍AVL、Splay、RedBlack等各种BST)
        * x由此前的查找确定,并经确认非NULL后方调用本函数,故必删除成功
        * 与searchIn不同,调用之前不必将hot置空
        * 返回值指向实际被删除节点的接替者,hot指向实际被删除节点的父亲——二者均有可能是NULL
    *********************************************************************************/
    template <typename T> static BinNodePosi(T) removeAt(BinNodePosi(T)& x, BinNodePosi(T)& hot) {
        BinNodePosi(T) w = x; //实际被摘除的节点,初值同x
        BinNodePosi(T) succ = NULL; //实际被初除节点的接替者
        if (!HasLChild(*x)) //若*x的左子树为空,则可
            succ = x = x->rChild; //直接将*x替换为其右子树
        else if (!HasRChild(*x)) //若右子树为空,则可
            succ = x = x->lChild; //对称地处理——注意:此时succ != NULL
        else { //若左右子树均存在,则选择x的直接后继作为实际被摘除节点,为此需要
            w = w->succ(); //(在右子树中)找到*x的直接后继*w
            swap(x->data, w->data); //交换*x和*w的数据元素
            BinNodePosi(T) u = w->parent;
            ((u == x) ? u->rChild : u->lChild) = succ = w->rChild; //隔离节点*w
        }
        hot = w->parent; //记录实际被删除节点的父亲
        if (succ) succ->parent = hot; //并将被删除节点的接替者与hot相联
        release(w->data); release(w); return succ; //释放被摘除节点,返回接替者
    }

完。

[70]: /images/20220517/2e0783f290054748aa81e44f41322ac7.png
[70 1]: /images/20220517/4ce27b3187a44fe297f6540bb6f80e17.png
[70 2]: /images/20220517/0ffeed69851b42a6a14ed48359fbab3c.png
[70 3]: /images/20220517/e5d20d3292834e3ba4dfd56b46ac69d2.png
[70 4]: /images/20220517/7c6cafd7c79143e99803c2a77aed6f4d.png
[70 5]: /images/20220517/3c253e1148094b088adb627f0c2f6e04.png