天天看點
傳回

“查找”學習提綱（二）——樹型查找和散列查找前言代碼模闆二叉排序/查找/搜尋樹查找折半查找和二叉排序樹查找總結平衡二叉（排序）樹/AVL樹平衡二叉排序樹查找紅黑（二叉排序）樹紅黑二叉排序樹查找二叉排序樹查找、平衡二叉排序樹查找和紅黑二叉排序樹查找總結B樹/B-樹/平衡多路查找樹B樹查找B+樹B+樹查找其他特殊的多路查找樹散列/哈希表散列查找總結參考資料作者的話

文章目錄

  • 前言
  • 代碼模闆
  • 二叉排序/查找/搜尋樹查找
    • 适用
    • 性能
    • 代碼模闆
  • 折半查找和二叉排序樹查找總結
  • 平衡二叉（排序）樹/AVL樹
    • 構造相應層數的樹至少需要的結點數
    • 平衡調整的過程
    • 平衡調整的類型
  • 平衡二叉排序樹查找
    • 适用
    • 性能
  • 紅黑（二叉排序）樹
    • 相關概念
    • 紅黑調整的基本操作
    • 插入過程
    • 删除過程
    • 删除過程總結
  • 紅黑二叉排序樹查找
    • 适用
    • 性能
  • 二叉排序樹查找、平衡二叉排序樹查找和紅黑二叉排序樹查找總結
  • B樹/B-樹/平衡多路查找樹
    • 相關概念
    • 特性
    • 插入過程
    • 删除過程
  • B樹查找
    • 适用
    • 過程
    • 性能
  • B+樹
    • B+樹與B樹的差別
  • B+樹查找
    • 适用
    • 方式
    • 性能
  • 其他特殊的多路查找樹
  • 散列/哈希表
    • 相關概念
    • 散列函數的構造原則
    • 散列函數的構造方法
    • 沖突處理的方法
  • 散列查找
    • 适用
    • 性能
  • 總結
    • 樹型查找
    • 散列查找
  • 參考資料
  • 作者的話

前言

“查找”學習提綱（二）——樹型查找和散列查找。

代碼模闆

  • 二叉排序樹的C++語言描述實作模闆_夜悊的部落格-CSDN部落格

二叉排序/查找/搜尋樹查找

适用

  • 動态表->二叉排序樹

性能

時間複雜度：O(logn)~O(n)。n為資料規模

  • 時間複雜度：樹的深度/高度
  • O(logn)。n為資料規模（樹是平衡樹）
  • O(n)。n為資料規模（樹是斜樹）

空間複雜度：O(n)。n為資料規模

  • 空間複雜度：二叉排序樹的大小或遞歸調用棧的規模/樹的深度/高度：
  • O(1)。未使用額外輔助空間（不包括二叉排序樹的大小；疊代法）
  • O(logn)。n為資料規模（不包括二叉排序樹的大小；遞歸法，樹是平衡樹）
  • O(n)。n為資料規模（包括二叉排序樹的大小；遞歸法，樹是斜數）
插入和删除的時間複雜度：O(logn)。n為資料規模（平均情況）

代碼模闆 

//查找   前序周遊   遞歸法
//适用：
//動态表->二叉排序樹
//時間複雜度：O(logn)~O(n)。n為資料規模
//時間複雜度：樹的深度/高度
// O(logn)。n為資料規模（二叉排序樹是平衡樹）
// O(n)。n為資料規模（二叉排序樹是斜樹）
//空間複雜度：
//空間複雜度：二叉排序樹的大小或遞歸調用棧的規模/樹的深度/高度：
// O(1)。未使用額外輔助空間（不包括二叉排序樹的大小；疊代法）
// O(n)。n為資料規模（包括二叉排序樹的大小；遞歸法）
bool searchBSTree(struct BSTNode *root, ELEM_TYPE key) //參數：根結點指針，需插入的關鍵字    傳回值：查找成功為true，查找失敗為false
{
    if (root == nullptr) //空樹  無查找位置
    {
        return false; //查找失敗
    }
    else //非空樹   遞歸查找
    {
        if (key == root->key) //需插入的關鍵字等于根結點的關鍵字
        {
            return true; //查找成功
        }
        else if (key < root->key) //需插入的關鍵字小于根結點的關鍵字
        {
            return searchBSTree(root->lChild, key); //查找左子樹
        }
        else if (key > root->key) //需插入的關鍵字大于根結點的關鍵字
        {
            return searchBSTree(root->rChild, key); //查找右子樹
        }
    }

    return false;
}
           
