二叉搜索树BST

原因

最近想了解下C++ STL中的map和set的原理，它们是由红黑树实现的，但是想要了解红黑树要先了解下最基本的二叉搜索树

概念

二叉搜索树(Binary Search Tree)是有如下特征：

• 每个元素有唯一的键，这些键能比较大小
• 任何一个结点，它的左子树上任意结点的键都比它小，它的右子树上任意结点的键都比它大（由此可以推出，键值最大的结点无右儿子，键值最小的结点无左儿子）

另外，如果对这棵二叉树进行中序遍历，键的排列会是严格递增的

代码定义

BST的C++类定义如下：

class BST{
private:
    class node{
    public:
        int key;
        int value;
        
        node* lc;   //左儿子
        node* rc;   //右儿子
    };
    
private:
    node* root;
    
//对外接口
public:
    BST();
    void Insert(int key, int value);
    bool Find(int key, int &value);
    bool Delete(int key);
    void MidOrder();
  
//内部接口及功能实现
private:
    void _Insert(node* &n, int key, int value);
    bool _Find(node* n, int key, int &value);
    node* _Delete(node* &n, int key, bool &flag);
    void _MidOrder(node* n);
};

它的结点包含一对键值对，此处为了方便全用整型变量表示（当然可以写成泛型的形式，但是应当注意键的类型需能比较大小或重载了该运算符）

另外，由于BST也是一种二叉树，所以结点也满足二叉树的结点定义，即包含左儿子指针和右儿子指针

操作

BST的操作有插入、查询、删除、遍历（建树的过程在插入中实现），这些方法基本都是递归实现的。

在上文的类定义中，由于node类为私有，并且方法的实现为递归，为了安全与简洁，对外部的方法作为接口会调用对应的私有方法，因此下文的每种操作都会列举出一个接口和方法实现，使用只需要调用规范好的接口就行了。

构造函数

BST::BST(){
    //初始化
    this->root = nullptr;
}

插入

以第1个数据为根结点，逐个插入所有数据。插入时分三种情况：

• 当传入指针即当前结点为空，则new直接插入（new一个结点，并赋值）
• 若插入数据键比当前结点的键小，则向左子树递归继续寻找插入位置
• 若插入数据键比当前结点的键大，则向右子树递归继续寻找插入位置

其代码如下：

//插入方法实现
void BST::_Insert(node* &n, int key, int value){
    //为空直接插入
    if(!n)
    {
        n = new node;
        n->key = key;
        n->value = value;
        n->lc = nullptr;
        n->rc = nullptr;
        return;
    }
    
    //不为空需要找查
    if(n->key == key)       //如果等于当前键，则直接修改该结点的值
        n->value = value;
    else if(n->key > key)   //当前结点的键大于所要插入的键，则往左子树找插入点
        this->_Insert(n->lc, key, value);
    else                    //当前结点的键大于所要插入结点的键，则往右子树找插入点
        this->_Insert(n->rc, key, value);
}

//插入方法接口
//参数：键，值
void BST::Insert(int key, int value)
{
    this->_Insert(this->root, key, value);
}

查询

该操作原理与插入类似，都是需要比较键的大小往判断往左子树找还是右子树找

//查找方法实现
//成功返回true，并将value改为键对应的值；否则返回false，value不做处理
bool BST::_Find(node* n, int key, int &value)
{
    //检查是否为空
    if(!n)
        return false;
    
    if(n->key == key)       //找到
    {
        value = n->value;
        return true;
    }
    else if(n->key > key)   //未找到，且当前键大于查询键，继续往左找
        return this->_Find(n->lc, key, value);
    else                    //未找到，且当前键小于查询键，继续往右找
        return this->_Find(n->rc, key, value);
}


//查找方法的接口
bool BST::Find(int key, int &value)
{
    return this->_Find(this->root, key, value);
}

删除结点

删除结点的操作比较麻烦。

首先根据键找到被删除结点，进行删除后改树应仍满足BST的定义，这就需要进行分类讨论：

• 当要被删除的结点为叶子结点，直接将其对应的父结点的指针置为空，并删除该结点
• 当要被删除的结点仅有左子树或右子树时，其对应父结点的指针应指向子树的根结点，再进行删除。
• 当要被删除的结点既有左子树，又有右子树，这种情况比较麻烦。一种删除方法是将右子树的最小键结点的键与值替换当前结点，然后删除右子树的最小键结点

代码如下（比较抽象）：

//删除方法的实现
BST::node* BST::_Delete(node* &n, int key, bool &flag)
{
    if(!n)
        return n;
    
    if(n->key>key)  //往左找
        n->lc = this->_Delete(n->lc, key, flag);
    if(n->key<key)  //往右找
        n->rc = this->_Delete(n->rc, key, flag);
    else{
        //找到
        flag = true;    //设置flag，表示删除成功
        //如果仅有左子树或右子树或为叶子结点
        if(!(n->rc))    //无右子树或为叶子结点
            return n->lc;
        if(!(n->lc))    //无左子树
            return n->rc;
        
        //寻找右子树最小键结点的键与值拷贝至当前结点
        node* p = n->rc;
        while(p->lc)
            p = p->lc;
        n->value = p->value;
        n->key = p->key;
        bool temp = false;
        n->rc = this->_Delete(n->rc, p->key, temp); //将右子树最小键结点的父结点左指针置为空
        delete p;   //删除原右子树最小键结点
    }
    
    return n;
}

//删除方法的接口
bool BST::Delete(int key)
{
    bool flag = false;
    this->_Delete(this->root, key, flag);
    return flag;
}

遍历

遍历方法无非就是二叉树的那几种，但是正如前面提到的，对BST进行中序遍历的时候，其键的排序是严格递增的，这也正是采用该数据结构的一种重要原因，所以此处仅给出了中序遍历的递归定义

注：其他遍历可参考之前文章 二叉树及其遍历-CairBin

//中序遍历方法实现
void BST::_MidOrder(node* n)
{
    if(!n)
        return;
    this->_MidOrder(n->lc);
    cout << n->key << ":" << n->value << " ";
    this->_MidOrder(n->rc);
}

//中序遍历接口
void BST::MidOrder()
{
    this->_MidOrder(this->root);
    cout << endl;
}

缺点与改进

BST的插入是按给定序列的顺序进行的，最后建成的树是唯一的。

也就是说它可能很好，也可能很坏。

• 最坏的情况：如序列{1,2,3,4,5,6,7}，为方便排序令其键与值相等，然后就会发现该BST会退化成一个每个结点都有右子树，无左子树（叶子结点都没有）的链表，导致访问一个结点的复杂度为$O(n)$
• 最好的情况：如序列{4,2,1,3,6,5,7}，同样令键与值相等，其为一个三层的满二叉树，访问结点的复杂度为$O(log_{2}{n})$

从上述情况看，BST优劣取决于是否为一个平衡的二叉树，所以有一系列相关的算法进行改进。BST算法有：红黑树、AVL、Splay等

参考

• 《算法竞赛入门到进阶》——清华大学出版社