查找

關(guān)鍵詞

1. 關(guān)鍵字
2. 主關(guān)鍵字
3. 次關(guān)鍵字

平均查找長度

定義: 需和給定值比較的關(guān)鍵字的個數(shù)的期望值,成為查找成功時的平均查找長度

對于有n個關(guān)鍵字的表,其平均查找長度如下:

其中是查找第i個關(guān)鍵字的概率,可知 (個人理解給定值出現(xiàn)在位置i上的概率)

是在i位置查找到目標(biāo)值時,已經(jīng)比較過的關(guān)鍵字的個數(shù).

靜態(tài)查找表

靜態(tài)查找表的順序存儲結(jié)構(gòu)

typedef struct{
    Elemtype *list;
    int ncount;
}SSTable;

順序查找的實現(xiàn)

從后往前找,零號位置作為哨兵,這樣不用沒找一次比較一次,當(dāng)查找量大于1000的時候,是可以提高一倍效率的.

int search(SSTable &list,Elemtype keyword){
    (list.list)[0]=keyword;
    int i=list.ncount;
    while ((list.list)[i]==keyword) i--;
    return i;
}

性能分析

如果在第一個位置需要查找n次,如果在最后一個位置需要查找1次,于是可以歸納出在第i個位置需要查找<u>n-i+1</u>次

一般情況下,出現(xiàn)在每個目標(biāo)出現(xiàn)在每個位置的概率時相等的,即

tip:上述討論是忽略了查找不成功的情況的,一般情況下查找不成功的概率確實小的可以忽略不計.

有序表的查找

折半查找算法(實際上就是二分查找)

int search_bin(SSTable &list,Elemtype key){
    int l=1,r=list.ncount;
    while (l<=r>){
        int mid=(l+r)/2;
        if (key==(list.list)[mid]) return mid;
        else if(key>(list.list)[mid]) l=mid+1;
        else r=mid-1;
    }
    return 0;
}

性能分析

• 通過判定樹來分析

• 有n個節(jié)點的樹的最大深度是

• 訪問第h層的節(jié)點總共需要訪問個節(jié)點(最壞情況)

二叉樹第h層有個節(jié)點
h層的二叉樹有個節(jié)點
等比數(shù)列公式:

為了方便計算,假設(shè)一個深度為h的滿二叉樹,此時,并且目標(biāo)值出現(xiàn)在每個位置的概率是相同的

可以得到:

當(dāng)n比較大的時候()時,可以近似等于

動態(tài)查找樹表

動態(tài)查找表的特點:表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的,即若存在返回索引,不存在插入

二叉排序樹(BST)

定義:

二叉排序樹或者是一顆空樹,或者是符合以下定義的樹:
(1)若它的左子樹不為空,則左子樹上所有的節(jié)點均小于根節(jié)點上的值
(2)若它的右子樹不為空,則右子樹上所有的節(jié)點均大于根節(jié)點上的值
(3)它的左子樹和右子樹同樣是二叉排序樹

儲存結(jié)構(gòu):(和二叉樹其實是一樣的)

typedef struct BiTNode{
    elemtype data;
    struct BiTNode *lchild,*rchild;
}BiTNODE,*BiTree;

查找算法

BiTree search(BiTree root,elemtype key,BiTree &pre,BiTree &p){
    //p是要傳給外部的參數(shù)
    if (!root) {p=pre;return NULL;} //返回上一個
    if (root->data==key) return root;
    else if(key>root->data) search(root->rchild,key,root);
    else search(root->lchild,key,root,p);
}

插入算法

int add(BiTree &T,elemtype key){
    BiTree temp;
    if (!search(T,key,T,temp)){
        //生成節(jié)點
        BiTree newnode=(BiTree)malloc(sizeof(BiTNode));
        *newnode={key,NULL,NULL};
        if (!temp) T=newnode;
        else{
            if (key>T->data) temp->lchild=newnode;
            else temp->rchild=newnode;
        }
    }
    else return -1;
    return 0;
}

刪除算法

分為三種
(1)被刪除的只有葉子節(jié)點
(2)被刪除的只有左子樹或者右子樹
(3)被刪除的節(jié)點既有左子樹又有右子樹

(1)將雙親節(jié)點的對應(yīng)的指針域改成空

(2)雙親節(jié)點指向被刪除節(jié)點的對應(yīng)的左子樹或者右子樹

(3)可以從左子樹操作也可以從右子樹操作,這里就以左子樹為例.

1. 找到左子樹里面最大的關(guān)鍵字,替換被刪除節(jié)點
2. 剛剛用來替換的那個最大的關(guān)鍵字的右子樹一定是空的,用(2)處理以下就可以了

int delete_1(BiTree& t,elemtype key){
    BiTree &pre,temp;
    temp=search(T,key,T,pre);
    if (!temp) return -1;
    else{
        if (!(temp->rchild)) {pre->next=temp->left;free(temp);}
        else if(!(temp->lchild)) {pre->next=temp->right;free(temp);}//這里的pre->next指所對應(yīng)的左子樹或者右子樹
        else{
            BiTree temp2;
            pre=temp;
            temp2=temp->lchild;
            while (temp2->rchild){pre=temp2; temp2=temp2->rchild;}
            temp->data=temp2->data;
            pre->next=temp2->right;
            free(temp2);
        }
    }
}

tip:這里的代碼可能有問題,重點看一下思路吧

conclude: 對于經(jīng)常需要刪除和添加的有序表,使用二叉排序樹是比較合適的

查找性能分析

對于不同的插入順序,構(gòu)造出來的二叉排序樹是不一樣的,于是查找的復(fù)雜度也是不一樣的,于是這里直接給出計算后的平均值

二叉平衡樹

定義: 平衡二叉樹又稱AVL樹.它或者是一棵空樹,或者是一棵具有如下性質(zhì)的樹:
(1) 它的左子樹和右子樹都是平衡二叉樹
(2) 他的左右子樹深度之差的絕對值不超過1

平衡因子

左子樹的深度與右子樹深度的差值(注意先后順序)

特點

平衡因子的絕對值不大于1

構(gòu)造-平衡旋轉(zhuǎn)技術(shù)

平衡旋轉(zhuǎn)技只針對最小不平衡子樹

平均查找長度在log級別上

4種平衡旋轉(zhuǎn)

1. LL型,右旋一次,被折下去的那個節(jié)點的左子樹會空出來,由定義可以知道,被折下去的部分一定是大于左邊部分的,于是空出來的位置可以接上折上去的節(jié)點的右子樹.

2. RR型,左旋一次,其余原理同LL型是一致的.

3. LR型

4. RL型

tip:怎么插入的這個節(jié)點其實和如何旋轉(zhuǎn)對應(yīng)上了

B-樹

(待續(xù))

哈希表