//查找   前序周遊   疊代法
bool searchBSTree2(struct BSTNode *root, ELEM_TYPE key) //參數：根結點指針，需插入的關鍵字    傳回值：查找成功為true，查找失敗為false
{
    if (root == nullptr) //空樹  無查找位置
    {
        return false; //查找失敗
    }
    else //非空樹   疊代查找
    {
        while (root != nullptr)
        {
            if (key == root->key) //需插入的關鍵字等于根結點的關鍵字
            {
                return true; //查找成功
            }
            else if (key < root->key) //需插入的關鍵字小于根結點的關鍵字
            {
                root = root->lChild; //查找左子樹
            }
            else if (key > root->key) //需插入的關鍵字大于根結點的關鍵字
            {
                root = root->rChild; //查找右子樹
            }
        }
    }

    return false; //未查找成功傳回，則查找失敗
}
           
//删除
//對删除結點node：
// 1.是葉子節點：直接删除node
// 2.有一棵左子樹或右子樹：子樹作為node的雙親結點的子樹，删除node（子樹拼接）
// 3.有左右兩棵子樹：
//取node的左子樹的最大關鍵字結點或右子樹的最小關鍵字結點替換node，删除node->第1或2情況（取左最小或右最大替換）
//取中序周遊時，node的直接前驅結點或直接後繼結點替換node，删除node->第1或2情況（取直接前驅或直接後繼替換）

折半查找和二叉排序樹查找總結

  • 過程相似

折半查找：

  • 二叉判定樹唯一
  • 插入和删除的時間複雜度為O(n)。n為資料規模
  • 适用有序順序表

二叉排序樹查找：

  • 二叉排序樹不唯一（關鍵字相同，插入順序不同）
  • 插入和删除的時間複雜度為O(logn)。n為資料規模（平均情況）
  • 适用動态表

平衡二叉（排序）樹/AVL樹

注意：平衡二叉樹是特殊的二叉排序樹

構造相應層數的樹至少需要的結點數

由遞推公式：

  • 0層：0
  • 1層：1（根結點在第1層）
  • 2層：2
  • …
  • h層：構造h-2層的樹至少需要的結點數+構造h-1層的樹至少需要的結點數+1

平衡調整的過程

  1. 确定最小失衡/不平衡子樹：插入路徑上離插入結點最近的平衡因子的絕對值大于1的結點為根的子樹
  2. 調整子樹的平衡

平衡調整的類型

LL型：

  • 名稱：LL調整；右單旋轉調整
  • 現象：插入結點在最小不平衡樹根結點A的左（L）孩子B的左（L）子樹上
  • 狀态：左高右低
  • 思想：左上右下；右單旋轉
  • 過程：B作根，B的右子樹挂接到A的左子樹，A成B的右孩子

RR型：

  • 名稱：RR調整；左單旋轉調整
  • 現象：插入結點在最小不平衡樹根結點A的右（R）孩子B的右（R）子樹上
  • 狀态：左低右高
  • 思想：左下右上；左單旋轉
  • 過程：B作根，B的左子樹挂接到A的右子樹，A成B的左孩子

LR型：

  • 名稱：LR調整；先左後右雙旋轉調整
  • 現象：插入結點在最小不平衡樹根結點A的左（L）孩子B的右（R）子樹C上
  • 狀态：左低中高右低
  • 思想：左下中上右下
  • 過程：C作根，C的左子樹挂接到B的右子樹，B成C的左孩子，C的右子樹挂接到A的左子樹，A成C的右孩子

RL型：

  • 名稱：RL調整；先右後左雙旋轉調整
  • 現象：插入結點在最小不平衡樹根結點A的右（R）孩子B的左（L）子樹C上
  • 狀态：左低中高右低
  • 思想：左下中上右下
  • 過程：C作根，C的左子樹挂接到A的右子樹，A成C的左孩子，C的右子樹挂接到B的左子樹，B成C的右孩子

插入和删除的平衡調整：

  • 過程和類型相似
  • 删除導緻樹高變化，可能需要回溯調整

