07-查找錶

鹹魚的學習 2022-01-08 03:17:53 阅读数:548

07- 查找

查找錶

一、認識查找錶

  • 查找錶:給定一個由同一類型的數據元素(或記錄)構成的集合,從中查找指定數據項(或數據元素某個特征)的數據元素或記錄
  • 查找錶的主要操作
    • 查詢某個“特定的”數據元素是否在查找錶中
    • 檢索某個“特定的”數據元素的各種屬性
    • 在查找錶中插入一個數據元素
    • 從查找錶中删去某個數據元素
  • 查找錶的分類
    • 靜態查找錶:僅作查詢和檢索操作的查找錶
    • 動態查找錶:在查找過程中同時插入查找錶中不存在的數據元素,或者從查找錶中删除已存在的某個數據元素
  • 關鍵字/Key
    • 是數據元素中某個數據項的值,用以錶示一個數據元素
    • 若此關鍵字可以識別惟一的一個記錄,則稱之為“主關鍵字”
    • 若此關鍵字可以識別若幹記錄,則稱之為“次關鍵字”
  • 查找/Searching
    • 根據給定的某個值,在查找錶中確定一個其關鍵字等於給定值的數據元素
    • 若查找錶中存在這樣一個記錄,則稱“查找成功”,查找結果:給出整個記錄信息,或指示該記錄在查找錶中的比特置;否則稱“查找不成功”,查找結果:給出“空記錄”或“空指針”
  • 查找方法
    • 查找的方法取决於查找錶的結構,所謂查找錶的結構來自於對集合中的元素間人為添加的“關系”。
  • 查找性能的評價
    • 查找速度、占用存儲空間多少、算法本身複雜程度
    • 平均查找長度ASL(Average Search Length)
      • 為確定記錄在錶中的比特置,需和給定值進行比較的關鍵字的個數的期望值叫查找錶算法的ASL
      • 對於包括 n n n個記錄的錶,查找成功時 A S L = ∑ i = 1 n p i c i ASL=\sum_{i=1}^np_ic_i ASL=i=1npici
      • 其中 p i p_i pi為查找錶中第 i i i個記錄的概率,且 ∑ i = 1 n p i = 1 \sum_{i=1}^np_i=1 i=1npi=1 c i c_i ci為找到查找錶中第 i i i個記錄需要比較關鍵字的次數

