搜尋資料表(Search Table)

關鍵字(Key)：資料元素中某個資料項目的"值"；鍵欄(Key Field)：標示紀錄的某個"資料項目"

主關鍵字(Primary Key)：關鍵字標示的是唯一紀錄

次要索引鍵值(Secondary Key)：可以識別多個資料元素的關鍵字

靜態搜尋資料表 VS 動態搜尋資料表

• 循序結構搜尋

循序搜尋法(Sequential Search)：又稱線性搜尋

int Sequential_Search(int *a, int n, int key) {
    int i;
    for (i = 1; i <= n; i++) {
        if (a[i] == key)
            return i;
    }
    return 0;
}

// 循序搜尋最佳化
int Sequential_Search2(int *a, int n, int key) {
    int i;
    a[0] = key;
    i = n;
    while(a[i] != key)
        i--;
    return i;
}

• 有序結構搜尋

二分搜尋法(Binary Search)：

int Binary_search(int *a, int n, int key) {
    int low, mid, high;
    low = 1;
    high = n;
    while(low <= high) {
        mid = (low + high) / 2;
        if (key < a[mid])
            high = mid - 1;
        else if (key > a[mid])
            low = mid + 1;
        else
            return mid;
    }
    return 0;
}

內插搜尋法：

mid = low + (high - low) * ((key - a[low]) / (a[high] - a[low]));

費氏搜尋法(Fibonacci Search)：

int Fibonacci_Search(int *a, int n, int key) {
    int low, mid, high, i, k;
    low = 1;
    high = n;
    k = 0;
    while(n > F[k] - 1)
        k++;
    for (i = n; i < F[k] - 1; i++)
        a[i] = a[n];
    while(low <= high) {
        mid = low + F[k-1] - 1;
        if (key < a[mid]) {
            // Search from (low) to (mid - 1), num = F[k - 1] - 1
            high = mid - 1;
            k = k - 1;
        } else if (key > a[mid]) {
            // Search from (mid + 1) to (high), num = F[k - 2] - 1
            low = mid + 1;
            k = k - 2;
        } else {
            // Found
            if (mid <= n)
                return mid;
            else
                return n;
        }
    }
    return 0;
}

• 線性索引搜尋

直接索引：索引項目一定是按照鍵欄且有序的

分區索引：

• 區內無序：每一區內不要求有序

• 區間有序：例如第二區鍵值均大於第一區

反向索引：不是由紀錄來確定屬性值，而是由屬性值來確定紀錄的位置

• 二元搜尋樹(Binary Search Tree) (中序走訪)

* 若左子樹不為空，則左子樹上所有節點均小於根節點的值
* 若右子樹不為空，則右子樹上所有節點均大於根節點的值
* 左、右子樹也均為二元搜尋樹
* 不會有重複鍵值

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

// T: 二元搜尋樹, key: 尋找鍵值, f: T的雙親, p: 找到的節點或訪問的最後一個節點
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
    if (!T) {
        *p = f;
        return FALSE;
    } else if (key == T->data) {
        *p = T;
        return True;
    } else if (key < T->data)
        return SearchBST(T->lchild, key, T, p);
    else
        return SearchBST(T->rchild, key, T, p);
}

Status InsertBST(BiTree *T, int key) {
    BiTree p, s;
    if (!SearchBST(*T, key, NULL, &p)) {
        // 沒找到
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
            *T = s;
        else if (key < p->data)
            p->lchild = s;
        else
            p->rchild = s;
        return True;  
    } else
        return False;
}

