二叉排序樹(shù)/二叉查找樹(shù)/二叉搜索樹(shù)BST

set和map的實(shí)現(xiàn)基礎(chǔ)
查找

BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p)
{
    p=NULL;   //p指向被查找結(jié)點(diǎn)的雙親結(jié)點(diǎn)，用于插入和刪除操作中
    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){
        //注意因?yàn)閭鞯腡是引用這樣就讓本身為空的lchild或者rchild指向新建的結(jié)點(diǎn)
        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中沒(méi)有引用對(duì)父節(jié)點(diǎn)的left或right的賦值要靠返回來(lái)實(shí)現(xiàn)

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;
}

構(gòu)造
依次輸入數(shù)據(jù)元素，并將它們插入二叉排序樹(shù)的適當(dāng)位置

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

刪除
刪除葉節(jié)點(diǎn)，僅有一邊子樹(shù)的節(jié)點(diǎn)都比較好解決，關(guān)鍵是左右子樹(shù)都有的節(jié)點(diǎn)

二叉排序樹(shù)的刪除.PNG

BinTree Delete(ElementType X, BinTree BST)
{
    Position Tmp;
    if(!BST) printf("沒(méi)找到");
    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){    //有兩個(gè)孩子的情況
            //用右樹(shù)中最小的節(jié)點(diǎn)的值去替換被刪除結(jié)點(diǎn)的值
            //再刪除這個(gè)最小節(jié)點(diǎn)（它不可能有兩個(gè)節(jié)點(diǎn)）
            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回去，把被刪除節(jié)點(diǎn)的右孩子賦給其父節(jié)點(diǎn)
            else if(!BST->Right)
                BST=BST->Left;
            free(Tmp);
        }
    return BST;
}

插入時(shí)，重復(fù)元的插入可用在結(jié)點(diǎn)記錄中添加一個(gè)附加字段來(lái)指示此數(shù)據(jù)出現(xiàn)的頻率來(lái)處理。但如果用于比較的關(guān)鍵字僅是記錄的部分成員，這樣即使關(guān)鍵字相同也是兩個(gè)不同的記錄，這種情況可以把具有相同鍵的所有數(shù)據(jù)保留在一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)中，如表等。
懶惰刪除
當(dāng)刪除次數(shù)不多時(shí)，可將被刪除結(jié)點(diǎn)仍保留在樹(shù)中，但有一個(gè)被刪除的記號(hào)，若有重復(fù)項(xiàng)則將表示其頻率的附加字段減一。

查找效率分析
對(duì)于高度為h的二叉排序樹(shù)，其插入和刪除操作都是O（h）
但在最壞的情況下，輸入序列是有序的，則會(huì)形成一個(gè)傾斜的單只樹(shù)。
上圖中刪除之前的二叉樹(shù)平均查找長(zhǎng)度為
ASL=（1+2x2+4x3+2x4+1x5）/10=3
但如果它是個(gè)單只樹(shù)的話
ASL=(1+2+....+10)/10=5.5
平均查找長(zhǎng)度主要取決與樹(shù)的高度，當(dāng)它為單只樹(shù)時(shí)O(n)，當(dāng)它為平衡二叉樹(shù)時(shí)O(log(2)n)
與二分查找相比，由于二分查找的對(duì)象是有序順序表，插入刪除的效率為O(n)，而二叉排序樹(shù)為O(log(2)n)。所以當(dāng)有序表是靜態(tài)查找表時(shí)，宜用順序表作為其存儲(chǔ)結(jié)構(gòu)，而采用二分查找實(shí)現(xiàn)查找操作。若有序表是動(dòng)態(tài)查找表，則應(yīng)選擇二叉排序樹(shù)作為其邏輯結(jié)構(gòu)。