平衡二叉排序樹查找

适用

  • 動态表->平衡二叉排序樹

性能

平均查找長度（ASL）：

  • 平均查找長度（ASL）：樹的深度/高度
  • O(logn)。n為資料規模

時間複雜度： O(logn)。n為資料規模

  • 時間複雜度：樹的深度/高度
  • O(logn)。n為資料規模

空間複雜度：O(n)。n為資料規模

  • 空間複雜度：平衡二叉排序樹的大小或遞歸調用棧的規模/樹的深度/高度
  • O(1)。未使用額外輔助空間（不包括平衡二叉排序樹的大小；疊代法）
  • O(logn)。n為資料規模（不包括B樹的大小；遞歸法）
  • O(n)。n為資料規模（包括平衡二叉排序樹的大小）
插入和删除的時間複雜度：O(logn)。n為資料規模

紅黑（二叉排序）樹

注意：紅黑樹是特殊的二叉排序樹。大緻/非嚴格平衡

相關概念

性質：

  • 結點是紅色或黑色
  • 根結點是黑色
  • 葉子結點/外部結點/虛拟結點/空結點是黑色
  • 不存在兩個相鄰的紅色結點/紅色結點的雙親結點和孩子結點是黑色
  • 每個結點到任一葉子結點的簡單路徑，黑色結點的數量相同

其他：

  • 引入n+1個葉子結點/外部結點/虛拟結點/空結點，保證内部結點的左、右孩子結點非空。即：外部結點無資料，黑色；内部結點有資料，紅色或黑色
  • 結點的黑高：結點到任一葉子結點的簡單路徑，不包括該結點的黑色結點數量/黑色結點的數量-1（由性質5）
  • 結點的深度的差=結點到任一葉子結點的簡單路徑，紅色結點數量的差（由性質2和性質5）
  • 紅色結點數量影響樹的深度/高度（由性質2和性質5）

結論：

  • 根結點到葉子結點的最長路徑不大于最短路徑的兩倍（由性質4和性質5）
  • n個内部節點，樹的高度不大于2log以2為底的(n+1)（由結論1）

紅黑調整的基本操作

  • 旋轉：左旋轉和右旋轉
  • 着色：紅色和黑色

插入過程

插入操作可能破壞性質4

有：

  • 插入結點Z
  • 插入結點Z的雙親結點P
  • 插入結點Z的叔叔結點Y
  • 插入結點Z的爺爺結點PP
  1. Z塗紅色
  2. 補充Z的葉子結點
  3. 插入：轉分類讨論A

分類讨論A：判斷Z和P

  • Z是根結點：Z塗黑色
  • Z不是根結點，P是黑色：不操作
  • Z不是根結點，P是紅色：轉分類讨論B（Z和P破壞性質4）

分類讨論B：判斷Y、PP、P和Z

前提：Z是紅色，P是紅色，PP是黑色（插入前是合法的紅黑（二叉排序）樹，由性質2和4得）
  • Y是黑色，Z是PP的左孩子的左孩子（LL）：右旋轉，P塗黑色，PP塗紅色
  • Y是黑色，Z是PP的右孩子的右孩子（RR）：左旋轉，P塗黑色，PP塗紅色

LL型：P作根，P的右子樹挂接到PP的左子樹，PP成P的右孩子；紅紅黑->紅黑紅

RR型：P作根，P的左子樹挂接到PP的右子樹，PP成P的左孩子；黑紅紅->紅黑紅

  • Y是黑色，Z是PP的左孩子的右孩子（LR）：左旋轉，右旋轉，P塗黑色，PP塗紅色
  • Y是黑色，Z是PP的右孩子的左孩子（RL）：右旋轉，左旋轉，P塗黑色，PP塗紅色

LR型：Z的左子樹挂接到P的右子樹，Z成PP的左孩子，P成Z的左孩子，成LL型

RR型：Z的右子樹挂接到P的左子樹，Z成PP的右孩子，P成Z的右孩子，成RR型

  • Y是紅色：Y塗黑色，P塗黑色，PP塗紅色（局部恢複性質4），将PP作為插入結點，轉分類讨論A

删除過程

删除操作可能破壞性質2、4和5
  1. 轉二叉排序樹的删除操作
  2. 轉作雙色結點
  3. 轉雙色讨論