Status DeleteBST(BiTree *T, int key) {
    if (!*T)
        return False;
    else {
        if (key == (*T)->data)
            return Delete(T);
        else if (key < (*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}

Status Delete(BiTree *p) {
    BiTree q, s;
    if ((*p)->rchild == NULL) {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    } else if ((*p)->lchild == NULL) {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    } else {
        q = *p;
        s = (*p)->lchild;
        while (s->rchild) {
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data;
        if (q != *p)
            q->rchild = s->lchild;
        else
            q->lchild = s->lchild;
        free(s);
    }
    return True;
}

• 平衡二元樹(AVL樹)

平衡二元樹是一種二元搜尋樹，但每個節點的左子樹和右子樹的高度差最多為1

平衡因子：左子樹高度 - 右子樹高度

typedef struct BiTNode {
    int data;
    int bf;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void R_Rotate(BiTree *P) {
    BiTree L;
    L = (*P)->lchild;
    (*P)->lchild = L->rchild;
    L->rchild = (*P);
    *P = L;
}

void L_Rotate(BiTree *P) {
    BiTree R;
    R = (*P)->rchild;
    (*P)->rchild = R->lchild;
    R->lchild = (*P);
    *P = R;
}

#define LH +1
#define EH 0
#define RH -1
void LeftBalance(BiTree *T) {
    BiTree L, Lr;
    L = (*T)->lchild;
    switch(L->bf) {
        case LH:
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:    // 新節點插在T的左孩子的右子樹上
            Lr = L->rchild;
            switch(Lr->bf) {
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
            break;

    }
}

Status InsertAVL(BiTree *T, int e, Status *taller) {
    if (!*T) {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    } else {
        if (e == (*T)->data) {
            *taller = FALSE;
            return FALSE;
        }
        if (e < (*T)->data) {
            // 左子樹
            if (!InsertAVL(&(*T)->lchild, e, taller))
                return FALSE;
            if (*taller) {
                switch ((*T)->bf) {
                    case LH:
                        LeftBalance(T);
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = TRUE;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                }
            }
        } else {
            // 右子樹
            if (!InsertAVL(&(*T)->rchild, e, taller))
                return FALSE;
            if (*taller) {
                switch ((*T)->bf) {
                    case LH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = TRUE;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = FALSE;
                        break;
                }
            }
        }
    }
    return TRUE;
}

• B樹索引(Multi-way Search Tree)

  • 2-3樹

  2節點包含一個元素和兩個或沒有孩子
  3節點包含一小一大兩個元素和三個或沒有孩子
  所有葉子都在同一層次
  
  插入(發生在葉子節點上)：
      1. 插在空樹 -> 直接插入一個2節點
      2. 插在2節點 -> 升級成3節點
      3. 插在3節點 -> 三者擇一往上移動一層
  刪除：
      1. 刪除3節點 -> 直接刪除
      2. 刪除2節點 -> 
          2-1. 雙親為2節點，且右孩子為3節點 -> 左旋
          2-2. 雙親為2節點，且右孩子為2節點 -> 移動再左旋
          2-3. 雙親為3節點 -> 把雙親變為2節點
          2-4. 完美二元樹木 -> 減少階數
      3. 刪除非葉子 ->
          3-1. 中序走訪得知前驅和後繼，由他們補位
      (還有很多...)
  

  • 2-3-4樹

  2節點包含一個元素和兩個或沒有孩子
  3節點包含一小一大兩個元素和三個或沒有孩子
  4節點包含小、中、大三個元素和四個或沒有孩子
  所有葉子都在同一層次
  

  • B樹

  節點最大的孩子數目稱為B樹的階，2-3樹是3階的B樹，2-3-4樹是4階的B樹
  m階的B樹有以下特性；
      如果根節點不是葉節點，則至少有兩棵子樹
      每一非根的分枝節點都有k-1個元素和k個孩子，其中高斯(m/2) <= k <= m
      每一葉子節點n都有k-1個元素，其中高斯(m/2) <= k <= m
      所有葉子節點都在同一層次
  

  • B+樹

  出現在分支節點中的元素，會被當作自己在該分支節點位置的中序後繼者，再次列出
  每個葉子節點都會保存指向後一個葉子節點的指標
  

• 雜湊表搜尋概述

1. 計算簡單
2. 雜湊位置分布均勻