查找一般分為有序查找和無序查找，這邊在講有序查找

例二分查找

? ? ? ? 二分查找就是在有序數組中，通過mid=(low+high)/2來判定中間值，將中間值與待查找的值進行比較，如果待查找的值大于中間值，那么就將范圍縮小，查找右邊；如果待查找的值小于中間值，那么查找左邊；如果待查找的值等于中間值，查找成功。

int BinarySearch(int R[],int n, int K){
//在數組R中對半查找K，R中關鍵詞遞增有序int low = 1, high = n, mid;while(low <= high){ //在Rlow…Rhigh之間查找Kmid=(low+high)/2;if(K<R[mid]) high=mid-1; //在左半部分查找else if(K>R[mid]) low=mid+1; //在右半部分查找else return mid; //查找成功}return -1; //查找失敗
}

? ? ? ? ? 在該算法中確定比較值是非常重要的一件事，不同的比較值的確定可以決定不同的時間復雜度。所以還可以拓展出類似斐波那契查找，插值查找之類的算法。

二叉查找樹

例1.查找

????????其實二叉查找樹在這邊更像是一種結構，就是結點的左孩子一定小于結點，結點右孩子一定大于結點。查找到數據之后往往還要對數據進行處理，在處理過后還要保持原有結構，是比較困難的地方。

BSTnode* Search2(BSTnode* root, int K){ BSTnode* p = root;while (p != NULL) {if (K < p->key) p = p->left;else if (K > p->key) p = p->right;else return p;}return NULL;
}

例2.插入

就是找到對應的位置，然后建立新的結點。

void Insert(BSTnode* &root, int K){if (root == NULL) root = new BSTnode(K); else if (K < root->key) Insert(root->left, K);else if (K > root->key) Insert(root->right, K);
}

例3.刪除

????????這邊的刪除是在二叉樹中一定有值等于k的結點的情況下，否則要修改一些代碼。

void remove(BSTnode* &root, int K) {if(root==NULL) return;if(K<root->key) remove(root->left, K); //在左子樹刪Kelse if(K>root->key) remove(root->right, K); //在右子樹刪Kelse if(root->left!=NULL && root->right!=NULL){BSTnode *s=root->right;while(s->left!=NULL) s=s->left;root->key=s->key; //s為t右子樹中根序列第一個結點remove(root->right, s->key);}else{ BSTnode* oldroot=root;root=(root->left!=NULL)? root->left:root->right;delete oldroot;}
}

例4.高度平衡樹

? ? ? ? 高度平衡樹是二叉查找樹中的一種，它的左右孩子的高度差不會大于1，它通過變形、旋轉，讓樹的結構變得相對“矮胖”，方便后續處理縮小時間。但是這種結構就會對數據操作的過程提出很多額外的要求。

????????下面是關于旋轉的一些基本操作。這邊的代碼都比較抽象，適合配合圖形理解。

????????以LL為例，就是新插入的結點，在A結點的左孩子的左子樹上（A結點是從下往上數第一個不平衡的點），插入之后導致不再平衡。于是A結點的左孩子（設為B結點）的右孩子單獨拎出來，把右孩子變成A結點的左孩子，然后將這個拎出的B結點作為新的結點，它的右孩子連接到A結點上。

struct AVLnode {int key; //關鍵詞int height; //以該結點為根的子樹高度AVLnode *left, *right;AVLnode(int K){ key=K; height=0; left=right=NULL; }
};
int Height(AVLnode *t){ return(t==NULL)?-1:t->height; }
int max(int a, int b){ return (a>b)? a:b; }
void UpdateHeight(AVLnode *t){t->height = max(Height(t->left),Height(t->right))+1;
}void LL(AVLnode* &A) {AVLnode *B = A->left;A->left = B->right;B->right = A;UpdateHeight(A);UpdateHeight(B);A = B;
}void RR(AVLnode* &A) {AVLnode *B = A->right;A->right = B->left;B->left = A;UpdateHeight(A);UpdateHeight(B);A = B;
}void RL(AVLnode* &A){LL(A->right);RR(A);
}void LR(AVLnode* &A) {RR(A->left);LL(A);
}

AVL樹插入算法的實現

void ReBalance(AVLnode* &t) {if(t==NULL) return;if(Height(t->left) - Height(t->right)==2){ if(Height(t->left->left) >= Height(t->left->right)) LL(t);elseLR(t);}else if(Height(t->right) - Height(t->left)==2){if(Height(t->right->right) >= Height(t->right->left)) RR(t);elseRL(t);}UpdateHeight(t);
}void Insert(AVLnode* &root, int K) {if(root==NULL) root=new AVLnode(K);else if(K < root->key) //在左子樹插入Insert(root->left, K);else if(K > root->key) //在右子樹插入Insert(root->right, K);ReBalance(root);
}

AVL樹刪除算法的實現

void remove(AVLnode* &root, int K) {if(root==NULL) return;if(K<root->key) remove(root->left, K); //在左子樹刪Kelse if(K>root->key) remove(root->right, K); //在右子樹刪Kelse if(root->left!=NULL && root->right!=NULL){AVLnode *s=root->right;while(s->left!=NULL) s=s->left;root->key=s->key; //s為t右子樹中根序列第一個結點remove(root->right, s->key);}else{ AVLnode* oldroot=root;root=(root->left!=NULL)? root->left:root->right;delete oldroot;}ReBalance(root);
}

所以其實比起怎么插入、刪除，更重要的是怎么保持原來的結構