二叉排序樹的删除操作：對删除結點node

  • 是葉子節點：直接删除node
  • 有一棵左子樹或右子樹：子樹作為node的雙親結點的子樹，删除node（子樹拼接）
  • 有左右兩棵子樹：取node的左子樹的最大關鍵字結點或右子樹的最小關鍵字結點替換node，删除node->第1或2情況（取左最小或右最大替換）。或取中序周遊時，node的直接前驅結點或直接後繼結點替換node，删除node->第1或2情況（取直接前驅或直接後繼替換）

有：

  • 删除結點Z
  • 二叉排序樹的删除操作後，替換删除結點Z的替換結點X
  • X的雙親結點P
  • X的兄弟結點W
  • W的左孩子結點WL
  • W的右孩子結點WR
  • X是P的左孩子，W是P的右孩子

作雙色結點：

  • 假設替換結點X有兩種顔色：原來的顔色（紅色或黑色）和增加的黑色
從Z繼承增加的黑色：因為若Z是紅色，删除Z不會破壞性質；若Z是黑色，删除會破壞性質
假設替換結點X有兩種顔色的目的：恢複性質5，破壞性質1
後續操作的核心：恢複雙色結點為單色結點/性質1

雙色讨論：

  • X是紅色和黑色：删除紅色，保留黑色
  • X是黑色和黑色，X是根結點：不操作
  • X是黑色和黑色，X不是根結點，轉分類讨論A

分類讨論A：

  • 轉W是紅色
  • 轉W是黑色

W是紅色：

  • 由性質4：W是紅色，則P、WL和WR是黑色
  • 處理：P塗紅色，W塗黑色（P和W交換顔色）。X是P的左孩子，則P/W左旋轉（調整P到X一側）。轉W是黑色

W是黑色：

  • WL是紅色，WR是黑色：轉WL是紅色，WR是黑色
  • WL是紅色或黑色，WR是紅色：轉WL是紅色或黑色，WR是紅色
  • WL是黑色，WR是黑色：轉WL是黑色，WR是黑色

WL是紅色，WR是黑色：

  • RL型：紅色結點WL是爺爺結點的右孩子W的左孩子
  • RL型：W塗紅色，WL塗黑色（W和WL交換顔色）。WL右旋（調整W為WL的右孩子）。轉WL是紅色或黑色，WR是紅色

WL是紅色或黑色，WR是紅色：

  • W塗P的顔色，P塗黑色（W和P交換顔色），WR塗黑色（保持W一側的黑高）。X是P的左孩子，P/W左旋轉（補充一黑色結點P到X一側）。結束

WL是黑色，WR是黑色：

  • X和W各提取一重黑色：X是黑色，W是紅色
  • 由性質5，需要補償該一重黑色：P有兩種顔色：原來的顔色（紅色或黑色）和增加的黑色
  • 将P作為替換結點X，轉雙色讨論

删除過程總結

一、二叉排序樹的删除操作：保持二叉排序樹的性質

二、作雙色結點：恢複性質5，破壞性質1

三、雙色讨論：恢複性質1。轉123

1 若X紅色+黑色：删除紅色，保留黑色

2 若X黑色+黑色，是根結點：不操作

3 若X黑色+黑色，不是根結點：性質5真正被破壞。轉(1)(2)

(1) 若W紅色：W塗黑色，P塗紅色，W左旋。轉(2)

由性質4：W紅色，P、WL和WR黑色

W塗黑色，W左旋：W成根替換P的位置，保持黑高

P塗紅色，W左旋：P成W的左孩子，保持黑高

W左旋：W的WL子樹挂接到P的右子樹，WL成X的兄弟

目的：轉換X的兄弟為黑色

(2) 若W黑色

① WL紅色，WR黑色：WL塗黑色，W塗紅色，WL右旋。轉②

由性質4：WL紅色，P黑色

WL塗黑色，WL右旋：WL成根替換W的位置，保持黑高

P塗紅色，W右旋：W成WL的右孩子，保持黑高

WL右旋：WL的右子樹挂接到W的左子樹，WL成X的兄弟

先：RL型。後：RR型

目的：轉換W的右孩子為紅色

② WR紅色：W塗紅色，P塗黑色，WR塗黑色，W左旋

由性質4：WR紅色，W黑色

