3. 二叉搜索树 --- BST（Binary Search Tree）

BST ： 二叉搜索树 树表结构查找相关算法

主要思想 : 循关键码访问 key

• 条件 ： 关键码之间
  1. 大小比较
  2. 相等比对

顺序性(标准定义) ： L <= V <= R
为简化起见，规定BST中不允许(禁止)重复词条
故有定义 ： L < V < R
这种简化 ： 应用中不自然，算法上也无必要
＃＃＃
如果一定要存在重复的词条，则需要做一些规定，防止插入一个已存在的词条，是插在存在的节点的左子树还是右子树中？
在此规定： 插入重复的词条，统一插到search()到的第一个已存在的重复节点的右子树中（因为当前的 BST 中可能存在多个重复词条节点）

BST ： 中序遍历序列，必须单调非降；这是 BST的充要条件。

BST 作为动态查找(搜索)算法 ： 查找过程中涉及插入和删除基本，在插入和删除动作执行时，不能改变 BST 的充要条件特性，所以 BST 的插入和删除节点的操作与标准的二叉树插入和删除节点的操作有所不同，涉及插入或删除后的 BST 的调整操作。

BST 插入或删除节点后不满足 BST性质，需要调整，满足终须单调非降性质

BST常用接口

1. 接口声明 ：

BinNodePosi Search(const T &);      //查找
BinNodePosi Insert(const T &);      //插入节点操作
BinNodePosi Remove(const T &);      //删除节点操作

/* 删除节点操作后的调整动作  */
/* 1. <3+4重构> */
BinNodePosi connect34(BinNodePosi, BinNodePosi, BinNodePosi,
                      BinNodePosi, BinNodePosi, BinNodePosi, BinNodePosi);

/*2. <旋转操作> */
BinNodePosi rotateAt(BinNodePosi);

/* 非常有用的一个记录值 */
BinNodePosi _hot;  

// 作为记录 Search() 命中节点的父亲 或 未找到时最后一个访问的节点
// 记录这个 _hot 以便于插入和删除操作！！！

2. 算法及其实现

2.1 BST查找算法实现 Search()

/*
BinNodePosi &v         当前树（子树）根节点，以 v 节点为根节点
const T &e             目标关键码
BinNodePosi ＆hot      记忆热点，插入、删除操作时很有用！！！作为父指针记忆
*/
BinNodePosi BST_Search(BinNodePosi &v, const T &e, BinNodePosi & hot)
{
    if ( !v || ( e== v->data))                       // 出口
    {
        return v;
    }

    hot = v;                                        // 记录当前节点
    if( e < v->data)
    {
        return BST_Search( v->lchild, e, hot);      //左子树递归搜索    
    }
    else
    {
        return BST_Search( v->rchild, e, hot);     //右子树递归搜索
    }
}/* 典型的尾递归，可改成迭代版实现 */
// 运行时间正比于返回节点 v 的深度，不超过树高O(h);

BinNodePosi Search(const T &e)
{
    return BST_Search(_root, e, _hot=NULL);
}


/*******************************************************************/
/*******************************************************************/
/* BST_Search() 非递归实现 */
BinNodePosi BST_Search2(BinNodePosi &v, const T &e, BinNodePosi & hot)
{
    BinNodePosi p = v;

    while(NULL != p)
    {
        if (e == p->data)
        {
            return p;
        }
      
        hot = p;   // 记录当前节点，执行下面的插入和删除动作时，hot 非常有用
        
        if ( p->data < e)
        {
            p = p->rchild;
        }
        else
        {
            p = p->lchild;
        }
    }

    return p;      //未找到， p == NULL
}

2.2 BST 插入算法实现

• × 先借助 Search(value) 确定待插入值 value 的插入位置及方向，再将新节点作为叶子插入
• × 若 value 尚不存在，则 _hot 为新结点的 父亲
v = Search(value) 为 _hot 对新孩子的引用；[ Search(value)本为空，V节点作为其引用 ]
  
  Search(value)

实例 ： 执行 insert(40)

BST-Insert过程图解

BST 插入算法实现 Code

后补

2.3 BST 删除算法实现

实现步骤：

• 定位待删除节点 : search(e)
• 确定目标节点是否存在，存在执行下面步骤；不存在，返回错误；
• 分两类情况实施删除操作，并作出对应的调整操作
• 更新树的规模 (size 和 _hot节点及其历代祖先的高度)

/* remove()  代码实现  Code */

bool remove(const T &e)
{
    BinNodePosi  &x = Search(e);    //step 1
    if (!x)
        return false;              // step 2
    
    removeAt(x , _hot);            // step 3

    _size --;                      // step 4
    updateHeightAbove(_hot);    

    return true;
}

删除操作 removeAt() 分以下两种情况分析实现

假设待删节点为 x

1. 情况一 ：

若 x 的 某一子树为空 ，则可将待删节点 x 替换为其另一个子树； 【即 直接将 x节点 的子树替换 x 节点】

验证 ： 拓扑结构未变；见下图。

示例：

待删节点 x 某一子树为空 - remove图解示例

情况一 代码实现

2. 情况二 ：

x 左右子树都存在（非空），删除调整怎么做？
采取的解决策略： 化繁为简 (化为情况一，然后按情况一解决)

算法步骤

• Step 1 ： 找中序遍历下的 x 的 直接后继，交换两者 swap
• Step 2 ：此时交换后删除 x 节点，变成情况一，执行一的相关操作即可

示例 ：

待删除节点x 左右子树都存在 - remove图解示例

情况二 代码实现

BST的删除操作的复杂度 O(h); [ h 为树高 ]