二、靜態查找錶

  • ADT
    ADT StaticSearchTable{
    
    數據對象D:D時具有相同天熱行的數據元素的集合
    數據關系R:數據元素同屬一個集合
    基本操作:
    Create(&ST,n); //構造一個含n個數據元素的靜態查找錶ST
    Destroy(&ST); //銷毀錶ST
    Search(ST,key); //查找ST中其關鍵字等於key的元素
    Traverse(ST,Visit());//按某種次序對ST的每個元素調用Visit函數一次且僅一次
    }ADT StaticSearchTable
    
  • 靜態查找錶的類型
    • 順序查找錶:集合元素間添加序偶關系,構成順序錶
    • 有序查找錶:集合元素間依據大小添加序偶關系,構成有序錶
    • 索引順尋標:集合元素分塊,塊間有序,塊內無序
  • 順序查找錶
    int Search_Seq(SSTable ST, KeyType key)
    {
    
    ST.elem[0].key=key; //設置哨兵
    for(i=ST.length;ST.elem[i].key!=key;--i);//從後往前找
    return i; //找不到時,i為0
    }//Search_Seq
    
    • 性能分析
      • 平均查找長度
        • 等概率查找: p i = 1 n , c i = n − i + 1 , A S L = ∑ i = 1 n p i c i = n + 1 2 p_i=\frac{1}{n},c_i=n-i+1,ASL=\sum_{i=1}^np_ic_i=\frac{n+1}{2} pi=n1,ci=ni+1,ASL=i=1npici=2n+1
        • 不等概率查找的情况下, A S L ASL ASL在查找概率滿足 p n ≥ p n − 1 ≥ ⋯ ≥ p 1 p_n\geq p_{n-1}\geq \dots\geq p_1 pnpn1p1時取最小值
        • 若查找概率無法實現測定,則查找過程采取的改進辦法是將訪問頻度大的記錄後移。或每次查找之後,將剛剛查找到的記錄直接移至錶尾的比特置上
      • 查找不成功時
        • 查找算法的 A S L ASL ASL應是查找成功時的 A S L ASL ASL和查找不成功時的 A S L ASL ASL的期望
        • 對順序查找,查找不成功時和給定值進行比較的次數都是 n + 1 n+1 n+1,若設查找成功和不成功可能性相同,對每個記錄的查找概率也相等,則 p i = 1 2 n p_i=\frac{1}{2n} pi=2n1,此時 A S L = 1 2 n + 1 2 + 1 2 ( n + 1 ) = 3 4 ( n + 1 ) ASL=\frac{1}{2}\frac{n+1}{2}+\frac{1}{2}(n+1)=\frac{3}{4}(n+1) ASL=212n+1+21(n+1)=43(n+1)
  • 有序查找錶
    • 將邏輯結構相鄰的元素按關鍵字排好序,則得到有序查找錶,可采用“折半”查找
    • 折半查找/Binary Search
      • 查找過程:每次將待查記錄所在區間縮小一半
      • 適用條件:采用順序存儲結構的有序錶
    int Search_Bin(SSTable ST, KeyType key)
    {
    
    low=1; high=ST.length;
    while(low <= high)
    {
    
    mid=(low+high)/2;
    if(key==ST.elem[mid].key)
    return mid; //找到待查元素
    else if(key < ST.elem[mid].key)
    high=mid-1; //繼續在前半區間進行查找
    else
    low=mid+1; //繼續在後半區間進行查找
    }
    return 0; //順序錶中不存在待查元素
    }
    
    • 性能分析
      • 關鍵字比較次數不超過 └ l o g 2 n ┘ + 1 \llcorner log_2n\lrcorner+1 log2n+1,時間複雜度為 O ( l o g n ) O(logn) O(logn)
      • 特別的,當 n > 50 n>50 n>50,查找成功時的 A S L ≈ l o g 2 ( n + 1 ) − 1 ASL\approx log_2(n+1)-1 ASLlog2(n+1)1
      • 折半查找適用條件:有序的順序錶
    • 斐波那契查找
      • 適用條件:有序靜態查找錶,順序錶的實現方式
      • 將折半查找的“砍一半”搜索空間,改成不平衡地近似砍一半,用斐波那契數做分割點 F n + 1 = F n + F n − 1 F_{n+1}=F_n+F_{n-1} Fn+1=Fn+Fn1
      • 假設有序查找錶長 m = F n + 1 − 1 m=F_{n+1}-1 m=Fn+11,則比較查找關鍵字 k e y key key S T . e l e m [ F n ] . k e y ST.elem[F_n].key ST.elem[Fn].key,前一般有 F n − 1 F_n-1 Fn1個記錄,後一半有 F n − 1 − 1 F_{n-1}-1 Fn11個記錄,采用類似折半查找的方法,遞歸調用
      • 若有序查找錶的長度 m ≠ F n − 1 m\neq F_n-1 m=Fn1,則取錶的前 F n − 1 F_n-1 Fn1項,使得 n n n盡可能大;查找錶後面的項采用遞歸調用斐波那契查找
      • 性能分析:平均優於折半,但最壞比折半差,分割時只需加减運算
    • 插值查找
      • 直接依據給定的 k e y key key值,來估計記錄應該在的比特置,估計比特置的公式 i = k e y − S T . e l e m [ l ] . k e y S T . e l e m [ h ] . k e y − S T . e l e m [ l ] . k e y ( h − l + 1 ) i=\frac{key-ST.elem[l].key}{ST.elem[h].key-ST.elem[l].key}(h-l+1) i=ST.elem[h].keyST.elem[l].keykeyST.elem[l].key(hl+1)
      • 適用條件:關鍵字在查找錶中“均勻分布”
      • 性能:錶大時,平均性能由於折半查找
順序錶 有序錶
錶的特性 無序 有序
存儲結構 順序或鏈式 順序
插删操作 易於進行 需移動元素
ASL的值
  • 索引順序錶
    • 在建立順序錶的同時,建立一個索引項,包括兩項:關鍵字項(塊內最大關鍵字)和指針項(塊在順序錶的起始比特置)
    • 索引錶按關鍵字有序,錶則為分塊有序
    • 又稱分塊查找
      • 查找過程:將錶分成幾塊,塊內無需,塊間有序,先確定待查記錄所在快,再在塊內查找
      • 適用條件:分塊有序錶
    • 算法實現
      • 用數組存放待查記錄,每個數據元素至少含有關鍵字域
      • 建立索引錶,每個索引錶節點含有最大關鍵字域和指向本塊第一個節點的指針
      • 利用索引錶,確定塊,然後再塊內順序查找
     typedef struct IndexType
    {
    
    keyType maxkey;//塊中最大的關鍵字
    int startpos;//塊的起始比特置指針
    }Index;
    int Block_search(RecType ST[],Index ind[],KeyType key,int n,int b)
    {
    
    //在分塊索引錶中查找關鍵字為key的記錄,錶長為n,塊數為b
    //LT小於, LQ小於等於,EQ等於
    int i=0,j;
    while((i<b)&&LT(ind[i].maxkey,key))
    i++;
    if (i>b)
    {
    
    printf("\nNot found"); return(0);
    }
    j=ind[i].startpos;
    while((j<n)&&LQ(ST[j].key,ind[i].maxkey))
    {
    
    if ( EQ(ST[j].key, key) )
    break;
    j++;
    } //在塊內查找
    if (j>=n||!EQ(ST[j].key,key))
    {
    
    j=0;
    printf("\nNot found");
    }
    return(j);
    }
    
    • 性能分析
      • A L S = L b + L w ALS=L_b+L_w ALS=Lb+Lw L b L_b Lb,查找索引錶,確定所在塊的平均查找長度, L w L_w Lw,塊中查找元素的平均查找長度
      • 若長為 n n n的錶被平均分為 b b b塊,則每塊包含 s = n b s=\frac{n}{b} s=bn個記錄,假設每個記錄的查找概率相等
        • 若用順序查找確定塊比特置 A S L = 1 b ∑ i = 1 b i + 1 s ∑ j = 1 s j = b + 1 2 + s + 1 2 = + f r a c 12 ( n s + s ) + 1 ASL=\frac{1}{b}\sum_{i=1}^bi+\frac{1}{s}\sum_{j=1}^sj=\frac{b+1}{2}+\frac{s+1}{2}=+frac{1}{2}(\frac{n}{s}+s)+1 ASL=b1i=1bi+s1j=1sj=2b+1+2s+1=+frac12(sn+s)+1
        • 若用折半查找確定塊比特置 A S L ≈ l o g 2 ( n s + 1 ) + s 2 ASL\approx log_2(\frac{n}{s}+1)+\frac{s}{2} ASLlog2(sn+1)+2s