W塗紅色，W左旋：W成根替換P的位置，原W側的黑高-1，破壞性質5

P塗黑色，W左旋：P成W的左孩子，X側的黑高+1，X恢複單色，恢複性質1

W左旋：W的左子樹挂接到P的右子樹，WR成X的兄弟

WR塗黑色：原W側的黑高+1，恢複性質5

目的：調整一黑色結點到X側

③ WL黑色，WR黑色：W塗紅色，P作雙色結點。轉二

X恢複單色，W塗紅色：各提取一重黑色

P作雙色結點：從X和W提取的黑色增加到P，保持黑高。P替換為X繼續處理

注意：X是P的右孩子，W是P的左孩子時，(1)(2)①②③有對稱情況

總結(1)(2)①②③：

關于黑色提取：

(2)③：有重複黑色可提取，調整操作向上委托的同時能夠保持黑高

(1)：W紅色，不能提取黑色

(2)①：WL紅色，WR黑色，由性質4，W黑色。若W提取黑色，W成紅色，則W->WL和W->WR的黑高不同，破壞性質5

(2)②：WR紅色，由性質4，W黑色。若W提取黑色，W成紅色，則W和WR紅色，破壞性質4

關于目的：

(1)：轉換為(2)

(2)①：轉換為(2)②

(2)②：調整結束

(2)③：調整操作向上委托

關于執行情況：

(2)③：唯一可重複執行的情況，每執行一次委托向上一層，最多次數是樹的深度/高度，為logn

有流程：(1)->(2)③，結束

最少流程：(2)②，結束

最多流程：(1)->(2)①->(2)②，結束

最多流程時，執行常數次的着色操作和至多三次的旋轉操作

紅黑二叉排序樹查找

适用

  • 動态表->紅黑二叉排序樹

性能

時間複雜度：O(logn)。n為資料規模

  • 時間複雜度：樹的深度/高度
  • O(logn)。n為資料規模

空間複雜度：O(n)。n為資料規模

  • 空間複雜度：紅黑二叉排序樹的大小或遞歸調用棧的規模/樹的深度/高度
  • O(1)。未使用額外輔助空間（不包括紅黑二叉排序樹的大小；疊代法）
  • O(logn)。n為資料規模（不包括紅黑二叉排序樹樹的大小；遞歸法）
  • O(n)。n為資料規模（包括紅黑二叉排序樹的大小）
插入和删除的時間複雜度：O(logn)。n為資料規模

二叉排序樹查找、平衡二叉排序樹查找和紅黑二叉排序樹查找總結

  • 平衡二叉排序樹查找和紅黑二叉排序樹查找的一般性能優于二叉排序樹查找
  • 若插入和删除操作相對少，查找操作相對多，适用平衡二叉排序樹查找
  • 若插入和删除操作相對多，查找操作相對少，适用紅黑二叉排序樹查找

B樹/B-樹/平衡多路查找樹

注意：-無意義，不念做B減樹，念做B樹
B樹是平衡多路查找樹，但限制更強：葉子結點在同一層

相關概念

  • 樹的階/度m：結點的分支數的最大值
  • 樹的深度/高度/外存存取次數h（一般不包括葉子結點層）：log以m為底的(n+1) <= h <= log以[m/2]上取整為底的[(n+1)/2]+1。n為關鍵字數

特性

  • 若結點有n個子樹，則有n-1個關鍵字
  • 若根結點不是葉子結點，則至少有2個子樹。若結點是非根非葉子結點，則至少有[m/2]上取整個子樹。結點至多有m個子樹
  • 非葉子結點的結構：（n,P0,K1,P1,K2,P2…Kn,Pn）。Ki（i=1,2,…,n）為結點的關鍵字，K1<K2<…Kn。Pi（i=0,1,…,n）為子樹根結點指針，P(i-1)所指子樹中所有結點的關鍵字<Ki，Pi所指子樹中所有結點的關鍵字>Ki。n為結點的關鍵字數
  • 葉子結點在同一層，為外部結點/虛拟結點/空結點，不包含資訊

其他：

  • 若有n個關鍵字，則有n+1個葉子結點（葉子結點對應查找失敗的情況）

插入過程

  1. 确定結點中關鍵字數的範圍：n為關鍵字數，有[m/2]上取整-1 <= n <= m-1
  2. 查找插入位置：若無插入位置，插入失敗；若有插入位置，插入
  3. 檢查結點中關鍵字數：若n <= m-1，插入完成；若n > m-1，結點拆分

