数据操作-Search（查找）

1. 顺序查找-O(N)
      线性表；无序查找
　　　 等概率条件下...平均查找长度：ASL = (n+....+2+1)/n= (n+1)/2。
2. 二分查找-O(logN)
      线性表；有序查找；mid=low+0.5*(high-low)
　　　 在等概率条件下...平均查找长度：ASL =（1/n）* ( j * 2^(j-1) )(j是从1到h)，ASL = log2(n+1)-1。
　　   原因：用二叉树来描述，树的高度d与节点树的关系为：n=(1+2+4+...... 2^(d-1))=2^d - 1；
　　   所以d = log2(n+1)，每一层只需要比较一次，所以最多需要比较log2(n+1)次
4. 差值查找-O(log(logN))-最坏o(logn)
      有序查找；mid=low+[(key-a[low])/(a[high]-a[low])]*(high-low)
3. 斐波那契查找-O(logN)
   　　有序查找
5. 分块查找-O(logN)
　　　　顺序查找
　　　　平均查找长度分为两部分，索引表的查找+块内的查找。（索引表能够用二分法和顺序查找，块内无序，所以只能用顺序查找）

　　　　　　如果以二分查找来确定块，则 ASL = log2(b+1)-1 + (s+1)/2。

　　　　　　如果以顺序查找来确定块，则 ASL = (b+1)/2 + (s+1)/2。

　　　　　　如果以哈希查找来确定块，则ASL=1 + (s+1)/2。

6. 哈希查找-O(1) 
7. 树表查找-动态查找-O(logN)

      二叉搜索树（二叉排序树）！！！！！！！ 
      平衡查找树！！！！！ 
      平衡查找树之红黑树！！！！！ 
      B树和B+树！！！！！

int a[10] = { 1, 6, 12, 21, 30, 31, 32, 42, 49, 52 };
function(a,10,49)

int seq_search(int *a,int n,int key)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(a[i]==key)
        {
            return i;
        }
    }
    return 0;
}

int binary_search(int *a,int n,int key)
{
    int mid;
    int low=0;
    int high=n-1;
    while(low<high)
    {
        mid=(low+high)/2;//low+0.5*(high-low)
        if(a[mid]==key)return mid;
        else if(a[mid]<key)low=mid+1;
        else if(a[mid]>key)high=mid-1;
    }
}

int BinarySearch(int[] a, int value, int low, int high) {
        if(low > high)return -1;
        int mid = (high + low)/2;
        if (a[mid] == value)return mid;
        if (a[mid] > value)
            return BinarySearch2(a, value, low, mid - 1);//往数组左边查找
        else
            return BinarySearch2(a, value, mid + 1, high);//往数组右边查找
    }

int insert_search(int *a,int n,int key)
{
    int mid;
    int low=0;
    int high=n-1;
    while(low<high)
    {
        mid=low+((key-a[low])/(a[high]-a[low]))*(low+high);
        if(a[mid]==key)return mid;
        else if(a[mid]<key)low=mid+1;
        else if(a[mid]>key)high=mid-1;
    }
}

void Fibonacci(int **Fb, int n)//构造费波纳茨数列
{
    int f1, f2,ft;
    int count=3;
    f1 = 1; f2 = 1;

    while (f2<n)//最后一位元素数字
    {
        ft = f1 + f2;
        f1 = f2;
        f2 = ft;
        count++;
    }
    (*Fb) = (int *)malloc(count*sizeof(int));
    (*Fb)[0] = 0;
    (*Fb)[1] = 1;
    for (f1 = 2; f1 <= count - 1; f1++)
        (*Fb)[f1] = (*Fb)[f1 - 1] + (*Fb)[f1 - 2];
}
int fibonacci_search(int *a,int n;int key)
{
    /* 1, 6, 12, 21, 30, 31, 32, 42, 49, 52
         Fb[]={1,1,2,3,5,8,13,....)
    1.首先我们要创建一个斐波拉契数列
    2.获取我们的数组大小n（我们不考虑0下标，因为我们的斐波那契数列从0开始，无法构成黄金比例），在斐波拉契数列中的位置
    3.因为我们的k=7,F[7]=13,而a数组最大为10，我们需要对其按照F[7]=13补齐数组，使其长度为F[7]-1=12,将a[11]=a[10],a[12]=a[10]
    4.开始正式查找，按照上图mid=low+F[k-1]-1;
    */
    int low=1;
    int high=n;
    int *Fb,*temp;
    Fibonacci(&fb,n);
    int k=0;
    while(n>Fb[k])//计算n位数字位于斐波那契数列位置
    {
        k++;
    }
    temp=(int *)malloc((Fb[k]-1+1)*sizeof(int));//后面加1是因为还有个下标0空间
    memcpy(temp,a,n*sizeof(n+1));
    for(i=n+1;i<Fb[k]-1;i++)
    {
        temp[i]=a[n];
    }
    while(low<=high)
    {
        mid=low+Fb[k-1]-1;
        if(key==temp[mid]){
            if(mid<=n)return mid;
            else return n;
        }
        else if(key>temp[mid])
        {
            low=mid+1;
            k=k-2
        }
        else
        {
            high=mid-1;
            k=k-1;
        }

    }
    return 0;
}

