# 查找的基本概念：
查找：
在資料集合中尋找滿足某種條件的資料元素的過程稱為查找，查找的結果可以分為查找成功和查找失敗兩種
查找表：
用于查找的資料集合稱為查找表
對查找表進行的操作一般有：1、查詢；2、檢索；3、插入；4、删除
1和2為靜态查找表（順序查找、折半查找、散列查找等）；3和4為動态查找表（二叉排序樹的查找、散列查找等）
**關鍵字：**略
平均查找長度：
所有查找過程中進行關鍵字的比較的平均值
順序查找法：
算法思想
又叫做線性查找，通常用于線性表
算法實作
typedef struct{
Elemtype *elem;//動态數組基址
int TableLen;//表的長度
}SSTable;
//順序查找
int Search_Seq(SSTable ST,Elemtype key){
int i;
for(i=0;i<ST.TableLen&&ST.elem[i]!=key;++i);
return i==ST.TableLen?-1:i;//查找成功，傳回數組下标，查找失敗，傳回-1;
}
加入哨兵後如何實作？
//順序查找
int Search_Seq(SSTable ST,Elemtype key){
ST.elem[0]=key;//0号位置存哨兵
int i;
for(i=ST.TableLen;ST.elem[i]!=key;--i);//從後往前找
return i;//查找成功，傳回數組下标，查找失敗，傳回0;
}
查找效率分析：
算法優化
1、（對有序表）
一個成功的結點的查找長度等于自身所在層數；
一個失敗結點的查找長度等于其父節點所在的層數；
2、（被查的機率不相等）
總結：
分塊查找法（多在選擇題中考查，很少考察實作代碼）
算法思想
查找效率分析
總結：
折半查找法
算法思想：
又稱為二分查找，僅适用于有序的順序表
算法實作
typedef struct {//查找表的資料結構（順序表）
ElemType *elem;//動态數組基址
int TableLen;
}SSTable;
//折半查找
int Binary_Search(SSTable L,ElemType key)
{
int low =0,high =L.TableLen -1,mid;
while(low<=high)
{
mid =(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem<key)
low =mid+1;
else (L.mid>key)
high = mid -1;
}
return -1;//查找失敗，傳回—1.
}
查找判定樹
查找判定樹的構造：
折半查找效率
總結：
拓展：
樹型查找
二叉搜尋樹（BST）
二叉排序樹的遞歸實作和非遞歸實作
//非遞歸實作
BTNode *BST_Search(BSTree T,int key){
while (T!=NULL &&key!=T->key)
{
if(key>T->key)
T=T->rchild;
else
T=T->lchild;
}
return T;
遞歸實作：
BTNode *BST_Search(BSTree T,int key){
if(T==NULL)
return NULL;
if(key==T->key)
return T;
else if (key<T->key)
return BST_Search(T->lchild,key);
else
return BST_Search(T->rchild,key);
}
對于非遞歸實作，最壞空間複雜度為O（1）；對于遞歸實作，最壞時間複雜度為O（h）。
二叉排序樹的插入：
遞歸實作：
二叉排序樹作為一種動态集合，其特點是樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的結點時再進行插入的。
由于二叉排序樹是遞歸定義的，是以插入結點的過程如下：若原二叉排序樹為空，則直接插入結點；否則，若關鍵字＜根結點關鍵字，則插入左子樹，若關鍵字＞根結點關鍵字，則插入右子樹。
//插入的遞歸算法
BSTNode *Insert(BSTNode *root, int x){
if(root == NULL){
root = CreateTreeNode(x);
return root;
}
if(x < root->data){
root->left = Insert(root->left, x);
}
if(x > root->data){
root->right = Insert(root->right, x);
}
return root;
}
非遞歸實作：
代碼實作：
//插入的非遞歸算法
BSTNode *Insert1(BSTNode *root, int x){
BSTNode *parent = NULL;
BSTNode *p = root;
if(root == NULL){
root = CreateTreeNode(x);
return root;
}
while(p != NULL){
parent = p;
if(x < p->data){
p = p->left;
}else{
p = p->right;
}
}
if(parent->data >x){
parent->left = CreateTreeNode(x);
}else{
parent->right = CreateTreeNode(x);
}
return root;
}
二叉排序樹的構造
不同的關鍵字序列可能得到同款的二叉排序樹。也可能得到不同款二叉排序樹
構造一棵二叉排序樹就是依次輸入資料元素，并将它們插入二叉排序樹中适當位置上的過程。
構造二叉排序樹的過程：每讀入一個元素，就建立一個新結點，若二叉排序樹為空，則将新結點作為二叉排序樹的根結點；若二叉排序樹非空，則将新結點的值與根結點的值比較，若小于根結點的值，則插入左子樹，否則插入右子樹。
void Create(BSTNode *&root, int str[], int n){
root = NULL;
for(int i=0; i<n; i++){
Insert(root, str[i]);
}
}
二叉排序樹的删除
先找到目标結點
1、若被删除結點z是葉結點，而直接删除，不會破壞二叉排序樹的性質
綜上，
在二叉排序樹中删除一個結點時，不能把以該結點為根的子樹上的結點都删除，必須先把被删除結點從存儲二叉排序樹的連結清單上摘下來，将因删除結點而斷開的二叉連結清單重新連結起來，同時**確定二叉排序樹的性質（左子樹結點值＜根結點值＜右子樹結點值）**不會丢失。
删除操作一般會出現三種情況：
1） 若被删除結點z是葉結點，則直接删除，不會破壞二叉排序樹的性質。
2） 若結點z隻有一棵左子樹或右子樹，則讓z的子樹成為z父結點的子樹，替代z的位置。
3） 若結點z有左、右兩棵子樹，則令z的直接後繼（或直接前驅）替代z，然後從二叉排序樹中删除這個直接後繼（或直接前驅），這樣就轉換成了第一或第二種情況。
注：已知二叉排序樹經過中序周遊可以得到一個遞增的有序序列，這裡的直接後繼（或直接前驅）應該是指被删除結點在這個中序周遊序列中的直接後繼（或直接前驅）。
展現在二叉排序樹的圖中:
某個結點的直接後繼為以該結點為根的右子樹中最左下位置的結點，即右子樹的最小值；
某個結點的直接前驅為以該結點為根的左子樹中最右下位置的結點，即左子樹的最大值。
已知二叉排序樹經過中序周遊可以得到一個遞增的有序序列，這裡的直接後繼（或直接前驅）應該是指被删除結點在這個中序周遊序列中的直接後繼（或直接前驅）。
展現在二叉排序樹的圖中:
某個結點的直接後繼為以該結點為根的右子樹中最左下位置的結點，即右子樹的最小值；
某個結點的直接前驅為以該結點為根的左子樹中最右下位置的結點，即左子樹的最大值。
實作代碼：
//删除
bool Delete(BSTNode *p){
//在二叉排序樹中删除結點p, 并重新連接配接它的左右子樹
BSTNode *q, *s;
//1.p為葉子結點
if(p->left==NULL && p->right==NULL){
p = NULL;
}
//2.1 p左子樹為空, 重接右子樹
else if(p->left == NULL){
q = p;
p = p->right;
free(q);
}
//2.2 p右子樹為空, 重接左子樹
else if(p->right == NULL){
q = p;
p = p->left;
free(q);
}
//3. p左右子樹均不為空
else{
q = p;
s = p->right; //找到p的右子樹的最左端（中序直接後繼）
while(s->left != NULL){
q = s;
s = s->left;
}
p->data = s->data;
if(q != p) //判斷是否執行上述while循環
q->left = s->right; //執行上述while循環，重接*q的左子樹
else
q->right = s->right; //未執行上述while循環，重接*q的右子樹，對于這個情況，可以參考代碼後給出的示例圖
free(s);
}
return true;
}
bool DeleteBST(BSTNode *root, int x){
if(root == NULL){
return false;
}else{
if(x == root->data)
return Delete(root);
else if(x < root->data)
return DeleteBST(root->left, x);
else
return DeleteBST(root->right, x);
}
}
查找效率分析
查找成功的平均查找長度為：
Σ(本層高度本層結點個數) / 結點總數
查找不成功的平均查找長度為：
Σ(本層高度本層補上的葉子結點個數) / 補上的葉子總數
總結：