注意：

查找時，查找到葉子結點，表明有插入位置

插入時，插入到相應的最底層的非葉子結點

結點拆分：

  • 結點中關鍵字數：n = m > m-1
  • 取第[m/2]上取整個關鍵字K
  • K的左指針指向第1~[m/2]上取整-1個關鍵字
  • K的右指針指向第[m/2]上取整+1~m個關鍵字
  • K插入雙親結點的相應位置中
  • 檢查雙親結點中關鍵字數：若n <= m-1，插入完成；若n > m-1，結點拆分

删除過程

  1. 确定結點中關鍵字數的範圍：n為關鍵字數，有[m/2]上取整-1 <= n <= m-1
  2. 查找删除位置：若無删除位置，删除失敗；若有删除位置，檢查結點中關鍵字數
  3. 檢查結點中關鍵字數：删除讨論1和2

注意：

查找時，查找到非葉子結點，表明有删除位置

删除時，在相應的的非葉子結點上删除

删除讨論1：删除的關鍵字不在最底層的非葉子結點上

  • 轉換：删除的關鍵字在最底層的非葉子結點上
  • 類比二叉排序樹的删除操作：在中序周遊中，查找删除結點的左子樹的最大值或右子樹的最小值結點/直接前驅或直接後繼結點
  • 關鍵字交換：取删除關鍵字X的相鄰關鍵字Y，Y替換X（X不在最底層的非葉子結點上），删除Y（Y在最底層的非葉子結點上）

删除讨論2：删除的關鍵字在最底層的非葉子結點上

  • 若n > [m/2]上取整-1：直接删除
  • 若n = [m/2]上取整-1，删除關鍵字結點的左兄弟結點或右兄弟結點的關鍵字 > [m/2]上取整-1：關鍵字借位ie。關鍵字流向：兄弟結點->雙親結點->目前結點
  • 若n = [m/2]上取整-1，删除關鍵字結點的左兄弟結點和右兄弟結點的關鍵字 = [m/2]上取整-1：結點合并。關鍵字流向：目前結點+雙親結點+兄弟結點；注意：可能導緻雙親結點的關鍵字數不合法

删除讨論總結：

  • 直接删除
  • 關鍵字交換
  • 關鍵字借位
  • 結點合并

B樹查找

适用

  • 動态表->B樹

過程

類似二叉排序樹查找
  1. 在B樹中查找結點（在外存進行）
  2. 在結點中查找關鍵字（在記憶體進行）。可使用線性查找

性能

時間複雜度：O(logn)。n為資料規模

  • 時間複雜度：樹的深度/高度
  • O(logn)。n為資料規模

空間複雜度：O(n)。n為資料規模

  • 空間複雜度：B樹的大小或遞歸調用棧的規模/樹的深度/高度
  • O(1)。未使用額外輔助空間（不包括B樹的大小；疊代法）
  • O(logn)。n為資料規模（不包括B樹的大小；遞歸法）
  • O(n)。n為資料規模（包括B樹的大小）

B+樹

B+樹與B樹的差別

  • 若結點有n個子樹，則有n個關鍵字
  • 根結點關鍵字數n的取值範圍：2 <= n <= m；除根結點關鍵字數n的取值範圍：[m/2]上取整 <= n <= m
  • 葉子結點包含資訊：全部關鍵字和全部記錄指針
  • 非葉子結點隻起索引作用，索引項：有子樹的最大關鍵字和子樹指針，無最大關鍵字對應記錄的存儲位址
  • 有一個指針指向最小關鍵字的葉子結點，所有葉子結點連結成線性連結清單

B+樹查找

适用

  • 動态表->B+樹

方式

  • 從根結點開始：樹型查找
  • 從最小關鍵字葉子結點開始：線性查找

性能

時間複雜度：O(logn) | O(mlogn) | O(logmlogn)。n為資料規模，m為樹的階

時間複雜度：查找結點時間（樹型查找）×查找結點中關鍵字時間（線性查找）

  • 查找結點時間：O(logn)。n為資料規模（樹的深度/高度）
  • 查找結點中關鍵字時間：O(m)。m為樹的階（順序查找）
  • 查找結點中關鍵字時間：O(logm)。m為樹的階（折半查找等）