順序查找 有序查找 分塊查找
ASL 最大 最小 兩者之間
錶結構 有序錶、無序錶 有序錶 分塊有序錶
存儲結構 順序存儲結構/線性鏈錶 順序存儲結構 順序存儲結構/線性鏈錶
  • 幾種查找錶的對比
查找 插入 删除
無序順序錶 O(n) O(1) O(n)
無序線性鏈錶 O(n) O(1) O(1)
有序順序錶 O(logn) O(n) O(n)
有序線性鏈錶 O(n) O(n) O(n)
靜態查找樹錶 O(nlogn) O(nlogn) O(nlogn)
  • 結論
    • 從查找性能看,最好情况能達 O ( l o g n ) O(logn) O(logn),要求錶有序
    • 從插入和删除的性能看,最好情况能達 O ( 1 ) O(1) O(1),要求存儲結構時鏈錶

三、動態查找錶

  • ADT
    ADT DynamicSearchTable{
    
    數據對象D:D是具有相同特性的數據元素的集合
    數據關系R:數據元素同屬一個集合
    基本操作:
    InitDSTable(&DT);
    DestroyDSTable(&DT);
    SearchDSTable(DT,key);
    InsertDSTable(&DT,e);
    DeleteDSTable(&DT,key);
    TraverseDSTable(DT, Visit());
    }ADT DynamicSearchTable
    
  • 動態查找錶的分類
    • 二叉排序樹:待查記錄集合的元素構建二叉樹式的邏輯結構
    • B − B^- B樹和 B + B^+ B+樹:待查記錄集合的元素構成多叉樹的邏輯結構
    • 鍵樹
  • 二叉排序樹
    • 二叉排序樹或者是一棵二叉樹,或者是具有如下特性的樹
      • 若左子樹不空,左子樹所有節點值均小於根節點值
      • 若右子樹不空,右子樹所有節點值均大於根節點值
      • 它的左右子樹也都是二叉排序樹
    • 查找算法思想
      • 若二叉排序樹為空,則查找不成功
      • 若給定值等於根節點的關鍵字,查找成功
      • 若給定值小於根節點的關鍵字,繼續在左子樹上查找
      • 若給定值大於根節點的關鍵字,繼續在右子樹上查找
    Status SearchBST(BiTree T, KeyType key,BitNode* &f,BitNode* &p)
    {
    
    if (!T)
    {
    
    p=f; //p指向查找路徑上訪問的最後一個結點並返回FALSE
    return FALSE;
    }
    if EQ(key, T->data.key)
    {
    
    p=T; //若查找成功,p指向該結點,並返回TRUE
    return TRUE;
    }
    if LT(key,T->data.key)
    {
    
    f=T;
    return(SearchBST(T->lchild,key,f,p));
    // 在左子樹中繼續查找
    }
    else
    {
    
    f=T;
    return(SearchBST(T->rchild, key,f,p));
    // 在右子樹中繼續查找
    }
    }//SearchBST
    
    • 二叉排序樹的中序遍曆為一個關鍵字的有序序列
    • 二叉排序樹的插入算法
      • 若二叉樹為空樹,則新插入的結點為新的根節點,否則,新插入的結點必為一個新的葉子結點,其插入比特置由查找過程得到
    Status InsertBST(BiTree &T, ElemType e)
    {
    
    if (!SearchBST(T,e.key,NULL,p))
    {
     //查找不成功
    BiTree* s = (BiTree)malloc(sizeof(BiTNode));
    s->data=e;
    s->lchild=s->rchild=NULL;
    if (!p)
    T=s; //插入s為新的根結點
    else if LT(e.key,p->data.key)
    p->lchild=s;//插入*s為*p的左孩子
    else
    p->rchild=s; //插入*s為*p的右孩子
    return TRUE; //插入成功
    }
    else
    return FALSE;
    } //Insert BST
    
    • 二叉排序樹的删除算法
      • 被删除的結點只有左子樹或只有右子樹,其雙親結點的指針域的值改為“指向被删除節點的左子樹或右子樹”
      • 被删除的結點既有左子樹,也有右子樹,用中序遍曆二叉樹輸出結構序列中被删除節點的前驅替代之,然後在删除該前驅節點
      • 被删除的結點是葉子,删去即可
    Status DeleteBST(BiTree &T, KeyType key)
    {
    
    BitNode *f=NULL, *p;
    if (!SearchBST(T,key,f,p)) //查找不成功
    return FALSE; //不存在關鍵字等於key的數據元素
    Delete(p,f);
    }//DeleteBST
    void Delete(BiTree &p, BiTree f)
    {
    //删除過程
    //從二叉排序樹中删除結點p,並重接它的左子樹或右子樹
    if (!p->rchild && !p->lchild)
    {
    ......;return ..}//删除葉子節點
    if (!p->rchild)
    {
    ......} //左孩子為空
    else if (!p->lchild)
    {
    ......} //右孩子為空
    else {
    ......}//左右孩子都非空
    }//Delete
    
    • 二叉排序樹操作的性能
      • 插入和删除的開銷都集中在查找操作
      • n個關鍵字,可構造不同形態的二叉排序樹,其平均查找長度可能會不同,甚至可能差別很大
      • 共有 n ! n! n!種不同的輸入序列,每個輸入序列對應一棵二叉排序樹,假設每棵二叉排序樹種每個關鍵字被等概查找,那麼得到平均查找長度為 2 n + 1 n l o g 2 n + C = O ( l o g n ) 2\frac{n+1}{n}log_2n+C=O(logn) 2nn+1log2n+C=O(logn)
  • 平衡二叉排序樹
    • 引入的原因
      • 二叉排序樹平均查找長度受樹的形態影響較大,形態比較均勻時查找效率較好,因此希望有形態總是均衡的二叉排序樹,查找時有最好的效率,這就是平衡二叉排序樹
    • AVLTree或者是空樹,或者是滿足下列性質的二叉樹
      • 左子樹和右子樹深度之差的絕對值不大於1
      • 左子樹和右子樹也都是平衡二叉樹
    • 平衡因子
      • 稱二叉樹上結點左子樹的深度减去右子樹深度為結點的平衡因子
      • 平衡二叉樹上的每個結點的平衡因子只可能是-1,0,1,否則,只要一個結點的平衡因子的絕對值大於1,該二叉樹就不是平衡二叉樹
    • 性質
      • 在平衡二叉排序樹上執行查找的過程與二叉排序上的查找過程一樣,和給定 k e y key key值比較的次數不超過樹的深度
      • 設深度為 h h h的平衡二叉排序樹所具有的最少結點數 N h N_h Nh,則 N h N_h Nh滿足遞推關系: N 0 = 0. N 1 = 1 , N 2 = 2 , ⋯ , N h = N h − 1 + N h − 2 N_0=0.N_1=1,N_2=2,\cdots,N_h=N_{h-1}+N_{h-2} N0=0.N1=1,N2=2,,Nh=Nh1+Nh2,類似斐波那契數,可解的 h = ≈ l o g Φ ( 5 ( n + 1 ) ) − 2 h=\approx log_{\Phi}(\sqrt{5}(n+1))-2 h=logΦ(5 (n+1))2,其中 Φ = 5 + 1 2 \Phi=\frac{\sqrt{5}+1}{2} Φ=25 +1
      • 平均查找長度和 l o g 2 n log_2n log2n是一個量級的,也是 O ( l o g n ) O(logn) O(logn)
    • 平衡化旋轉(LL,LR,RL,RR)
      • 失衡結點:沿著插入或删除結點上行到根節點就能找到受到影響的結點,這些結點的平衡因子和子樹深度都可能會發生變化,平衡因子絕對值大於1的結點稱為失衡結點
      • L L LL LL型平衡化旋轉
        • 失衡節點a初始時刻平衡因子為1,在結點a的左孩子b的左子樹上進行插入x,使得a的平衡因子變成2
        • 插入前: a = 1 , b = 0 a=1,b=0 a=1,b=0,插入後: b = 1 , a = 2 b=1,a=2 b=1,a=2,旋轉後 a = 0 , b = 0 a=0,b=0 a=0,b=0
        • 順時針旋轉以a為根的子樹
        typedef struct BNode
        {
        
        KeyType key; //關鍵字域
        int Bfactor; //平衡因子域
        ... //其它數據域
        struct BNode *Lchild, *Rchild;
        }BSTNode;
        void LL_rorate(BSTNode *a)
        {
        
        BSTNode* b;
        b=a->Lchild;
        a->Lchild=b->Rchild;
        b->Rchild=a;
        a->Bfactor=b->factor=0;
        a=b;
        }
        
      • L R LR LR型平衡化旋轉
        • 失衡節點a初始時刻平衡因子為1,在結點a的左孩子b的右子樹上插入x,使得a的平衡因子變成2
        • 插入前: a = 1 , b , c = 0 a=1,b,c=0 a=1,b,c=0,插入後: c = 0 , 1 , − 1 , b = − 1 , a = 2 c=0,1,-1,b=-1,a=2 c=0,1,1,b=1,a=2,旋轉後 ( − 1 , 0 , 0 ) , ( 0 , 1 , 0 ) , ( 0 , 0 , 0 ) (-1,0,0),(0,1,0),(0,0,0) (1,0,0),(0,1,0),(0,0,0)
        • 先逆時針旋轉a的左子樹,再順時針旋轉a為根的子樹
        void LR_rotate(BSTNode *a)
        {
        
        BSTNode *b,*c;
        b=a->Lchild;
        c=b->Rchild;
        a->Lchild=c->Rchild;
        b->Rchild=c->Lchild;
        c->Lchild=b;
        c->Rchild=a;
        if(c->Bfactor==1)
        {
        
        a->Bfactor=-1;
        b->Bfactor=0;
        c->Bfactor=0;
        }
        else if(c->Bfactor==0)
        a->Bfactor=b->Bfactor=0;
        else
        {
        
        a->Bfactor=0;
        b->Bfactor=1;
        c->Bfactor=0;
        }
        }
        
      • R L RL RL型平衡化旋轉
        • 失衡結點a初始時平衡因子為-1,在結點a的右孩子b的左子樹上插入x,使得a的平衡因子變成-2
        • 插入前: a = − 1 , b , c = 0 a=-1,b,c=0 a=1,b,c=0,插入後: c = 0 , − 1 , 1 , b = 1 , a = − 2 c=0,-1,1,b=1,a=-2 c=0,1,1,b=1,a=2,旋轉後: ( 1 , 0 , 0 ) , ( 0 , − 1 , 0 ) , ( 0 , 0 , 0 ) (1,0,0),(0,-1,0),(0,0,0) (1,0,0),(0,1,0),(0,0,0)
        • 先順時針旋轉a的右子樹,再逆時針旋轉a為根的子樹
        void RL_rotate(BSTNode *a)
        {
        
        BSTNode *b,*c;
        b=a->Rchild;
        c=b->Lchild;
        a->Rchild=c->Lchild;
        b->Lchild=c->Rchild;
        c->Lchild=a;
        c->Rchild=b;
        if(c->Bfactor==1)
        {
        
        a->Bfactor=0;
        b->Bfactor=-1;
        c->Bfactor=0;
        }
        else if(c->Bfactor==0)
        a->Bfactor=b->Bfactor=0;
        else
        {
        
        a->Bfactor=1;
        a->Bfactor=0;
        a->Bfactor=0;
        }
        }
        
      • R R RR RR型平衡化旋轉
        • 失衡節點a初始時刻平衡因子為-1,在結點a的右孩子b的右子樹上進行插入x,使得a的平衡因子變為-2.
        • 插入前: a = − 1 , b = 0 a=-1,b=0 a=1,b=0,插入後 b = − 1 , a = − 2 b=-1,a=-2 b=1,a=2,旋轉後: a = 0 , b = 0 a=0,b=0 a=0,b=0
        • 逆時針旋轉以a為根的子樹
        BSTNode* RR_rotate(BSTNode *a)
        {
        
        BSTNode *b;
        b=a->Rchild;
        a->Rchild=b->Lchild;
        b->Lchild=a;
        a->Bfactor=b->Bfactor=0;
        a=b;
        }
        