先选取各块中的最大关键字构成一个索引表；（每一块中的结点不必有序，但块与块之间必须"按块有序"）
查找分两个部分：
    先对索引表进行二分查找或顺序查找，以确定待查记录在哪块中；
    然后，在已确定的块中用顺序法进行查找。

用给定的哈希函数构造哈希表；
根据选择的冲突处理方法解决地址冲突，常见的解决冲突的方法：拉链法和线性探测法。

散列函数：
1：直接定址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b，其中a、b为常数（这种散列函数叫做自身函数）
2：数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3：平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
4：折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5：随机数法
6：除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k) = k mod p， p<=m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

解决冲突方法
1）拉链法：
将大小为M 的数组的每一个元素指向一个链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法；
2）线性探测法：
使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1：若任意节点的左子树不空，则左子树上所有节点的key值均小于它的根节点的值；
2：若任意节点的右子树不空，则右子树上所有节点的key值均大于它的根节点的值；
3：任意节点的左、右子树也分别为二叉查找树；
4：没有键值相等的节点。

以下内容实现二叉搜索树的搜索，插入，删除
searchBFS(bitTree T,int key,bitTree F,bitTree* P)
T:树
key：查找关键字
F：搜索过程中当前子树父亲节点
P:插入前搜索是否存在数据，存在不插入，不存在通过该指针获取插入位置直接插入

int searchBFS(bitTree T,int key,bitTree F,bitTree* P)
{
    if(!T)//树为空
    {
        *P=F;//返回父节点
        return 0;//没找到
    }
    else
    {
        if(T->data==key)
        {
            *p=T;
            return 1;
        }
        else if(T->data<key)
        {
           return searchBFS(T->rchild,key,T,*P);
        }else if(T->data>key)
        {
           return searchBFS(T->lchild,key,T,*P);
        }
    }
}

int insertBST(bitTree* T,int key)
{
    bitTree P,s;
    int i=searchBFS(*T,key,NULL,&P)//&这个很重要
    //树为空
    if(!T)
    {
        return 0;
    }
    if(i==0)//树中不存在数据根据搜索返回数据直接插入此时P是父节点
    {
        s=(bitTree)malloc(sizeof(bitNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!P)//空树
        {
            *T=s;
        }
        else if(P->data>key)
        {
            P->lchild=s;
        }
        else if(P->data<key)
        {
            P->rchild=s;
        }
        return 1;
    }
    //树中已存在数据
    else return 0;

}

/**
1:叶子结点-直接删除
2:节点只有左孩子、右孩子-让该节点父节点指向左孩子、右孩子
    （其实1可以由2,3代替，因为2,3一起就包括了左右子树都不存在的情况，其中2,3指向的左右子树为NULL就是1情况）
3:节点有左右孩子
 1、找到该节点的右子树中的最左孩子（也就是右子树中序遍历的第一个节点）
 2、把它的值和要删除的节点的值进行交换
 3、然后删除这个节点即相当于把我们想删除的节点删除了，返回true；
*/
int delectBST(bitTree *T,int key)//找到节点
{
    if(!T) return 0;
    else
    {
        if(T->data==key)
        {
            deletekey(T);
        }
        else if(T->data<key)
        {
            DeleteBST(T->rchild, key);
        }
        else if(T->data>key)
        {
            DeleteBST(T->lchild, key);
        }
    }
}
int delectkey(bitTree *T)//删除节点
{
    bitTree q,f;
    if(!T)return 0;
    if(!(T->lchild))
    {
        q=T;
        T=T->rchild;
        free(q);
    }
    else if(!T->rchild)
    {
        q=T;
        T=T->lchild;
        free(q);
    }
    else
    {
        f=T;
        q=T->rchild;
        while(q->lchild)//找到该节点的右子树中的最左孩子
        {
            f=q;//f为q父节点 f比q大
            q=q->lchild;
        }
        T->data=q->data;//把它的值和要删除的节点的值进行交换
        if(f!=T)f->lchild=q->rchild;//q的右子树接到q父节点的左子树上
        else f->rchild=q->rchild;//T只有右子树
        free(q);
    }
    return 1;

}

每个节点都带有颜色属性的二叉查找树，颜色为 红色 或 黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。