時間複雜度：通路外存的輸入/輸出（I/O）次數

  • 一次通路外存的輸入/輸出（I/O）讀取一頁
  • 頁大小 = 非葉子結點大小
  • 通路外存的輸入/輸出（I/O）次數 = 樹的深度/高度：O(logn)。n為資料規模

空間複雜度：O(n)。n為資料規模

  • 空間複雜度：B+樹的大小或遞歸調用棧的規模/樹的深度/高度
  • O(1)。未使用額外輔助空間（不包括B+樹的大小；疊代法）
  • O(logn)。n為資料規模（不包括B+樹的大小；遞歸法）
  • O(n)。n為資料規模（包括B+樹的大小）

其他特殊的多路查找樹

  • 2-3樹：3階B樹
  • 2-3-4樹：4階B樹

散列/哈希表

相關概念

  • 查找表：存儲記錄/關鍵字
  • 散清單：類比索引表和映射表，存儲關鍵字和散清單位址的映射關系
  • 映射：h(key) = addr。key為關鍵字，h()為散列函數 ，addr為散清單位址
  • 沖突/碰撞：兩個或兩個以上的不同關鍵字，通過散列函數，映射到散清單相同位址
  • 同義詞：對某個散列函數，能夠發生沖突的不同關鍵字
  • 裝填因子：散清單的裝填程度。α = n/m。α為裝填因子，n為散清單中的記錄數，m為散清單的大小
注意：散清單的平均查找長度（ASL）與α有關，與n和m無關

散列函數的構造原則

  • 定義域包含查找表的所有關鍵字，值域取決于散清單的大小/位址範圍
  • 簡單：能夠在較短時間計算出結果
  • 盡量避免沖突：計算的散清單位址能等機率和均勻地分布在散清單中（了解）

另：

  • 散清單的大小
  • 關鍵字的大小/長度/位數
  • 關鍵字的分布
  • 計算散清單位址的時間
  • 關鍵字查找的頻率

散列函數的構造方法

直接定址法：

  • 方法：h(key) = key或h(key) = a × key + b(a和b為常數)
  • 特點：簡單，均勻（關鍵字映射的散清單位址在散清單中分布均勻），不會産生沖突
  • 适用：查找表的規模比較小；關鍵字的分布基本連續

除留餘數法：

  • 方法：h(key) = key % p(m為散清單的大小，p為質數，有p <= m。一般取p為小于或等于散清單的大小的最大質數或不包含小于20質因子的合數，能夠盡量避免沖突：若p > m，則取餘的散清單位址可能越界；質數的取餘運算可以使散清單位址盡量均勻)

平方取中法：

  • 方法：h(key) = key²的中間幾位數
  • 适用：未知關鍵字的分布；關鍵字的位數比較少，可能小于散清單位址需要的位數；關鍵字的每位取值比較不均勻

數字分析法：

  • 方法：取關鍵字的若幹數位，可進行旋轉、反轉和疊加等操作
  • 适用：關鍵字的位數比較多；關鍵字若幹數位的取值比較均勻

折疊法：

  • 方法：關鍵字從左到右分割成位數相等的幾部分（最後一部分位數不夠可短些），各部分求和，依據散清單的大小，取和的後幾位
  • 适用：未知關鍵字的分布；關鍵字位數比較多

随機數法：

  • 方法：h(key) = random(key)。random()為随機函數。即關鍵字的随機函數值為散清單位址
  • 适用：各關鍵字的位數不相等
注意：關鍵字不是數字，是符号，可通過ASCII碼、Unicode碼等轉換為數字

沖突處理的方法

開放定址法：

  • 含義：空閑散清單位址向同義詞開放，也向非同義詞開放
  • 了解：同義詞通過散列函數映射到散清單位址A（固有的），非同義詞通過散列函數映射到散清單位址B（固有的），在B發生沖突，通過沖突處理能夠映射到A（變化的）
  • 發生沖突的散清單位址作自變量，通過沖突處理函數，映射到新的散清單位址
  • 數學遞推公式：hi = (h(key) + di) % m。m為散清單的大小，i為發生沖突的次數/新散清單位址的計數值，0 <= i <= m，di為增量序列，key為關鍵字，h()為散列函數，h(key)為散清單位址，hi為新散清單位址
  • 數學遞推公式中，确定di->确定沖突處理方法
  • 有線性探測法，平方探測法，雙散列法，僞随機序列法
  • 注意：對散清單，不能實體删除關鍵字/關鍵字-散清單位址映射（因為會截斷其他該散清單位址的關鍵字的探測位址）。能邏輯删除關鍵字/關鍵字-散清單位址映射（使用标記；需要定期維護散清單避免未利用表項過多）

