查找一般分为有序查找和无序查找，这边在讲有序查找

例二分查找

        二分查找就是在有序数组中，通过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);
}

所以其实比起怎么插入、删除，更重要的是怎么保持原来的结构