查找概論：
查找表（Search Table）是由同一類型的資料元素（或記錄）構成的集合。
關鍵字（Key）是資料元素中某個資料項的值，又稱為鍵值，用它可以辨別一個資料元素。
若此關鍵字可以唯一地辨別一個記錄，則稱此關鍵字為主關鍵字（Primay Key）。
對于那些可以識别多個資料元素（或記錄）的關鍵字，我們稱為次關鍵字（Secondary Key ）。
查找： 查找(Searching)就是根據給定的某個值，在查找表中确定一個其關鍵字等于給定值得資料元素（或記錄）
查找表按照操作方式來分有兩種：靜态查找表和動态查找表
靜态查找表（Static Search Table）:隻作查找操作的查找表。它的主要操作有：
(1)查詢某個“特定的”資料元素是否存在查找表中。
(2)檢索某個“特定的”資料元素和各種屬性。
動态查找表（Dynamic Search Table）：在查找過程中同時插入查找表中不存在的資料元素，或者從查找表中删除已經存在的某個資料元素。動态查找表的操作是兩個：
(1)查找時插入資料元素。
(2)查找時删除資料元素。
順序表查找：
針對線性表進行查找操作，是以它就是靜态查找表。
順序查找（Sequential Search）又叫線性查找，是最基本的查找技術，它的查找過程是：從表中的第一個（或最後一個）記錄開始，逐個進行記錄的關鍵字和給定值比較，若某個記錄的關鍵字和給定值相等，則查找成功，找到所查找的記錄；如果直到最後一個記錄（或第一個）記錄，其關鍵字和給定的值都不等時，則表中沒有所查找的記錄，則查找不成功。
順序表查找算法：
/*順序查找，a為數組，n為要查找的數組長度，key為要查找的關鍵字*/
int Sequential_Search(int *a,int n,key)
{
int i;
for(i = 1;i<=n;i++)
{
if(a[i-1]==key)/*因為數組一般是從0開始的，具體可以根據實際情況來定,例如如果要從1開始的話，就可以直接這樣寫
if(a[i]==key)，從1開始的數組在下面的優化中是有用處的，實際上來說，當然設定在末尾也是可以的，但是要進行一些修改*/
return i;
}
return 0;
}
順序表查找優化：
因為我們每次循環都需要對i是否越界的進行判定，那麼我們可以改變一下思路，設定一個哨兵
/*有哨兵順序查找*/
int Sequential_Search_Better(int *a,int n,int key)
{
int i;
a[0] = key;//設定a[0]為關鍵字值，我們稱之為“哨兵”
i = n;
while(a[i]!=key)
{
i--;
}
return i;//傳回0說明查找失敗
}
時間複雜度O(n).
缺點：n很大時，查找效率低下。
有序表查找：
折半查找(Binary Search)技術，又稱為二分查找。它的前提是線性表中的記錄必須是關鍵碼有序(通常是從小到大有序)，線性表必須采用順序存儲。折半查找的基本思想是：在有序表中，取中間記錄作為比較對象，若給定與中間值的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區域繼續查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區域繼續查找。不斷重複上述過程，知道查找成功，或所有查找區域無記錄，查找失敗為止。
以下是折半查找算法的代碼實作：
/*折半查找*/
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
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;
}
時間複雜度：O(logn)
插值查找：
在折半查找中把
mid = (low+high)/2;//折半
改成
mid = low + (high-low)*(key-a[low])/(a[high]-a[low]);//插值
就可以得到另一種有序表查找算法---》插值查找法。
插值查找(Interpolation Search)是根據要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找算法，其核心就在于插值的計算公式：(key-a[low])/(a[high]-a[low])。
其時間複雜度也是O(logn),但是對于表長較大，而且關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數組中如果分布類似{0,1,2,2000,2001,……,999998,999999}這種極端不均勻的資料，用插值就未必是一個好的選擇了。
斐波那契查找(Fibonacci Search)：
利用了黃金分割原理來實作的。
以下是斐波那契查找算法的實作代碼：
/*斐波那契查找*/
int Fibonacci_Search(int *a,int n,int key)
{
int low,high,mid,i,k;
low = 1;//定義最低下标為記錄首位
high = n;//定義最高下标為記錄末位
k = 0;
while(n>F[k]-1)//計算n位于斐波那契數列的位置
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])//若查找記錄小于目前分隔記錄
{
high=mid-1;//最高下标調整到分隔下标mid-1處
k = k-1;
}
else if(key>a[mid])//若查找記錄大于目前分隔記錄
{
low=mid+1;//最低下标調整到分隔下标的mid+1處
k = k-2;//斐波那契數列下标減兩位
}
else
{
if(mid<=n)
return mid;//若相等則說明mid即為查找到的位置
else
return n;//若mid>n說明是補全數值，傳回n
}
}
return 0;
}
斐波那契算法的核心在于：
1.當key=a[mid]時，就查找成功；
2.當key<a[mid]時，新範圍是第low個到第mid-1個，此時範圍個數為F[k-1]-1個；
3.當key>a[mid]時，新範圍是第m+1個到第high個，此時範圍個數為F[k-2]-1個。
也就是說，如果要查找的記錄在右側，則左側的資料都不用再判斷了，不斷反複進行下去，處于當中的大部分資料，其工作效率要高一些。是以盡管斐波那契查找的時間複雜度也為O(logn),但就平均性能來說，還是要優于折半查找的。可惜如果是最壞情況，比如這裡的key=1，那麼始終都處于左側長半區在查找，則查找效率要低于折半查找。
還有比較關鍵一點，折半查找是進行加法與除法運算(mid=(low+high)/2)，插值查找進行複雜的四則運算(mid=low+(high-low)*(key-a[low])/(a[high]-a[low])),而斐波那契查找隻是最簡單的加減法運算(mid=low+F[k-1]-1),在海量資料的查找過程中，這種細微的差别可能會影響最終的查找效率。
線索索引查找:
資料結構的最終目的是提高資料的處理速度，索引是為了加快查找速度而設計的一種資料結構。---》》》索引就是把一個關鍵字與它對應的記錄相關聯的過程；；；一個索引由若幹個索引項構成，每個索引項至少至少應該包含關鍵字和其對應的記錄在存儲器中的位置等資訊。
索引技術是組織大型資料庫及磁盤檔案的一種重要的技術。
索引按照結構可以分為：
線索索引、樹形索引和多級索引。
以下隻介紹線索索引：
所謂線索索引就是講索引項集合組織為線性結構，也稱為索引表。
以下會重點介紹三種線性索引：
稠密索引、分塊索引和反向索引
稠密索引：
稠密索引是指線上性索引中，将資料集中的每個記錄對應一個索引項。
對于稠密索引這個索引表來說，索引項一定是按照關鍵碼有序的排序。
索引項有序也就意味着我們要查找關鍵字時，可以使用折半、插值、斐波那契等有序查找算法，大大提高了效率。這顯然是稠密索引的優點，但是如果資料集非常大，那也就意味着索引也得同樣的資料集長度規模，對于記憶體有限的計算機來說，可能就需要反複去通路磁盤，查找性能反而大大下降了。
分塊索引：
稠密索引因為索引項與資料集的記錄個數相同，是以空間代價很大。為了減少索引項的個數，我們可以對資料集進行分塊，使其分塊有序，然後再對每一塊建立一個索引項，進而減少索引項的個數。
分塊有序，是把資料集的記錄分成了若幹塊，并且這些塊需要滿足兩個條件：
(1)塊内無序，即每一塊内的記錄不要求有序。
(2)塊間有序，例如，要求第二塊所有記錄的關鍵字均要大于第一塊中所有記錄的關鍵字，第三塊的所有記錄的關鍵字均要大于第二塊的所有記錄關鍵字……因為隻有塊間有序，才有可能在查找時帶來效率。
對于分塊有序的資料集，将每塊對應一個索引項，這種索引叫做分塊索引。
如下圖所示：
我們定義的分塊索引的索引項結構分為三個資料項：
》最大關鍵碼，它存儲每一塊中的最大關鍵字，這樣的好處就是可以使得在它之後的下一塊重的最小關鍵字也能比這一塊最大的關鍵字要大。
》存儲了塊中的記錄個數，以便于循環時使用。
》用于指向塊首資料元素的指針，便于開始對這一塊中記錄進行周遊。
在分塊索引表中查找，就是分兩步進行：
1.在分塊索引表中查找要查關鍵字所在的塊。由于分塊索引表是塊間有序的，是以很容易利用折半、插值等算法得到結果。
2.根據塊首指針找到相應的塊，并在塊中順序查找關鍵碼。因為塊中可以是無序的，是以隻能順序查找。
分塊索引的效率比順序查找的O(n)是高了不少，但是顯然它與折半查找的O(logn)相比還有不少的差距。是以在确定所在塊的過程中，由于塊間有序，是以可以應用折半、插值等手段來提高效率。
總的來說，分塊索引在兼顧了對細分塊不需要有序的情況下，大大增加了整體查找的速度，是以普遍被用于資料庫表查找等技術的應用中。
反向索引：
索引項的通用結構是：
次關鍵碼
記錄号表
其中，記錄号表存儲具有相同次關鍵字的所有記錄的記錄号(可以使指向記錄的指針或者是該記錄的主關鍵字)。這樣的索引方法就是反向索引(inverted index).
反向索引源于實際應用中需要根據屬性（或字段、次關鍵碼）的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的位址。由于不是由記錄來确定屬性值，而是由屬性值來确定記錄的位置，因而成為反向索引。
反向索引的優點：查找速度非常快，基本等于生成索引後，查找時都不用去讀取記錄，就可以得到結果。
反向索引的缺點：記錄号不是定長的，若是對多篇文章所有單詞建立反向索引，每個單詞都将對應相當多的文章編号，維護比較困難，插入和删除操作都需要作相應的處理。
二叉排序樹：
二叉排序樹(Binary Sort Tree)，又稱為二叉查找樹。它或者是一顆空樹，或者是具有下列性質的二叉樹。
若它的左子樹不為空，則左子樹的所有節點均小于它的根結構的值；
若它的右子樹不為空，則右子樹的所有節點均大于它的根結構的值；
它的左、右子樹也分别為二叉排序樹。
從二叉排序樹的定義可以知道，它氣體是二叉樹，然後它采用了遞歸的定義方法，再者，它的結點間滿足一定的次序關系，左子樹結點一定比其雙親結點小，右子樹結點一定比其雙親結點大。
構造一棵二叉排序樹的目的，其實并不是為了排序，而是為了提高查找和插入删除關鍵字的速度。不管怎麼說，在一個有序資料集上的查找，速度總是要快于無序的資料集的，而二叉排序樹這種非線性的結構，也有利與插入和删除的實作。
二叉排序樹查找操作：
首先提供一個二叉樹的資料結構：
/*二叉樹的二叉連結清單結點結構定義*/
typedef struct BiTNode //結點結構
{
int data;//結點資料
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
然後以下是二叉排序樹的查找實作：
/*遞歸查找二叉排序樹T中是否存在key，指針f指向T的雙親，其初始調用值為NULL;
若查找成功，則指針p指向該資料元素結點，并傳回TRUE;
否則指針p指向查找路徑上通路的最後一個結點并傳回FALSE*/
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);//在右子樹繼續查找
}
二叉排序樹插入操作：
/*當二叉排序樹T中不存在關鍵字等于key的資料元素是，
插入key并傳回TRUE，否則傳回FALSE*/
Status InsertBST(BiTree *T,int key)
{
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p))//查找不成功
{
s = (BiTree)malloc(sizeof(BiTree));
s->data=key;
s->lchild = s->rchild = NULL;
if(!p)
*T = s;//插入s為新的根結點
else if (key<p->data)
p->lchild = s;//插入s為左孩子
else
p->rchild = s;//插入s為右孩子
return TRUE;
}
else
return FALSE;//樹中已存在關鍵字
}
建構二叉排序樹的程式代碼：
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93}
BiTree T = NULL;
for(i=0;i<10;i++)
{
InsertBST(&T,a[i]);
}
二叉排序樹删除操作：
删除結點的三種情況：
(1)葉子結點
(2)僅有左或右子樹的結點
(3)左右子樹都有的結點，我們來看代碼，下面這個算法是遞歸方式對二叉排序樹T查找key,查找到時删除
實作代碼
/*若二叉排序樹T中存在關鍵字等于key的資料元素時，則删除該資料元素結點，并傳回TRUE；否則傳回FALSE */
Status DeleteBST(BiTree *T,int key)
{
if(!*T)//不存在關鍵字等于key的資料元素
return FALSE;
else
{
if(key==(*T)->data//找到關鍵字等于key的資料元素
return Delete(T);
else if(key<(*T)->data)
return DeleteBST(&(*T)->lchild,key);
else
return DeleteBST(&(*T)->rchild,key);
}
}
這段飯嗎和前面的二叉排序查找幾乎完全相同個，唯一的差別就在于
return Delete(T);
這行，此時執行的是Delete方法，對目前結點進行删除操作。
以下是Delete代碼：
/*從二叉排序樹中删除結點p，并重接它的左或右子樹.*/
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;//s指向被删結點的直接前驅
if(q!=*p)
q->rchild=s->lchild;//重接q的右子樹
else
q->lchild=s->lchild;//重接q的左子樹
free(s);
}
return TRUE;
}
總之，二叉排序樹是以連結的方式存儲，保持了連接配接存儲結構在執行插入或删除操作時不用移動元素的優點，隻要找到合适的插入和删除位置後，僅需要修改連結指針即可。插入删除的時間性能比較好。而對于二叉排序樹的查找，走的就是從根節點到要查找的結點的路徑，其比較次數等于給定的結點在二叉排序樹的層數。極端情況，最少為1次，最多也不會超過樹的深度。
但是問題在于，二叉排序樹的形狀是不确定的。
如果二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，均為【log2n】+1，那麼查找的時間複雜也就是O(logn),近似與折半查找。
不平衡的情況就是斜樹，查找的時間複雜度為O(n)，等同于順序查找。
于是我們可以引申出“平衡二叉樹”這樣的一個概念，即探讨關于如何讓二叉排序樹平衡的問題。
平衡二叉樹（AVL樹）：
平衡二叉樹（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree),是一種二叉排序樹，其中每一個結點的左子樹和右子樹的高度差至多等于1。-----》》》一種高度平衡的二叉排序樹。
二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF(Balance Factor)，那麼平衡二叉樹上所有結點的平衡因子隻可能是-1、0、1。隻要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。
距離插入結點最賤的，且平衡影子的絕對值大于1的結點為根的子樹，我們稱為最小不平衡子樹。
平衡二叉樹實作原理
平衡二叉樹建構的基本思想就是在建構二叉排序樹的過程中，每當插入一個結點時，先檢查是否因為插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各個結點之間的連結關系，進行相應的旋轉，使之成為新的平衡子樹。
平衡二叉樹的實作算法：
改進二叉排序樹的結點結構，增加一個bf，用來存放平衡因子：
typedef struct BiTNode //結點結構
{
int data;//結點資料
int bf;//結點的平衡因子
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
右旋操作
/*對以p為根的二叉排序樹作右旋處理，處理之後p指向新的樹根結點，即旋轉處理之前的左子樹的根結點*/
void R_Rotate(BiTree *P)
{
BiTree L;
L=(*P)->lchild;//L指向P的左子樹根結點
(*P)->lchild = L->rchild;//L的右子樹接為P的左子樹
L->rchild=(*P);
*P=L;//P指向新的結點
}
左旋操作
/*對以P為根的二叉排序樹作左旋處理，處理之後P指向新的樹根結點，即旋轉處理之前的右子樹的根結點0*/
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild;//P指向P的右子樹根結點
(*P)->rchild = R->lchild;//R的左子樹挂接為P的右子樹
R->lchild = (*P);
*P = R;//P指向新的根結點
}
下面是左平衡旋轉處理的函數代碼：
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
/*對以指針T所指結點為根的二叉樹作左平衡旋轉處理，
本算法結束時，指針T指向新的根結點*/
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L = (*T)->lchild;//L指向T的左子樹根結點
switch(L->bf)
{
//檢查T的左子樹的平衡度，并作相應平衡處理
case LH://新結點插入在T的左孩子的左子樹上，要作單右旋轉處理
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH://新結點插入在T的左孩子的右子樹上，要作雙旋處理
Lr=L->rchild;//Lr指向T的左孩子的右子樹的根
switch(Lr->bf)//修改T及其左孩子的平衡因子
{
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);//對T的左子樹作左旋平衡處理
R_Rotate(T);//對T作右旋平衡處理
}
}
主函數：
/*若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個資料元素為e的結點并傳回1，否則傳回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否。*/
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{
/*插入新結點，樹“長高”，置taller為TRUE*/
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}
else
{
if(e==(*T)->data;
{
/*樹中已存在和e有相同關鍵字的結點則不再插入*/
*taller = FALSE;
return FALSE;
}
if(e<(*T)->data)
{
if(!InsertAVL(&(*T)->lchild,e,taller)) //未插入
return FALSE;
if(*taller) //已插入到T的左子樹中且左子樹“長高”
{
switch((*T)->bf) //檢查T的平衡度
{
case LH://原本左子樹比右子樹高，需要作左平衡處理
LeftBalance(T);
*taller = FALSE;
break;
case EH://原本左右子樹等高，現因左子樹增高而樹增高
(*T)->bf = LH;
*taller = FALSE;
break;
case RH://原本右子樹比左子樹高，現在左右子樹等高
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}
else
{
//應繼續在T的右子樹中進行搜尋
if(!InsertAVL(&(*T)->rchild,e,taller))//未插入
return FALSE;
if(*taller) //已插入到T的右子樹且右子樹“長高”
{
switch((*T)->bf) //檢查T的平衡度
{
case LH://原本左子樹比右子樹高，現在左右子樹等高
(*T)->bf = EH;
*taller = FALSE;
break;
case EH://原本左右子樹等高，現因右子樹增高而樹增高
(*T)->bf = RH;
*taller = FALSE;
break;
case RH://原本右子樹比左子樹高，需要作右平衡處理
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
構造一棵平衡二叉樹的代碼實作：
int i;
int a[10] = {3,2,1,4,5,6,7,10,9,8};
BiTree T = NULL;
Status taller;
for(i = 0;i<10;i++)
{
InsertAVL(&T,a[10],&taller);
}
查找的時間複雜度O(logn);
插入和删除也同樣是O(logn).
多路查找樹(B樹)
多路查找樹(muitl-way search tree)，其中每一個結點的孩子數可以多于兩個，且每一個結點處可以存儲多個元素。
---》》》其有四種特殊形式：
2-3樹、2-3-4樹、B樹和B+樹
--》》2-3樹：
2-3樹是這樣的一棵多路查找樹：其中每一個結點都具有兩個孩子（我們稱它為2結點）或三個孩子（我們稱它為3個結點）。
一個2結點包含一個元素兩個孩子（或沒有孩子），且與二叉排序樹類似，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。與二叉排序樹的差別在于這個2結點要麼沒有孩子，要有就隻能有兩個，不能隻有一個孩子。
一個3結點包含一小一大兩個元素和三個孩子（或沒有孩子），一個3結點要麼沒有孩子，要麼具有3個孩子。如果某個3結點有孩子的話，左子樹包含小于較小元素的元素，右子樹包含大于較大元素的元素，中間子樹包含介于兩元素之間的元素。
并且所有的2-3樹中所有的葉子都在同一層次上。
2-3樹複雜的地方就在于新結點的插入和已有結點的删除。
2-3樹的插入實作：
2-3樹插入可以分為三種情況：
1)對于空樹，插入一個2結點即可。
2)插入結點到一個2結點的葉子上。應該說，由于其本身就隻有一個元素，是以隻需要将其更新為3的結點即可。
3)要往3結點中插入一個新元素。
因為3結點本身已經是2-3樹的最大容量，是以就需要将其拆分，且将樹中兩元素或插入元素的 三者中選擇其一向上移動一層。複雜的情況也正在于此。
2-3樹删除實作：
2-3樹的删除也分為三種情況：
1)所删除的元素位于一個3結點的葉子結點上，這非常簡單，隻需要在該結點處删除該元素即可，不會影響到整棵樹的其它結點結構。
2)所删除元素位于一個2結點上，即要删除的是一個隻有一個元素的結點。對于删除葉子是2結點的情況，需要分一下四種情形來讨論。
情形一，此節點的額雙親也是2結點，且擁有一個3結點的右孩子。
情形二，此結點的雙親是2結點，它的右孩子也是2結點。
情形三，此結點的雙親是一個3結點。
情形四，如果目前樹是一個滿二叉樹的情況，此時删除任何一個葉子都會使得整棵樹不能滿足2-3樹的定義。
3)所删除的元素位于非葉子的分支結點。此時我們通常是将樹按中序周遊後得到此元素的前驅或後繼元素，考慮讓它們來補位即可。
2-3-4樹：
2-3-4就是2-3樹的概念擴充，包括4結點的使用。一個4結點包含小中大三個元素和四個孩子(或沒有孩子)，一個4結點要門沒有孩子，要麼具有4個孩子。---》》》如果某個4結點有孩子的話，左子樹包含小于最小元素的元素；第二子樹包含大于最小元素，小于第二進制素的元素；第三子樹包含大于第二進制素，小于最大元素的元素；右子樹包含大于最大元素的元素。
B樹：
B樹(B-tree)是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例。結點最大的孩子數目稱為B樹的階(order)，是以，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。
--》所有葉子結點都位于同一層次。
--》所有分支結點包含下列資訊資料（n,A0,K1,A1,K2,A2,…,Kn,An），其中：Ki(i=1,2,…,n)為關鍵字，且Ki<K(i+1)(i=1,2,…，n-1);Ai(i=0,2,…,n)為指向子樹根結點的指針，且指針A(i-1)所指子樹中所有關鍵字均小于Ki(i=1,2,…，n),An所指子樹所有結點的關鍵字均大于Kn,n(【m/2】-1<=n<=m-1)為關鍵字的個數(或n+1為子樹的個數)。
在B樹上查找的過程是一個順直鎮查找結點和在結點中查找關鍵字的交叉過程。
B+樹：
B+樹是應檔案系統所需而出的一種B樹的變形樹，其實從嚴格意義上，它其實已經不是第六章定義的樹了。在B樹中，每個元素在該樹中隻出現一次，有可能在葉子結點上，也有可能在分支結點上。而在B+樹中，出現在分支結點中的元素會被當做他們在該分支結點位置的中序後繼者（葉子結點）中再次列出。另外，每一個葉子結點都會保留一個指向後一頁子結點的指針。
：---》》》插圖：
一棵m階的B+樹和m階的B樹的差異在于：
--》》有n棵子樹的結點中包含有n個關鍵字
--》》所有葉子結點包含全部關鍵字的資訊，以及指向含這些關鍵字記錄的指針，葉子結點本身依關鍵字的大小自小而大順序連結。
--》》所有分支結點可以看成是索引，結點中僅含有其子樹中的最大（或最小）的關鍵字。
這樣的資料結構的好處：如果是要随機查找，我們就從根結點出發，與B樹的查找方式相同，隻不過即使在分支結點找到了待查找的關鍵字，它也隻是用來索引的，不能提供實際記錄的通路，還是需要到達包含此關鍵字的終端結點。
B+樹特别适合帶有範圍的查找。
散清單查找（哈希表）概述
散清單查找定義：
存儲位置=f(關鍵字)
散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系f使得每個關鍵字key對應一個存儲位置f(key)。
--》》我們把這種對應關系f稱為散列函數，又稱為哈希（Hash）函數。
采用三列結束将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表(Hash table)。
散清單查找步驟：
整個散列過程其實就是兩步》》》
1)在存儲時，通過散列函數計算記錄的散列位址，并按此散列位址存儲該記錄。--》》總之就是，不管是什麼記錄，我們都要用同一個散列函數計算出位址再存儲。
2)當查找記錄時，我們通過同樣的散列函數計算記錄的散列位址，按此三列位址通路該記錄。
---》》》散列技術既是一種存儲方法，也是一種查找方法。
散列技術的記錄之間不存在什麼邏輯關系，它隻與關鍵字有關。故散列主要是面向查找的存儲結構。
散列技術最适合的求解問題是查找與給定值相等的記錄。
散列技術 “不适合” 以下情況：
1.那種相同的關鍵字，能夠對應很多的記錄的情況。
2.不适合反問查找。
另一個問題是沖突。理想的情況下，每一個關鍵字，通過散列函數計算出來的位址都是不一樣的，可現實生活中，這隻是一個理想。我們時常碰到以下情況：兩個關鍵字key1≠key2，但卻有f(key1)=f(key2)，這種現象我們稱為沖突(collision)，并把key1和key2稱為這個散列函數的同義詞（synonym）。
--》出現沖突将造成查找錯誤。盡管可以通過盡心設計的散列函數讓沖突盡可能的少，但不能完全避免。
散列函數的構造方法：
原則：
1)計算簡單。散列函數的計算時間不應該超過其他查找技術與關鍵字的比較時間。
2)散列位址分布均勻。我們剛剛也談到沖突帶來的問題，最好的辦法确實就是盡量讓散列位址均勻地分布在存儲空間中，這樣可以保證存儲空間的有效利用，并減少為處理沖突而耗費的時間。
以下是幾種常用的散列函數的構造方法。
1.直接定址法：取關鍵字的某個線性函數值為散列位址，即
f(key) = a * key + b (a、b為常數)
這樣的散列函數的優點就是簡單、均勻，也不會産生沖突，但問題是這需要事先知道關鍵字的分布情況，适合查找表較小且連續的情況。--》由于這樣的限制，在現實應用中，這種方法雖然簡單，但是卻并不常用。
2.數字分析法：
抽取方法是使用關鍵字的一部分來計算散列存儲位置的方法，這在散列函數中是常常用到的手段。
數字分析法通常适合處理關鍵字位數比較大的情況，如果事先知道關鍵字的分布且關鍵字的若幹位分布較均勻，就可以考慮用這個方法。
3.平方取中法：
假設關鍵字是1234，則其平方為1522756，抽取中間的3位就是227，用作散列位址。
平方取中法較适合于不知道關機子的分布，而位數又不是很大的情況。
4.折疊法：将關子健從左到右分割成位數相等的幾部分（注意最後一部分位數不夠時可以短些），然後将這幾部分疊加求和，并按散清單表長，去最後幾位作為散列位址。
例子：
比如我們的關鍵字時9876543210，散清單表長三位，我們将其分成四組，987|654|321|0，然後将它們疊加求和987+654+321+0 = 1962，再求後3位得到散列位址為962。
有時還不能夠保證分布均勻，不妨從一端到另一端來回折疊後對齊相加。比如我們将987和321反轉，再與654和0相加，變成789+654+123+0 = 1566，此時散列位址為566。
折疊法事先不需要知道關鍵字的分布，适合關鍵字位數較多的情況。
5.除留餘數法
此方法為最常用的構造散列函數方法。對于散清單長為m的散列函數公式為;
f(key) = key mod p (p<=m)
本方法的關鍵在于選擇合适的p,p如果選擇得不好，就可能容易産生同義詞。
--》》根據前人的經驗，若散清單表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20的質因子的合數。
6.随機數法：
選擇一個随機數，取關鍵字的随機函數值為它的散列位址。也就是f(key) = random(key)。
現實中，應該視不同的情況采用不同的散列函數。以下是一些考慮因素：
1.計算散列位址所需要的時間。
2.關鍵字的長度。
3.散清單的長度。
4.關鍵字的分布情況。
5.記錄查找的頻率。
處理散列沖突的方法：
1.開放定址法：是一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入。
它的公式是：
fi(key)=(f(key)+di) MOD m (di = 1,2,3,……,m-1)
---》》》線性探索法
---》》》本來不是同義詞卻需要争奪一個位址的情況，我們稱這種現象為堆積。
改進di=1^2,-1^2,2^2,-2^2……,q^2,-q^2,(q<=m/2)，這就等于是可以雙向尋找可能的空位置。對于34來說，我們取di=-1即可以找到空位置了。
增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域。我們稱這種方法為二次探索法。
fi(key)=(f(key)+di) MOD m (di=1^2,-1^2,2^2,-2^2……,q^2,-q^2,q<=m/2)
還有一種方法是，在沖突時，對位移量di采用随機函數計算得到，我們稱之為随機探測法。
fi(key)=(f(key)+di) MOD m (di是一個随機數列)
總之開放位址法隻要在散清單未填滿時，總能找到不發生沖突的位址，使我們常用的解決沖突的方法。
2.再散列函數法
事先準備多個散列函數。
fi(key) = RHi(key) (i=1,2,…,k)
這裡RHi就是不同的散列函數，你可以把前面提到的除留餘數、折疊、平方取中全部用上。每當發生散列位址沖突時，就換一個散列函數計算，相信總有一個可以吧沖突解決掉。這種方法能夠使關鍵字不産生聚集，當然，相應地也增加了計算時間。
3.鍊位址法
将所有關鍵字為同義詞的記錄存儲在一個單連結清單中，我們稱這種表為同義詞字表，在散清單中指存儲所有同義詞字表的頭指針。
---》》連位址法對于可能會造成很多沖突的散列函數來說，提供了絕不會出現找不到位址的保障。當然，這也就帶來了查找時需要周遊單連結清單的性能損耗。
4.公共溢出區法
将沖突的另外履歷一個公共的溢出區來存放。
在查找時，對給定值通過散列函數計算出散列位址後，先與基本表的相應位置進行對比，如果相等，則查找成功，否則到溢出表去順序查找。如果相對于基本表而言，有沖突的資料很少的情況下，公共溢出區的結構對于查找性能來說還是非常高的。
散清單查找實作：
散清單結構的定義，其中HashTable就是散清單結構。結構中elem為一個動态數組：
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 //定義散清單長為數組的長度
#define UNLLKEY -32768
typedef struct
{
int *elem;//資料元素存儲基址，動态配置設定數組
int count;//目前資料元素個數
}HashTable;
int m = 0;//散清單表長，全局變量
有了結構定義，以下對散清單進行初始化
/*初始化散清單*/
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(i = 0;i<m;i++)
H->elem[i] = UNLLKEY;
return OK;
}
為了插入時計算位址，我們需要定義散列函數，散列函數可以根據不同情況更改算法。
/*散列函數*/
int Hash(int key)
{
return key % m;//除留餘數法
}
初始化完成後，我們可以對散清單進行插入操作。假設我們的關鍵字集合如下：
{12,67,56,16,25,37,22,29,15,47,48,34}
/*插入關鍵字進散清單*/
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key);//求散列址
while(H->elem[addr]!=NULLKEY)//如果不為空，則沖突
addr = (addr+1)%m;//開放定址法的線性探測，也可以改用其他的方法
H->elem[addr] = key;//直到有空位後插入關鍵字
}
散清單存在後，我們再需要時就可以通過散清單查找要的記錄
/*散清單查找關鍵字*/
Status SearchHash(HashTable H,int key, int *addr)
{
*addr = Hash(key);//求散列位址
while(H.elem[*addr]!=key)//如果不為空，則沖突
{
*addr = (*addr+1)%m;//開放定址法的線性探測
if(H.elem[*addr]==NULLKEY||*addr==Hash(key))
{//如果循環回到原點
return UNSUCCESS;//則說明關鍵字不存在
}
}
return SUCCESS;
}
查找的代碼與插入的代碼非常類似，隻需要做一個不存在關鍵字的判斷而已。
散清單的查找性能分析：
如果"沒有沖突"則為O(1).
散列查找的平均查找長度取決于以下因素：
1.散列函數是否均勻--》》由于不同的散列函數對于同一組随機的關鍵字，産生的沖突的可能性是相同的，是以不考慮其對平均查找長度的影響。
2.處理沖突的方法--》》相同的關鍵字、相同的散列函數，但處理沖突的方法不同，會使得平均查找長度不同。比如線性探測處理沖突可能會昌盛堆積，顯然沒有二次探測法好，而鍊位址法處理沖突不會産生任何堆積，因而具有更佳的平均查找性能。
3.散清單的填裝因子：
所謂填裝因子α = 填入表中記錄個數/散清單長度。α标志着散清單的裝滿的程度。當填入表中的記錄越多，α越大，産生沖突的可能性越大。也就是說，散清單的平均查找長度取決于填裝因子，而不是取決于查找集合中的記錄個數。
不管記錄個數n有多大，我們總可以選擇一個合适的填裝因子以便将平均查找長度限定在一個範圍之内，此時我們散列查找的時間複雜度就真的是O(1)了。為此，我們通常間散清單的空間設定得比 号召集合大，此時雖然會浪費一定的空間，但是換來的查找效率大大的提升，總的來說，還是非常值得。 P c ch