四、改進索引技術

  • 索引順序錶:將數據錶分塊,塊間有序,塊內無序,塊有索引
    • 如果每個記錄都建立索引,即塊的大小為1,這就給數據建立了稠密的索引錶
    • 索引錶有序,可以用折半查找或平衡二叉樹來構造索引錶
    • 適用場景:
      • 記錄大小不固定,或者每個記錄都很大
      • 記錄存儲在外存,內存放不下,比如數據庫文件
      • 增删記錄的操作非常頻繁時,不移動數據,僅更新索引錶
  • 樹形索引錶
    • 用平衡二叉樹來組織索引錶可行,但大型數據庫不可行
    • 因此,必須選擇一種盡可能降低磁盤I/O次數的索引組織方式,樹結點的大小盡可能地接近頁的大小,由此提出了多路平衡查找樹,稱為 B − B^- B
  • 磁盤結構
    • 磁盤是很多塊構成的集合
    • 每個塊有自己的“地址”,用於查找給定地址的塊
    • 每個磁盤塊的大小都是固定的,格式化的時候設定
    • 磁盤塊是磁盤讀取的基本單比特
  • B − B^- B
    • B − B^- B樹主要用於文件系統種,在 B − B^- B樹中,每個結點的大小為一個磁盤頁,結點中所包含的關鍵字及其孩子的數目取决於頁的大小
    • 一棵 m m m B − B^- B樹,或者是空樹,或者是滿足以下性質的 m m m叉樹
      • 根結點或者是葉子,或者至少有兩棵子樹,至多有 m m m棵子樹
      • 除根結點外,所有非終端結點至少有 ┌ m 2 ┐ \ulcorner\frac{m}{2}\urcorner 2m棵子樹,至多 m m m棵子樹
      • 所有葉子結點都在樹的同一層上
      • 每個結點應包含如下信息: ( n , A 0 , K 1 , A 1 , K 2 , A 2 , … , K n , A n ) (n,A_0,K_1,A_1,K_2,A_2,\dots,K_n,A_n) (n,A0,K1,A1,K2,A2,,Kn,An),其中 K i K_i Ki是關鍵字,且 K i < K i + 1 K_i<K_{i+1} Ki<Ki+1 A i A_i Ai是指向孩子結點的指針,且 A i − 1 A_{i-1} Ai1所指向的子樹中所有的結點的關鍵字都小於 K i K_i Ki A i A_i Ai所指向的子樹中所有結點的關鍵字都大於 K i K_i Ki n n n是結點中關鍵字的個數,且 ┌ m 2 ┐ − 1 ≤ n ≤ m − 1 \ulcorner\frac{m}{2}\urcorner-1\leq n\leq m-1 2m1nm1
      • 存儲結構
      #define M 5 //根據實際需要定義B-樹的階數
      typedef struct BTNode{
      
      int keynum; //結點中關鍵字數目
      struct BTNode *parent; //指向父節點的指針
      KeyType key[M]; //關鍵字向量,key[0]未用
      struct BTNode *ptr[M]; //子樹指針向量
      RecType *recptr[M];
      //記錄指針向量,recptr[0]未用
      }BTNode;
      
      • B − B^- B樹的查找
        • 從樹的根節點 T T T開始,在 T T T所指向的結點的關鍵字向量 k e y [ 1... k e y n u m ] key[1...keynum] key[1...keynum]中查找給定值 K K K(折半查找),若沒找到,則將 K K K與各個分量的值進行比較
          • K < k e y [ 1 ] : T = T − > p t r [ 0 ] K<key[1]:T=T->ptr[0] K<key[1]:T=T>ptr[0]
          • k e y [ i ] < K < k e y [ i + 1 ] , T = T − > p t r [ i ] key[i]<K<key[i+1],T=T->ptr[i] key[i]<K<key[i+1],T=T>ptr[i]
          • K > k e y [ k e y n u m ] : T − > p t r [ k e y n u m ] K>key[keynum]:T->ptr[keynum] K>key[keynum]:T>ptr[keynum]
        • 直到 T T T是葉子結點且未找到相等關鍵字,查找失敗
        int BT_search(BTNode* T, KeyType K, BTNode *p)
        {
        
        //在B-樹種查找關鍵字K,查找成功返回在結點中的比特置
        //及結點指針p;否則返回0及最後一個指針
        BTNode *q;
        int n;
        p = q = T;
        while(q!=NULL)
        {
        
        p=q;
        q->key[0]=K; //設置查找哨兵
        for(n=q->keynum;K<=q->key[n];n--)
        {
        
        if(n>0&&EQ(q->key[n],K));
        return n;
        }
        q=q->ptr[n];
        }
        }
        
        • 性能分析
          • 分為找節點和在節點中找關鍵字,在節點中找關鍵字是堆內存操作,找節點是對外存數據處理,找節點是影響性能的主要因素
          • 一個節點通常是一個磁盤塊,訪問節點數越少越好
          • 關鍵在於關鍵字所在節點的深度
            • 設被查詢關鍵字在 B − B^- B樹的深度為 h h h
            • 第h層上至少有 ┌ m 2 ┐ h − 2 \ulcorner\frac{m}{2}\urcorner^{h-2} 2mh2個節點
            • 根節點至少包括一個關鍵字,其它節點至少包括 ┌ m 2 ┐ \ulcorner\frac{m}{2}\urcorner 2m個關鍵字,可推的 n ≥ 1 + ( ┌ m 2 ┐ − 1 ) ∑ i = 2 h ( ┌ m 2 ┐ − 1 ) i = 2 ( ┌ m 2 ┐ − 1 ) h − 1 − 1 n\geq1+(\ulcorner\frac{m}{2}\urcorner-1)\sum_{i=2}^h(\ulcorner\frac{m}{2}\urcorner-1)^i=2(\ulcorner\frac{m}{2}\urcorner-1)^{h-1}-1 n1+(2m1)i=2h(2m1)i=2(2m1)h11
            • 推得 h ≤ l o g ┌ m 2 ┐ − 1 ( n + 1 2 ) + 1 h\leq log_{\ulcorner\frac{m}{2}\urcorner-1}(\frac{n+1}{2})+1 hlog2m1(2n+1)+1
      • B − B^- B樹的插入
        • B − B^- B樹的種查找關鍵字 K K K,若找到,錶名關鍵字已存在,返回;否則, K K K的查找操作失敗於某個葉子節點,轉下一步
        • K K K插入到該葉子節點中,插入時,若
          • 葉子結點的關鍵字數 < m − 1 <m-1 <m1:直接插入
          • 葉子節點的關鍵字樹 = m − 1 =m-1 =m1:將節點“分裂”
        • 分裂的方法
          • 從中間分成兩個節點,將最中間關鍵字(上界)插入父節點,並以分裂後的兩個節點作為其左右子節點,若父節點被插入新節點後,不滿足 m m m B − B^- B樹定義,繼續分裂
      • B − B^- B樹的删除
        • B − B^- B樹上删除一個關鍵字 K K K,首先找到關鍵字所在的節點 N N N,然後在 N N N中進行關鍵字 K K K的删除操作
        • N N N不是葉子節點,設 K K K N N N中的第 i i i個關鍵字,則將指針 A i − 1 A_{i-1} Ai1所指子樹中的最大關鍵字 K ′ K' K放在 ( K ) (K) (K)的比特置,然後删除 K ′ K' K,而 K ′ K' K一定在葉子節點上
        • 從葉子節點删除一個關鍵字
          • 若節點 N N N中關鍵字個數 > ┌ m 2 ┐ − 1 >\ulcorner\frac{m}{2}\urcorner-1 >2m1,則直接删除關鍵字
          • 若節點 N N N中關鍵字個數 = > ┌ m 2 ┐ − 1 =>\ulcorner\frac{m}{2}\urcorner-1 =>2m1,若節點 N N N的左(右)兄弟節點中關鍵字個數 > ┌ m 2 ┐ − 1 >\ulcorner\frac{m}{2}\urcorner-1 >2m1,則將節點 N N N的左(右)兄弟節點中最大(最小)關鍵字上移到其父節點中,而父節點中大於(小於)且緊靠上移關鍵字的關鍵字下移到節點 N N N
          • 若結點 N N N和其兄弟結點中的關鍵字數 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉−1 =m/21,删除結點 N N N中的關鍵字,再將結點 N N N中的關鍵字、指針與其兄弟結點以及分割二者的父結點中的某個關鍵字 K i K_i Ki,合並為一個結點,若因此使父結點中的關鍵字個數 < ⌈ m / 2 ⌉ − 1 <⌈m/2⌉−1 <m/21,則依此類推
  • B + B^+ B+
    • B − B^- B樹不同,它只用葉子結點存儲記錄,所有非葉子結點可看成索引
    • 一棵 m m m B + B^+ B+
      • 若一個結點有 m m m棵子樹,則必含有 m m m個關鍵字
      • 所有葉子結點中包含了全部記錄的關鍵字信息以及這些關鍵字記錄的指針,而且葉子結點按關鍵字的大小從小到大順序鏈錶
      • 所有非葉子結點可以看成是索引的部分,結點中只含有其子樹的根節點中的最大(或最小)關鍵字
    • B + B^+ B+樹的操作類似 B − B^- B
      • 查詢區別:在非葉節點上找到關鍵字,不停止,沿著路徑找到葉節點
      • 插入區別:僅在葉節點進行,當葉節點包含超過 m m m個關鍵字,則分裂,並在雙親結點中包含分裂後兩個節點的最大關鍵字及指針
      • 删除區別:僅在葉節點進行,當葉節點的最大關鍵字被删除,其雙親的最大關鍵字可當成是“分界關鍵字”依然存在;葉節點過小時,需要類似 B − B^- B樹進行結點合並

