搜索(Search)的概念通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。实施搜索时有两种不同的环境。静态环境，搜索结构不提供插入和删除等操作。静态搜索表动态环境，搜索结构提供插入和删除等操作。动态搜索表顺序搜索(SequentialSearch)template<classType>intsearchList<Type>::Search(constType&x)const{//顺序搜索关键码为x的对象,//成功返回位置i,失败返回0Element[0].key=x;//将x送0号位置设“监视哨”inti=CurrentSize;while(Element[i].key!=x)i--;//从后向前顺序搜索returni;}顺序搜索的平均搜索长度(ASL)搜索成功时，在等概率情形，pi=1/n,i=0,1,2,,n-1基于有序顺序表的折半搜索搜索成功的例子搜索失败的例子template<classType>intorderedList<Type>::BinarySearch(constType&x,constintlow,constinthigh)const{//折半搜索的递归算法intmid=-1;if(low<=high){mid=(low+high)/2;if(Element[mid].key<x)mid=BinarySearch(x,mid+1,high);elseif(Element[mid].key>x)mid=BinarySearch(x,low,mid-1);}returnmid;}有序顺序表的折半搜索的判定树(10,20,30,40,50,60)折半搜索性能分析定义二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。左子树(如果存在)上所有结点的关键码都小于根结点的关键码。右子树(如果存在)上所有结点的关键码都大于根结点的关键码。左子树和右子树也是二叉搜索树。template<classType>BstNode<Type>*BST<Type>::Find(Typex,BstNode<Type>*ptr)const{//二叉搜索树的递归的搜索算法if(ptr==NULL)returnNULL;//搜索失败elseif(x<ptr->data)//在左子树搜索returnFind(x,ptr->leftChild);elseif(x>ptr->data)//在右子树搜索returnFind(x,ptr->rightChild);elsereturnptr;//相等,搜索成功}二叉搜索树的插入在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。搜索成功:树中已有这个元素,不再插入。搜索不成功:树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。template<classType>voidBST<Type>::Insert(Typex,BstNode<Type>*&ptr){if(ptr==NULL){//空二叉树ptr=newBstNode<Type>(x);//创建结点if(ptr==NULL){cout<<“存储不足"<<endl;exit(1);}}elseif(x<ptr->data)//在左子树插入Insert(x,ptr->leftChild);elseif(x>ptr->data)//在右子树插入Insert(x,ptr->rightChild);}输入数据，建立二叉搜索树的过程二叉搜索树的删除(四种情况)3.被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。4.被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。二叉搜索树查找次数分析AVL树的定义AVL树的类定义每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子如果在某一结点发现高度不平衡，停止回溯。该不平衡的结点为最深的不平衡点根据最深的不平衡点与新插入点的位置关系，进行相应的平衡化旋转单旋转:左单旋转或右单旋转双旋转:先左后右旋转和先右后左旋转插入新结点后导致结点A的平衡因子变成2，出现不平衡。为使树恢复平衡，以结点B为旋转轴，让结点A反时针旋转。//左单旋转的算法template<classType>voidAVLTree<Type>::RotateLeft(AVLNode<T