線性探測法：

  • 方法：di = 0,1,…,m-1
  • 缺點：易出現聚集/堆積問題（同義詞和非同義詞映射到相同的散清單位址）

平方探測法/二次探測法：

  • 方法：di = 0²,1²,-1²,…,k²,-k²。k <= m/2，m為可表示成4×k+3的質數
  • 缺點：不能探測到所有散清單位址，至少能探測到一半的散清單位址

雙散列法：

  • 方法：di = i × h2(key)
  • 特點：最多m-1次探測回到第一次發生沖突的位置/原散清單位址

僞随機序列法：

  • 方法：di = 僞随機數
  • 僞随機數：随機種子相同，每過程（沖突處理過程和查找過程）生成的僞随機數數列相同，數列中的僞随機數互不相同

鍊位址法/拉鍊法/連結法：

  • 方法：同義詞連結成單連結清單/同義詞子表，散清單的散清單位址表項不存儲關鍵字，存儲單連結清單頭指針
  • 優點：散清單不會滿
  • 缺點：增加周遊單連結清單的時間

再散列函數法：

  • 方法：每沖突時，更換散列函數再計算
  • 優點：不易出現聚集/堆積問題
  • 缺點：增加散列函數再計算時間

公共溢出區法：

  • 方法：每沖突時，将關鍵字順序存儲到另一溢出表中
  • 适用：沖突少->溢出表相對散清單的規模小

散列查找

适用

  • 查找性能要求高，記錄關系無要求

性能

影響因素：

  • 散列函數
  • 沖突處理方法
  • 裝填因子

平均查找長度（ASL）/平均比較次數：

  • 查找成功：依據關鍵字計算：每關鍵字的比較次數的和/關鍵字數。每關鍵字的比較次數的和：（計算散清單位址）無沖突比較1次，有1次沖突（計算新散清單位址）比較2次，以此類推
  • 查找失敗：依據散清單位址計算：每可以映射到的散清單位址上，比較到空散清單位址（比較空散清單位址算作比較1次）比較次數的和/可以映射到的散清單位址數

時間複雜度：O(1)

空間複雜度：O(m)。m為散清單的大小

總結

樹型查找

名稱 适用 時間複雜度 空間複雜度
二叉排序樹查找 動态表->二叉排序樹 O(logn)~O(n) O(n)
平衡二叉排序樹查找 動态表->平衡二叉排序樹 O(logn) O(n)
紅黑二叉排序樹查找 動态表->紅黑二叉排序樹 O(logn) O(n)
B樹查找 動态表->B樹 O(logn) O(n)
B+樹查找 動态表->B+樹 O(logn) | O(mlogn) | O(logmlogn) O(n)

散列查找

名稱 适用 時間複雜度 空間複雜度
散列查找 查找性能要求高，記錄關系無要求 O(1) O(m)

參考資料

  • 《2023版資料結構高分筆記》主編：率輝
  • 《2023年計算機組成原理考研複習指導》組編：王道論壇
  • 《大話資料結構》作者：程傑
  • B+ 樹搜尋時間複雜度到底是什麼：mlogmN / logN？ - 知乎 (zhihu.com)

作者的話

  • 感謝參考資料的作者/部落客
  • 作者：夜悊
  • 版權所有，轉載請注明出處，謝謝~
  • 如果文章對你有幫助，請點個贊或加個粉絲吧，你的支援就是作者的動力~
  • 文章在描述時有疑惑的地方，請留言，定會一一耐心讨論、解答
  • 文章在認識上有錯誤的地方, 敬請批評指正
  • 望讀者們都能有所收獲
資料結構 算法 B樹 散清單 c++
上一篇: 劍指offer題解（C語言）----JZ08 二叉樹的下一個結點
下一篇: 二叉樹中序線索化與周遊（c）

繼續閱讀