二叉排序树/二叉查找树/二叉搜索树BST

set和map的实现基础
查找

BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p)
{
    p=NULL;   //p指向被查找结点的双亲结点，用于插入和删除操作中
    while(T!=NULL&&key!=T->data{
        p=T;
        if(key<T->data)    T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

插入

int BST_Insert(BiTree &T, KeyType k)
{
    if(T==NULL){
        //注意因为传的T是引用这样就让本身为空的lchild或者rchild指向新建的结点
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(k==T->key)
                return 0;
    else if(k<T->key)
                return BST_Insert(T->lchild, k);
    else
                return BST_Insert(T->rchild, k);
}

不使用引用
C中没有引用对父节点的left或right的赋值要靠返回来实现

BinTree Insert(ElementType X, BinTree BST)
{
    if(!BST){
        BST=malloc(sizeof(struct TreeNode));
        BST->Data=X;
        BST->Left=BST->Right=NULL;
    }else
         if(X<BST->Data)
             BST->Left=Insert(X, BST->Left);
         else if(X>BST->Data)
             BST->Right=Insert(X, BST->Right);
    return BST;
}

构造
依次输入数据元素，并将它们插入二叉排序树的适当位置

void Creat_BST(BiTree &T, KeyType str[], int n)
{
    T=NULL;
    int i=0;
    while(i<n){
        BST_Insert(T, str[i]);
        i++;
    }
}

删除
删除叶节点，仅有一边子树的节点都比较好解决，关键是左右子树都有的节点

二叉排序树的删除.PNG

BinTree Delete(ElementType X, BinTree BST)
{
    Position Tmp;
    if(!BST) printf("没找到");
    else if(X<BST->Data)
        BST->Left=Delete(X, BST->Left);
    else if(X>BST->Data)
        BST->Right=Delete(X, BST->Right);
    else
        if(BST->Left&&BST->Right){    //有两个孩子的情况
            //用右树中最小的节点的值去替换被删除结点的值
            //再删除这个最小节点（它不可能有两个节点）
            Tmp=FindMin(BST->Right);
            BST->Data=Tmp->Data;
            BST->Right=Delete(Tmp->Data, BST->Right);
        }else{
            Tmp=BST;
            if(!BST->Left)
                BST=BST->Right;    //return回去，把被删除节点的右孩子赋给其父节点
            else if(!BST->Right)
                BST=BST->Left;
            free(Tmp);
        }
    return BST;
}

插入时，重复元的插入可用在结点记录中添加一个附加字段来指示此数据出现的频率来处理。但如果用于比较的关键字仅是记录的部分成员，这样即使关键字相同也是两个不同的记录，这种情况可以把具有相同键的所有数据保留在一个辅助数据结构中，如表等。
懒惰删除
当删除次数不多时，可将被删除结点仍保留在树中，但有一个被删除的记号，若有重复项则将表示其频率的附加字段减一。

查找效率分析
对于高度为h的二叉排序树，其插入和删除操作都是O（h）
但在最坏的情况下，输入序列是有序的，则会形成一个倾斜的单只树。
上图中删除之前的二叉树平均查找长度为
ASL=（1+2x2+4x3+2x4+1x5）/10=3
但如果它是个单只树的话
ASL=(1+2+....+10)/10=5.5
平均查找长度主要取决与树的高度，当它为单只树时O(n)，当它为平衡二叉树时O(log(2)n)
与二分查找相比，由于二分查找的对象是有序顺序表，插入删除的效率为O(n)，而二叉排序树为O(log(2)n)。所以当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现查找操作。若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

---