靜態搜尋法
對靜態檔案(用循序表示法儲存)進行搜尋
循序搜尋法
時間複雜度最差最好情況皆為bigO(N)
一筆筆資料逐一比較
unsorted array:insert=bigO(1) , finddata=bigO(n) , findminormax=bigO(n)
binary search algorithm(二元搜尋法)
時間複雜度為bigO(2底log N)
資料需先排列，從中間位置開始比較，依大小在到左半邊或右半邊的中間比較
遞迴方法
int binary_search(int list[],int first,int last,int data){ //data代表資料
if(first>last)return(-1); //資料不在list內
else{
middle=(first+last)/2;
if(list[middle]==data)return(middle); //傳回data的位置
else{
if(list[middle]>data)binary_search(list,middle-1,last,data); //data在左半邊
else if(list[middle]
}
}
}
非遞迴方法
int binary_search(int list[],int first,int last,int data){
int middle;
while(first<=last){
middle=(first+last)/2;
if(data==list[middle])return(middle);
else if(data>list[middle])first=middle+1; //data在右邊
else last=middle-1; //data在左邊
}
if(first>last)return(-1); //資料不在list內
}
費氏搜尋法
時間複雜度為bigO(2底log N)
資料需先排列，使用費氏數列切割檔
費氏數列：f(0)=0,f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5,f(6)=8,f(7)=13
假設n筆資料=f(x)-1 ex:12=f(7)-1=13-1,x=7
樹根=f(x-1) ex:f(7-1)=f(6)=8
左子樹節點數=f(x-1)-1 ex:f(6)-1=7
右子樹節點數=f(x-1)-2 ex:f(6)-2=4
樹根與son差距=f(x-3) ex:f(7-3)=3,因此樹根-3到左子樹樹根，+3到右子樹樹根
假設樹根值=f(j) ex:8=f(6),j=6
樹根與son差距=f(j-2) ex:f(6-2)=3,結果同上做法不同而己
假設祖父與父親差距=f(r) ex:差距=8-5=3 , 3=f(4),r=4
在左子樹的父節點和son的差距=f(r-1) ex:f(r-1)=f(4-1)=2
在右子樹的父節點和son的差距=f(r-2) ex:f(r-2)=f(4-2)=1
假設高度為h(root=0)，則節點數為f(h+3)-1
f(0)=1,f(1)=2,f(2)=4,f(3)=7,f(4)=12,f(5)=20…
插補搜尋法
資料需先排列，和二元搜尋法類似，差別在middle的計算不同，若資料分佈均匀則為bigO(1),否則最差情況為bigO(n)
假設list[lower]=第一筆資料且值最小，list[upper]=最後一筆資料且值最大
middle=(key-list[lower])/(list[upper]-list[lower])*(upper-lower)+lower
擴充二元樹＝原樹＋external node外部節點
原內部節點指向空的欄位，改成指向特殊的外部節點(也稱失敗節點，且有n+1個)
internal path length內部路徑長度(i)=搜尋成功的成本,由樹根到所有內部節點的路徑長度的總和
external path length外部路徑長度(e)=搜尋失敗的成本,且e=i+2*n，由樹根到所有外部節點的路徑長度的總和
若等於完整二元樹，擴充二元樹則有最小的i與e，(假設各節點長度為1)則i的長度=n為0~n各別放入ceil(log2(n+1))-1後相加
ex:n=7,就是0+1+1+2+2+2+2
若等於傾斜二元樹，擴充二元樹則有最大的i與e，(假設各節點長度為1)則i的長度=n*(n-1)/2=0+1+2+3+…(n-1)
設id1=樹根到第一個內部節點的距離，ip1=第一個內部節點的加權，
weighted internal path length加權內部路徑長度=id1*ip1+id2*ip2+….idn*ipn (搜尋成功的成本)
設ed1=第一個外部節點的距離，ep1=第一個外部節點的加權
weighted external path length加權外部路徑長度=ed1*ep1+ed2*ep2+…..ed(n+1)*ep(n+1) (搜尋失敗的成本)
huffman tree(霍夫曼樹)
說明：具有最小加權外部路徑長度(編碼與解碼成本)的擴充二元樹(內部節點的加權總合=加權外部路徑長度)
演算法：貪婪法，選擇程式=外部節點的加權
優點：編碼與解碼，最佳合併過程
huffman tree建立方法：將一筆料經排序後，每一次找出兩個最小加權的值當父節點，並反覆一直到建出樹根節點
huffman code建立方法：將左分支表示0，右分支表示1，每個資料即可得到一個編碼
最差狀況下的合併次數：內部節點相加
optimal binary search tree(最佳二元搜尋樹)
說明：高度最小的二元搜尋樹，且加權內部路徑長度與加權外部路徑長度總和最小
目地：為了能讓搜尋成本最少，也就是搜尋的平均比較次數最少，以提昇搜尋效率
做法：可先產生所有可能的二元樹，再計算各不同二元樹的搜尋成本，即可找出成本最小的最佳搜尋二元樹
動態規畫法的設計方式：讓樹根節點的左子樹搜尋成本與右子樹搜尋成本相加會最小的擴充二元樹，就是搜尋成本最小的最佳二元搜尋樹
遞迴關係式：cost(i,j)={
0 , if i=j
min{cost(i,k-1)+cost(k,j)}+weight(i,j) , i<=j
……………………………………………………………………………..
動態搜尋法
允許資料能隨時進行插入與刪除運作，適合使用鏈結表示法
sorted linked list: insert=O(n) , finddata=O(N) , findmaxormin=O(1)
unsorted linked list:insert=O(1) , finddata=O(N) , findmaxormin=O(N)
binary search tree(二元搜尋樹)
說明：二元樹的一種，若非空集合，則樹根節點的左子樹所有節點比樹根節點的值小，右子樹所有節點則比樹根節點大，左右子樹也等於二元搜尋樹
若使用中序走訪，則可將值由小到大列出
優點：動態資料插入刪除與搜尋
特質:左子樹小於父節點,右子樹大於父節點
worst case:O(n),average case:O(2底log n)
void find_great_than_x(struct treenode *root,int x){ //此程式碼尚未完成
if(root==null)printf(“there is no data y>x”); //若是空樹則沒有
else if(root->dataright,x); //若x比樹根大則往右子樹搜尋
else if(root->data>x) find_great_than_x(root->left,x); //若x比樹根小則往左子樹搜尋
else printf(“y=%d”,root->data”);
}
插入運作
treenode insert(struct treenode *root,int value){ //新增value進樹
}
搜尋運作
treenode search(struct treenode *node,int value){
}
刪除運作
若要刪除的資料節點分支度<2 則直接刪除，否則找該節點左子樹中最大值節點或右子樹中最小值節點取代欲刪除節點，在刪除最大或最小值節點
treenode delete(struct treenode *root,int value,struct treenode *parent){
}
最差情況是建立傾斜二元樹，則插入刪除搜尋都為bigO(N)，最佳情況是建立趨近平衡的二元樹，則插入刪除搜尋都為bigO(2底log n)
avl tree(高度平衡二元樹)
說明：特殊二元搜尋樹,定義和二元搜尋樹一樣，差別在於插入或刪除一節點後要對部份子樹進行調整以保持高度平衡
優點：動態資料插入刪除與搜尋，最差情況(log n)優於二元搜尋樹
插入刪除插尋都為bigO(2底log n)，也就是樹的高度
節點結構
typedef struct avltreenode *treenode;
typedef struct avltreenode{
treenode left;
int data;
int balance_factor; //左右子樹高度差，只有-1,0,1三種值
treenode right;
}
插入與刪除需要做rotation旋轉,共有四種：
LL:點a左樹根b取代點a,點a和點a右樹變成點b右樹,點b原右樹變成點a左樹(a變b的右樹,b的右樹變成a的左樹)
RR:和LL相反(a變b的左樹,b的左樹變成a的右樹)
LR:點a左兒b的右兒點c取代點a,點b變成點c左樹,點a和點a右樹變成點c右樹,點c左樹變成點b右樹,點c右樹變成點a左樹
RL:和LR相反
m元b樹 高度平衡m元搜尋樹
特殊的m-way搜尋樹，分支度為m，樹根分支度至少為2，失敗節點在最下層且同一層，每個節點至少有ceil(M/2)個子樹
優點：動態資料插入刪除與搜尋
2-3tree:分支度為3的btree,除失敗節點外,所有節點分支度不是2就是3
insert,delete複雜度＝樹的高度＝O(log3(N))
2-3-4tree:分支度4的btree,除失敗節點外,所有節點分支度不是2就是3或4，設高為h：
當各內部節點分支度是4時具有最小高度,則資料數=4^h-1,若不考慮失敗節點則h=ceil(log4(n+1))
當各內部節點分支度是2時具有最大高度,則資料數=2^h-1,若不考慮失敗節點則h＝ceil(log2(n+1))
insert,delete複雜度＝O(log4(N))
搜尋新增刪除都為bigO(logm(N))
分支度為3的節點結構
struct treenode{
struct treenode *child1; //指向第一資料欄位的左兒子節點
int data1;
struct treenode *child2; //指向第一資料欄位的右兒子節點
int data2;
struct treenode *child3; //指向第二資料欄的右兒子節點
int degree;
}treenode
插入運作：
1, 由樹根往下找，若資料不在b樹中則停在失敗節點,然後插入資料在失敗節點的上層節點c中
2, 若節點c未填滿(分支度
若節點c填滿(分支度=M)，將c節點在同一層分成二個節點，並將c節點中間的資料插入到父親節點
3, 重覆步驟2直到完成插入(分支度=
刪除運作：。。。
節點個數：分支度為3的b樹，若高為h，則節點數為1+3^1+3^2+….3^(h-1)=(3^h-1)/2，1節點有2資料，所以資料數為3^h-1
範圍查詢：。。。
b’ tree
btree的一種變化，可提供單一資料的簡單查詢與多個資料的範圍查詢
原失敗節點中放所有資料，並用鏈節欄位連成一鏈節串列，且資料值由左至右逐一遞增
原非失敗節點中只存於部份的值用來當成索引結構，表示節點的子樹中的最大值或最小值以方便範圍查詢
red-black trees(紅黑樹)
2-3-4樹的二元樹形式表示，為二元搜尋樹
各節點指標有紅指標(234樹經轉換後多出來的指標)與黑指標(原先234樹指標)
由樹根節點到外部節點的所有路徑上，黑指標的個數相同
由樹根節點到外部節點的所有路徑上，不會有連續兩個紅指標
hashing search(雜湊搜尋法)
主要用在插入和搜尋或刪除
最有用的資料結構之一
運作時間和資料個數無關,時間複雜度為bigO(1)
經過一個算術運算函數計算，而得到資料位址(雜湊位址)
collision:不同的資料計算出相同的雜湊位置，第n筆資料未碰撞的機率=資料1未碰撞機率*資料2未碰撞機率…*資料n未碰撞機率
overflow:發生collision且沒有空間可以存放資料
若無發生overflow溢位，則搜尋插入刪除所需時間空間和資料個數無關
hashing function(雜湊函數)：主要注意有:避免collision碰撞(算出的位置最好是均匀分配)，容易計算
常用有平方中間法，除法，摺疊法，數字分析法
除法：資料 mod 雜湊表大小(最好是質數)＝雜湊位置
因為雜湊表空間有限所以溢位一定會發生，解決辦法：
linear probing(線性搜尋法)：將hash表視為環狀，發生溢位時，往下找最近的空位存放資料
chaining(鏈串法)：hash表各位址用鏈結串列存放資料，相同位址的資料會存放在同一個鏈結串列中
rehashing(重新雜湊)：若發生溢位則用另一個雜湊寒數重新計算資料位址
若資料被刪除時？
……………………………………………………………………………..
heap(堆積結構)
可應用在priority queue
heap適合用循序表示法儲存
ps:
heap是樹狀結構,而堆疊是線性結構
滿足heap的條件:
1為一完整二元樹
2裡面的元素需符合heap condition(也稱heap property)
ps:
heap condition:
各node內的data比它左右兩邊child nodes內的data小,而左右兩child nodes間並無一定的關係
也就等於,每棵子樹中最小的元素總是在樹根
heap分為:
max heap(最大堆積),父節點會比子節點大
min heap(最小堆積),父節點會比子節點小
若有n個節點,則高度為log2(n+1)，因此插入與刪除複雜度=bigO(log2(n))
搜尋最大值與最小值皆為bigO(1)，但若要搜尋指定的值為bigO(n)
整個建立最大最小堆積結構的複雜度為bigO(n)
證明：。。。
在線性複複雜度bigO(N)建立max tree步驟
1，將陣列資料視為完整二元樹，並取一值當新資料插入堆積樹內，新資料需插在最後一個節點
2，若是max tree,則新資料比父節點大則調換，並往上逐一檢查子節點是否大於父節點，若是則調換
2，若是min tree,則新資料比父節點小則調換，並往上逐一檢查子節點是否小於父節點，若是則調換
void insertitem(p,data){
pos=rear+1; //pos取得最後一個節點的位置
p[pos]=data;
while(pos>front){ //front是第一個節點的位置
if(p[pos] < p[pos/2]){ break;}
else{
swap(p[pos],p[pos/2]);
pos=pos/2;
}
}
}
刪除
將最後一筆資料取代要被刪除的資料，並往下檢查是否符合最大或最小樹的性質
removeroot(p){
…
}
雙向堆積結構
一個樹根節點的值為null的完整二元樹，且樹根的左子樹是最小樹，右子樹是最大樹，因此左子樹節點必小於右子樹節點
插入運作：插在最後一個節點後面，若比右樹任一節點大則到右樹並進行最大堆積的處理，否則就在左樹進行最小堆積的處理
雙向堆積的刪除最小值運作
雙向堆積的刪除最大值運作
插入與刪除最大或最小運作皆為bigO(log2(n))