五、哈希錶與哈希查找

  • 哈希函數/Hash:哈希函數是一種從關鍵字空間到存儲地址空間的一種映射
  • 哈希錶:根據設定的哈希函數 H ( k e y ) H(key) H(key),將一組關鍵字映射到一個有限的、地址連續的地址集(區間)上,並以關鍵字在地址集中的“象”作為相應記錄在錶中的存儲比特置,如此構造所得的查中錶稱之為“哈希錶”
  • 哈希查找:也叫散列查找,依據給定的關鍵字 k e y key key和哈希函數,直接算出記錄存儲的地址,不經過比較,一次存取就能得到想要查找的記錄
  • 存在的問題:
    • 兩個不同關鍵字計算出相同的哈希地址
      • 這稱之為“沖突”,需要設計一個函數,將所有不同 k e y key key映射到不同的地址
      • 若設計不出,就需要設計沖突解决辦法
    • 哈希錶存在很多空白的空間沒有存放記錄
      • 空間太大,可能很多沒存儲記錄,浪費了;空間太小,可能產生大量沖突
  • 常見哈希函數
    • 直接定址法
      • H ( k e y ) = k e y H(key)=key H(key)=key或者 H ( k e y ) = a × k e y + b H(key)=a\times key+b H(key)=a×key+b
      • 此方法僅適合於:地址集合的大小等於關鍵字集合的大小
    • 平方取中法
      • 以關鍵字的平方值得中間幾比特作為存儲地址
      • 此方法適合於:關鍵字中的每一比特都有某些數字重複出現頻度很高的現象,或不知道關鍵字頻率分布情况時
    • 隨機數法
      • 設定哈希函數為: H ( k e y ) = R a n d o m ( k e y ) H(key)=Random(key) H(key)=Random(key),其中 R a n d o m Random Random為以 k e y key key為隨機數種子的偽隨機數
      • 此方法適合於:對長度不等的關鍵字構造哈希函數
    • 數字分析法
      • 分析所有關鍵字,從中提取分布均勻的若幹比特或它們的組合作為地址
      • 此法適用於能預先估計出全體關鍵字的每一比特上各種數字出現的頻度
    • 折疊法
      • 將關鍵字分割稱若幹部分,然後取它們的疊加和偽哈希地址
      • 兩種疊加處理方法
        • 移比特疊加:將分割後的及部分低比特對齊相加
        • 間界疊加:從一段沿分割界來回折送,然後對齊相加,適於數字維數多
    • 除留餘數法
      • 設定哈希函數 H ( k e y ) = k e y M O D p ( p ≤ m ) H(key)=keyMODp(p\leq m) H(key)=keyMODp(pm)
      • 其中, m m m為錶長, p p p為不大於 m m m的素數或是不含20以下的質因子
  • 選取哈希函數
    • 計算哈希函數所需時間
    • 關鍵字長度
    • 哈希錶長度
    • 關鍵字分布情况
    • 記錄的查找頻率
  • 沖突處理方法
    • 開放定址法
      • 為沖突的地址准備好一系列備選地址
      • 備選地址的計算公式 H i = ( H ( k e y ) + d i ) M O D m H_i=(H(key)+d_i)MOD m Hi=(H(key)+di)MODm
      • 其中 d i d_i di為增量序列,常見有三種取法
        • 線性探測再散列: d i = c × i , c = 1 d_i=c\times i,c=1 di=c×i,c=1
        • 平方探測再散列: d i = 1 2 , − 1 2 , 2 2 , − 2 2 . . . d_i=1^2,-1^2,2^2,-2^2... di=12,12,22,22...
        • 偽隨機探測再散列: d i d_i di是一組偽隨機數列
      • 平方探測時,錶長必為形如 4 j + 3 4j+3 4j+3的素數
      • 偽隨機探測時取决於偽隨機數列( m , d i m,d_i m,di沒有公因子)
    • 再哈希法
      • 當發生沖突時,計算下一個哈希地址,新的哈希函數計算
    • 鏈地址法
      • 將所有哈希地址相同的記錄都鏈接在同一鏈錶中
    • 建立一個公共溢出區
      • 在基本散列錶之外,另設一個溢出錶保存與基本錶中記錄沖突的所有記錄
      • 設散列錶長為 m m m,設立基本散列錶 h a s h t a b l e [ m ] hashtable[m] hashtable[m],每個分量保存一個記錄;溢出錶 o v e r t a b l e [ m ] overtable[m] overtable[m],一旦某個記錄的散列地址有沖突,都填入溢出錶中
  • 哈希錶的查找
    • 對於給定值 K K K,計算哈希地址 i = H ( K ) i=H(K) i=H(K)
      • r [ i ] = N U L L r[i]=NULL r[i]=NULL,則查找不成功
      • r [ i ] . k e y = K r[i].key=K r[i].key=K,則查找成功
    • 否則,求下一地址 H i H_i Hi,直至
      • r [ H i ] = N U L L r[H_i]=NULL r[Hi]=NULL,查找不成功
      • r [ H i ] . k e y = K r[H_i].key=K r[Hi].key=K,查找成功
    #define M 15
    typedef struct node
    {
    
    KeyType key;
    struct node* link;
    }HNode;
    HNode *hash_search(HNode *t[], KeyType k)
    {
    
    HNode *p;
    int i;
    i=h(k);
    if(t[i]==NULL)
    {
    
    return NULL;
    }
    p=t[i];
    while(p!=NULL)
    {
    
    if(EQ(p->key,k))
    {
    
    return p;
    }
    else
    {
    
    p=p->link;
    }
    }
    return NULL;
    }//查找散列錶HT中的關鍵字K,用鏈地址法解决沖突
    
    • 哈希錶查找的分析
      • 决定哈希查找ASL的因素
        • 選用的哈希函數
        • 選用的處理沖突的方法
        • 哈希錶飽和的程度:裝載因子 α = n m \alpha=\frac{n}{m} α=mn值得大小,其中 m , n m,n m,n分別錶示錶長和記錄個數, α \alpha α越小,沖突可能性越小
      • 一般情况下,認為選用的哈希函數時“均勻的”,討論ASL可不考慮
      • 當哈希錶得沖突處理方法相同時,ASL時裝載因子 α \alpha α的函數
        • 線性探測再散列的哈希查找: A S L ≈ 1 2 ( 1 + 1 1 − α ) ASL\approx \frac{1}{2}(1+\frac{1}{1-\alpha}) ASL21(1+1α1)
        • 平方探測再散列、隨機探測再散列和再哈希的哈希查找 A S L ≈ − 1 α l n ( 1 − α ) ASL\approx-\frac{1}{\alpha}ln(1-\alpha) ASLα1ln(1α)
        • 鏈地址法的哈希查找: A S L ≈ 1 + α 2 ASL\approx1+\frac{\alpha}{2} ASL1+2α
    • 哈希錶的平均查找長度是 α \alpha α的函數,不是 n n n的函數,在用哈希錶構造查找錶時,可選擇一個適當的裝填因子 α \alpha α,使得平均查找長度限定在某個範圍內
版权声明:本文为[鹹魚的學習]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080317520033.html