（数据结构）如何手搓一棵二叉搜索树（BST）

发布于：2022-12-10 ⋅ 阅读:(744) ⋅ 点赞:(0)

目录

函数总览

search

insert

removeAt

旋转

代码：

BST是基础的搜索树，二叉树的派生类

也是后面一些搜索树的子类

BST的每个节点都是key和value两个值

而且具有局部有效性

即对于每一个节点，其左子树的value都不大于此节点，其右子树的value都不小于此节点

使得可以进行二分查找，加快效率

我们先造一个键值对备用

template <typename K,typename V>
class entry{
public:
    K key;
    V value;

    //constructor
    entry()=default;
    entry(K k,V v):key(k),value(v) {}

    //operator
    bool operator==(entry<K,V> const e) {return key==e.key;}
    bool operator!=(entry<K,V> const e) {return key!=e.key;}
    bool operator>(entry<K,V> const e) {return key>e.key;}
    bool operator<(entry<K,V> const e) {return key<e.key;}
};

#define T entry<K,V>

函数总览

template <typename K,typename V>
class lxrBST :public lxrbintree<T>{
protected:
    lxrbinnodeposi(T) __hot;
    lxrbinnodeposi(T)& searchIn(lxrbinnodeposi(T) &x,K const &key,lxrbinnodeposi(T) &hot);
    lxrbinnodeposi(T) connect34(lxrbinnodeposi(T) x,lxrbinnodeposi(T) y,lxrbinnodeposi(T) z,
                                lxrbinnodeposi(T) T0,lxrbinnodeposi(T) T1,lxrbinnodeposi(T) T2,lxrbinnodeposi(T) T3);//return new root
    lxrbinnodeposi(T) rotateAt(lxrbinnodeposi(T) x);
    lxrbinnodeposi(T) removeAt(lxrbinnodeposi(T) &x,lxrbinnodeposi(T) &hot);
public:
    //call by key,always assume that key exists,read-only
    V operator[](K const &key);

    virtual lxrbinnodeposi(T)& search(K const &key);
    virtual lxrbinnodeposi(T) insert(K const &key,V const &value);
    virtual bool              remove(K const &key);
};

这里除了基础的查找，插入，删除函数

还有一些旋转函数，以便于后续其他树调用

查找和删除用virtual修饰，以便其他树重写该方法

search

二叉树的查找算法

之前说过二叉树是局部有序的

那我们在查找一个节点时，即可用二分提升效率

如果要查找的value小于该节点，那么查找左子树，否则查找右子树

这里的技巧主要在于利用`__hot`内部变量来保存被查找结点的父结点，即使被查找结点为空指针，__hot仍然会指向它的父结点，从而后续的插入和删除操作就可以方便地进行。

过程类似下图

代码如下

template <typename K,typename V>
lxrbinnodeposi(T)& lxrBST<K,V>::searchIn(lxrbinnodeposi(T)& x,K const &key,lxrbinnodeposi(T) &hot){
    if(!x || x->data.key==key) return x;
    hot=x;
    return key<x->data.key ? searchIn(x->leftchild,key,hot) : searchIn(x->rightchild,key,hot);
}
template <typename K, typename V>
lxrbinnodeposi(T)& lxrBST<K, V>::search(K const &key){
	return searchIn(this->__root, key, __hot = nullptr);
}

insert

插入算法：

BST的插入算法主要要考虑的问题是不能破坏BST的局部有序性，为此可以先通过调用一次查找算法来找到被插入结点应该存在的位置，随后利用被返回的结点以及__hot变量，可以方便地实现插入操作

之后更新此节点以上的高度

代码如下：

template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::insert(K const &key,V const &value){
    lxrbinnodeposi(T) &x=search(key);
    if(x) return x;
    x=new lxrbinnode<T>(entry<K,V>(key,value),__hot);
    ++(this->__size);
    this->updateHeightAbove(__hot);
    return x;
}

removeAt

删除节点

和BST的查找一样，BST的删除算法也需要保证不改变BST的局部有序性，为此需要对删除了当前结点的树做一些调整，使之重新成为一棵BST。具体的调整方法如下：

如果被删除结点没有左子树或者没有右子树，那么就可以直接用它的右子树或者左子树来替代它，就可以在删除结点的同时保持了BST的性质。

如果被删除结点既有左子树，又有右子树，可以找到它的直接后继succ()，用直接后继的数据来替代当前结点的数据，随后删除直接后继结点，而这里的直接后继是一定没有左子树的。

之后别忘了更新高度

代码如下：

​
template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::removeAt(lxrbinnodeposi(T) &x,lxrbinnodeposi(T) &hot){
    lxrbinnodeposi(T) succ;
    if     (!x->leftchild)  succ=x=x->rightchild;
    else if(!x->rightchild) succ=x=x->leftchild;
    else{
        succ=x->succ();
        x->data=succ->data;
        if(succ->parent==x) succ->parent->rightchild=succ->rightchild;
        else                succ->parent->leftchild=succ->rightchild;
        hot=succ->parent;
        succ=succ->rightchild;
    }
    if(succ) succ->parent=hot;
    return succ;
}
template <typename K,typename V>
bool lxrBST<K,V>::remove(K const &key){
    lxrbinnodeposi(T) &x=search(key);
    if(!x) return false;

    removeAt(x,__hot);
    --(this->__size);
    this->updateHeightAbove(__hot);
    return true;
}

​

旋转

在最原始的BST中是不涉及旋转算法的

写在这里是因为以后很多高级搜索树都需要此方法

为了便捷性才写在这里

具体实现和思路会写在下一篇-AVL树的失衡调整中

代码：

#ifndef LXRBST_H_
#define LXRBST_H_

