查找概论2-二叉排序树

既要使插入、删除的效率高也要使查找的效率高，即实现高效率的动态查找表——引入二叉排序树

二叉排序树

---

• 定义：若左子树不为空，则左子树节点值均小于根节点值；若右子树不为空，则节点值均大于根节点值；左右子树均为二叉排序树。
  QQ截图20140808163818.jpg
• 二叉排序树的节点可以定义为如下形式

struct BNode
{
    int data;
    BNode *lhs,*rhs;
};

• 查找操作 可以采用递归的形式，其中T为指向根节点的指针，key为所寻找的值，p为找到后指向节点的指针，pT一直保持指向所要开始找的节点的父节点，若最终没有找到，则p=pT，表明最后搜索的位置，便于后续的插入操作。

//二叉排序树搜索
bool searchBST(BNode *T,int key, BNode *pT,BNode *p)
{
    if(!T)
    {
        p = pT;
        return false;
    }
    else if(key == T->data)
    {
        p = T;
        return true;
    }
    else if(key<T->data)
        return(T->lhs,key,T,p);
    else if(key>T->data)
        return(T->rhs,key,T,p);
}

• 插入操作 可以通过调用查找操作进行简化，插入总是插入称为叶子节点，利用指针操作，具有较高的效率

//插入
bool insertBST(BNode *T,int key)
{
    BNode *p;
    if(!searchBST(T,key,NULL,p))
    {
        BNode * s = new BNode();
        s->data = key;
        s->lhs = NULL;
        s->rhs = NULL;
        if(!p)                            //表明为根节点
            p = s;
        if(key>p->data)           
            p->rhs = s;
        else
            p->lhs = s;
        return true;
    }
    else
        return false;
}

• 创建二叉树 利用插入操作可以创建一颗二叉排序树

//建立一个二叉树
#include <ctime>
void createBTree(BNode * head)
{
    srand(time(NULL));
    int num = 10;
    while (num--)
        insertBST(head,rand()%100);
}

• 删除节点 相对复杂，需要考虑三种情况

1、删除节点为叶子节点，直接删除即可
2、删除节点只包含左子树或者只包含右子树，这时候将其子树续接后删除该节点即可
3、删除节点包含左、右子树，考虑用里该节点最近的节点进行替换，替换后删除替换的那个节点即可

• 其中最近的节点指中序遍历中其前后节点，获取方法有（1）从删除节点开始，先左拐，然后一直右拐；（2）从删除节点开始，先右拐，然后一直左拐；替换后需要删除的节点情形一定是1或者2，按照上述方法删除即可。详细代码如下

//删除二叉排序树的节点，采用递归的思想，和采用查找的时候一样
//分为叶子节点——直接删除即可
//删除节点只有左子树或者右子树——删除后把其子树替代原先的节点位置
//删除节点有两个子树
bool deleteNode(BNode *T)
{
    if(T->lhs == NULL  && T->rhs == NULL)   //叶子节点
    {
        delete(T);
    }else if(T->lhs == NULL)                //只有右子树
    {
        BNode *q = T;
        T->data = T->rhs->data;
        T->lhs = T->rhs->lhs;
        T->rhs = T->rhs->rhs;
        delete(T->rhs);
    }else if(T->rhs == NULL)                //只有左子树
    {
        BNode *q = T;
        T->data = T->rhs->data;
        T->rhs = T->lhs->rhs;
        T->lhs = T->lhs->lhs;
        delete(T->lhs);
    }else                                   //有左右子树
    {
        BNode *q = T->lhs;
        BNode *p = T;
        while(q->rhs)
        {
            p = q;
            q = q->rhs;
        }
        T->data = q->data;
        if(q==p->lhs)
            T->lhs = q->lhs;
        else
            p->rhs = q->lhs;
        delete(q);
    }
    return true;
}
bool deleteBST(BNode *T,int key)
{
    if(T == NULL)
        return false;
    if(T->data<key)
        deleteBST(T->rhs,key);
    else if(T->data>key)
        deleteBST(T->lhs,key);
    else
        return deleteNode(T);
}

小结

---

• 以链式存储的二叉排序树，对于插入删除具有较高的效率
• 同时由于左右子树的树形结构，对于查找也是相当的便利，最大查找次数=树的深度\层数，如果二叉排序树完全平衡，则其深度为（向下取整）[logn]+1,那么其查找的复杂度为O(logn)。

reference

---

• 大话数据结构