#include "../04 bintree/lxrbintree.h"
#include <stdexcept>
using std::runtime_error;

template <typename K,typename V>
class entry{
public:
    K key;
    V value;

    //constructor
    entry()=default;
    entry(K k,V v):key(k),value(v) {}

    //operator
    bool operator==(entry<K,V> const e) {return key==e.key;}
    bool operator!=(entry<K,V> const e) {return key!=e.key;}
    bool operator>(entry<K,V> const e) {return key>e.key;}
    bool operator<(entry<K,V> const e) {return key<e.key;}
};

#define T entry<K,V>

template <typename K,typename V>
class lxrBST :public lxrbintree<T>{
protected:
    lxrbinnodeposi(T) __hot;
    lxrbinnodeposi(T)& searchIn(lxrbinnodeposi(T) &x,K const &key,lxrbinnodeposi(T) &hot);
    lxrbinnodeposi(T) connect34(lxrbinnodeposi(T) x,lxrbinnodeposi(T) y,lxrbinnodeposi(T) z,
                                lxrbinnodeposi(T) T0,lxrbinnodeposi(T) T1,lxrbinnodeposi(T) T2,lxrbinnodeposi(T) T3);//return new root
    lxrbinnodeposi(T) rotateAt(lxrbinnodeposi(T) x);
    lxrbinnodeposi(T) removeAt(lxrbinnodeposi(T) &x,lxrbinnodeposi(T) &hot);
public:
    //call by key,always assume that key exists,read-only
    V operator[](K const &key);

    virtual lxrbinnodeposi(T)& search(K const &key);
    virtual lxrbinnodeposi(T) insert(K const &key,V const &value);
    virtual bool              remove(K const &key);
};

//protected method
template <typename K,typename V>
lxrbinnodeposi(T)& lxrBST<K,V>::searchIn(lxrbinnodeposi(T)& x,K const &key,lxrbinnodeposi(T) &hot){
    if(!x || x->data.key==key) return x;
    hot=x;
    return key<x->data.key ? searchIn(x->leftchild,key,hot) : searchIn(x->rightchild,key,hot);
}

template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::connect34(lxrbinnodeposi(T) x,lxrbinnodeposi(T) y,lxrbinnodeposi(T) z,
                                        lxrbinnodeposi(T) T0,lxrbinnodeposi(T) T1,lxrbinnodeposi(T) T2,lxrbinnodeposi(T) T3){
    x->leftchild=T0;
    x->rightchild=T1;
    if(T0) T0->parent=x;
    if(T1) T1->parent=x;
    this->updateHeight(x);

    x->leftchild=T2;
    x->rightchild=T3;
    if(T2) T2->parent=z;
    if(T3) T3->parent=z;
    this->updateHeight(z);

    x->parent=y;
    z->parent=y;
    y->leftchild=x;
    y->rightchild=z;
    this->updateHeight(y);

    return y;
    
}

template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::rotateAt(lxrbinnodeposi(T) x){
    lxrbinnodeposi(T) p=x->parent;
    lxrbinnodeposi(T) g=p->parent;
    if(p==g->leftchild){
        if(x==p->leftchild){
            p->parent=g->parent;
            return connect34(x,p,g,x->leftchild,x->rightchild,p->rightchild,g->rightchild);
        }
        else{
            x->parent=g->parent;
            return connect34(p,x,g,p->leftchild,x->leftchild,x->rightchild,g->rightchild);
        }
    }
    else{
        if(x==p->leftchild){
            x->parent=g->parent;
            return connect34(g,x,p,g->leftchild,x->leftchild,x->rightchild,p->rightchild);
        }
        else{
            p->parent=g->parent;
            return connect34(g,p,x,g->leftchild,p->leftchild,x->leftchild,x->rightchild);
        }
    }
}

template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::removeAt(lxrbinnodeposi(T) &x,lxrbinnodeposi(T) &hot){
    lxrbinnodeposi(T) succ;
    if     (!x->leftchild)  succ=x=x->rightchild;
    else if(!x->rightchild) succ=x=x->leftchild;
    else{
        succ=x->succ();
        x->data=succ->data;
        if(succ->parent==x) succ->parent->rightchild=succ->rightchild;
        else                succ->parent->leftchild=succ->rightchild;
        hot=succ->parent;
        succ=succ->rightchild;
    }
    if(succ) succ->parent=hot;
    return succ;
}

//public interfaces
template <typename K,typename V>
V lxrBST<K,V>::operator[](K const &key){

    lxrbinnodeposi(T) x=search(key);
    if(!x) throw runtime_error("Fatal Error: key doesn't exist.");
    return x->data.value;
}

template <typename K, typename V>
lxrbinnodeposi(T)& lxrBST<K, V>::search(K const &key){
	return searchIn(this->__root, key, __hot = nullptr);
}

template <typename K,typename V>
lxrbinnodeposi(T) lxrBST<K,V>::insert(K const &key,V const &value){
    lxrbinnodeposi(T) &x=search(key);
    if(x) return x;
    x=new lxrbinnode<T>(entry<K,V>(key,value),__hot);
    ++(this->__size);
    this->updateHeightAbove(__hot);
    return x;
}

template <typename K,typename V>
bool lxrBST<K,V>::remove(K const &key){
    lxrbinnodeposi(T) &x=search(key);
    if(!x) return false;

    removeAt(x,__hot);
    --(this->__size);
    this->updateHeightAbove(__hot);
    return true;
}
#undef T

#endif

而BST的缺点就是没有平衡拓扑结构

使得极端情况下，如果所有节点都按照之字形排列

那么整棵树就会退化成一条链表

操作的最坏复杂度达到了n平方

这明显是不被允许的

也就有了后来的很多高级搜索树

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布