sponsored links

算法设计

一、数据结构

0. 基础结构(百科之)

array / 数组 / 索引数组
map / 映射 / 关联数组
multimap / 多重映射
set / 集
multiset / 多重集
hash / 哈希表 / 散列表
列表:数组、链表、队列、栈

1. 跳跃列表

跳跃列表是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间),并且对并发算法友好。
基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。

跳跃列表不提供绝对的最坏情况性能保证,但是在实际中它工作的很好,随机化平衡方案比在平衡二叉查找树中用的确定性平衡方案容易实现;跳跃列表在并行计算中也很有用,这里的插入可以在跳跃列表不同的部分并行的进行,而不用全局的数据结构重新平衡。

1. 平衡二叉树/AVL树

平衡二叉树(Balanced Binary Tree)又被称为AVL树。

性质:
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

2. 二叉搜索树

二叉搜索树(Binary Search Tree)又称为二叉查找树或二叉排序树。

性质:
二叉搜索树,或者是一棵空树,或者是具有下列性质的二叉树:
1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 
2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 
3、它的左、右子树也分别为二叉排序树。

平衡二叉搜索树

平衡二叉搜索树指:该二叉树既是二叉搜索树也是平衡二叉树。

操作效率:
对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。



2. B-树/B树

B-树是一种多路搜索树。适用于外查找,因为:二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下,而B-树是一种平衡的多叉树。

性质:
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树(m>=3),深度为m。它或者是空树,或者是满足下列性质的树:
1、根结点至少有两个子女;
2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;其中┌m/2┐表示对m/2向上取整
3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:┌m/2┐ <= j <= m ;
4、所有的叶子结点都位于同一层。
在B-树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

从另一个角度理解性质:
1.定义任意非叶子结点最多只有M个儿子;且M>2;
2.根结点的儿子数为[2, M];
3.除根结点以外的非叶子结点的儿子数为[M/2, M];
4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字,根节点至少一个关键字);
5.非叶子结点的关键字个数=指向儿子的指针个数-1;
6.非叶子结点的关键字:K[1], K[2], …, K[m-1],m<=M;且K[i]< K[i+1] ;
7.非叶子结点的指针:P[1], P[2], …, P[m];其中P[1]指向关键字小于K[1]的子树,P[m]指向关键字大于K[m-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
8.所有叶子结点位于同一层;

操作效率:
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最低搜索性能为:O(log2(N))
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作;
参考:http://blog.csdn.net/v_july_v/article/details/6530142

3. B+树

B+树是应文件系统所需而出的一种B-树的变型树。

性质:
一棵m阶的B+树和m阶的B-树的差异在于:
1.有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。
通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

操作效率:
相对于B数,B+-tree的磁盘读写代价更低,B+-tree的查询效率更加稳定;
数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。
参考:http://blog.csdn.net/v_july_v/article/details/6530142 

B*树

B*树是在B+树的基础上,在非根和非叶子结点中再增加指向兄弟的指针。
B*树分配新结点的概率比B+树要低,空间使用率更高。但在实践中的应用不足。

5. R树

R树是目前应用最为广泛的一种空间索引结构。
R树是一个高度平衡树,它是B树在k维上的自然扩展,用空间对象的MBR(Minimal Bounding Rectangle)来近似表达空间对象,根据地物的MBR建立R树,可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点都对应着磁盘页D和区域I,如果结点不是叶结点,则该结点的所有子结点的区域都在区域I的范围之内,而且存储在磁盘页D中。如果结点是叶结点,那么磁盘页D中存储的将是区域I范围内的一系列子区域,子区域紧紧围绕空间对象,一般为空间对象的外接矩形。

1. 除非它是根结点之外,所有叶子结点包含有m至M个记录索引(条目)。作为根结点的叶子结点所具有的记录个数可以少于m。通常,m=M/2。
2. 对于所有在叶子中存储的记录(条目),I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(注意:此处所说的“矩形”是可以扩展到高维空间的)。
3. 每一个非叶子结点拥有m至M个孩子结点,除非它是根结点。
4. 对于在非叶子结点上的每一个条目,i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形(同性质2)。
5. 所有叶子结点都位于同一层,因此R树为平衡树。

操作效率:
R树是一种能够有效进行高维空间搜索的数据结构,它已经被广泛应用在各种数据库及其相关的应用中。但R树的处理也具有局限性,它的最佳应用范围是处理2至6维的数据,更高维的存储会变得非常复杂,这样就不适用了。
R树兄弟结点对应的空间区域可以重叠,可以较容易地进行插入和删除操作。R树的查询效率会因重叠区域的增大而大大减弱,在最坏情况下,其时间复杂度甚至会由对数搜索退化成线性搜索。

R+树

R树的变种之一,在R+树中,兄弟结点对应的空间区域没有重叠。
因此对于点查询,查询路径可以只有一条,克服了R树中多路查询的问题。对于区域查询,查询的效率也可以得到提高。
存在的主要问题是:结点分裂操作复杂,且可能向上级结点或者下级结点蔓延,这就导致了结点分裂的增加和目录的多次重复存储,除了存储空间开销大之外,树的深度也会增加,这就影响了查找的性能;同时由于在插入和删除空间对象时要保证兄弟结点对应的空间区域不重叠,而使插入和删除操作的效率降低。

R*树

R*树是最有效的R树变种之一,它能对覆盖区域、重叠面积和边界周长进行启发式地优化,并通过重新插入节点重建R树以提高其性能。(但重新插入这个过程相当繁琐,其实现过程太过漫长)
参考:http://studenthu.blog.163.com/blog/static/7403856020102193553356/ 

5. 红黑树

红黑树是一种自平衡二叉查找树,典型的用例是在STL中用于set、map等的内部实现的关联数组。
它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。它的统计性能要好于平衡二叉树。

性质:
红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因而,红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。
红黑树是 2-3-4树的一种等同,这意味着它们是等价的数据结构。换句话说,对于每个 2-3-4 树,都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具。但 2-3-4 树在实践中不经常使用。

操作效率:
在插入和删除之后,红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次,但是它导致了非常复杂的操作。
参考:http://blog.csdn.net/v_july_v/article/category/774945

2-3-4树

2-3-4 树在计算机科学中是阶为 4 的B树。大体上同B树一样,2-3-4 树是可以用做字典的一种自平衡资料结构。
2-3-4 树在多数程式语言中实现起来相对困难,因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些,所以可以用它来替代。


二、查找排序算法

1.二分查找

int SearchBin(int *a,int n,int v)
{
    //查找成功返回下标,否则返回-1
    int low=0;
    int high=n-1;
    int mid;
    while(low<=high) //必须有等号,防止漏掉最后一个
    {
        mid=(low+high)/2;
        if(a[mid]==v)return mid;
        if(a[mid]<v)low=mid+1;
        else high=mid-1; //+1,-1是关键,防止死循环
    }
    return -1;
}

2.插入排序

说明:时间复杂性最好为O(n),平均为O(n^2),最坏为O(n^2);稳定排序;
当序列基本有序或局部有序时效率非常高,对于n不是很大的随机数据,速度表现也很好(速度优于冒泡和选择),故工程实现上一般都采用快排+插入结合(可参考STL的sort函数实现);
和选择排序对比:
选择排序最好的时间复杂度也为O(n^2),但其移动次数是最少的,故随机数据时的实际表现会优于冒泡排序;但从速度表现上来讲,不如插入排序(n不是很大);而且选择排序是不稳定算法;总结:只适用于对移动次数有特殊要求的少数特定情况;
void InsertSort(int *a,int n)
{
    int i,j,t;
    for(i=1; i<n; i++)
    {
        for(j=i; j>0; j--)
        {
            if(a[j-1]<=a[j])break;
            t=a[j];
            a[j]=a[j-1];
            a[j-1]=t;
        }
    }
}

3.起泡排序

说明:时间复杂度最好为O(n),平均为O(n^2),最坏为O(n^2);稳定排序;
适用场景和插入排序类似,但是实际表现比插入排序略逊;
从工程实用角度来讲,是比较鸡肋的算法,但是有些人认为该算法实现简单而钟情,另外,笔试面试也比较钟情该算法。
void BubbleSort(int *a,int n)
{
    int i,j,t;
    bool nochg;
    for(i=n-1; i>0; i--)
    {
        nochg=true;
        for(j=0; j<i; j++)
        {
            if(a[j]>a[j+1])
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                nochg=false;
            }
        }
        if(nochg)break;
    }
}

4.快速排序

说明:时间复杂度最好和平均都是O(n*log(n)),最差为O(n^2);不稳定排序;
当序列正序或逆序时,快速排序退化到O(n^2),但实际情况比较少发生,而且也可以简单通过选取中间位置元素做基准值来解决:交换中间位置和首位置的元素后,再取首位置元素做基准值;而且早已经有对随机取基准值的研究和既成的比较高效算法,可以保证快速排序的表现稳定在O(n*log(n));
对于随机数据情况,快速排序的表现十分优异,在所有O(n*log(n))级别的排序算法中是实际表现最好的,也就是C*n*log(n)的常数系数C低于其他算法。
和堆排序对比:
堆排序的最好、平均、最差时间复杂度都是O(n*log(n));不稳定排序;一般情况下排序表现都不如快速排序,但在部分排序时有自己的独特优势;

int inline Partition(int *a,int low,int high)
{
    int midv=a[low]; //以第一个元素(记为midv)将数组a分成两部分,在midv所在位置之前的元素均小于等于midv,而它之后的元素均大于等于midv,返回midv的位置。
    while(low<high)
    {
        while(low<high&&a[high]>=midv)high--; //必须带等号,否则有等于midv值的元素时会死循环
        a[low]=a[high];
        while(low<high&&a[low]<=midv)low++;
        a[high]=a[low];
    }
    a[low]=midv; //此时low==high
    return low;
}


void QSort(int *a,int low,int high)
{
    if(low<high) //至少2个才排序
    {
        int mid=Partition(a,low,high);
        QSort(a,low,mid-1);
        QSort(a,mid+1,high);
    }
}

5.归并排序

说明:最好、平均、最坏情况的时间复杂度都是O(n*log(n));需要O(n)的辅助空间;稳定排序;
n很大时,稳定排序的首选算法;也是工程实现稳定排序时采用的算法,例如STL的stable_sort就是使用归并排序+插入排序实现;
//合并a[low, mid]和a[mid+1, high]两个有序队列
void inline Merge(int *a,int low,int mid,int high)
{
    int i=low,j=mid+1,k=0,*b=new int[high-low+1]; //递归中使用动态内存分配可能会效率不高,也可以考虑使用传参来指定附加的数组空间
    while(i<=mid&&j<=high)
    {
        if(a[i]<=a[j])b[k++]=a[i++]; //等号保持了稳定性
        else b[k++]=a[j++];
    }
    if(i>mid)
    {
        while(j<=high)b[k++]=a[j++];
    }
    else
    {
        while(i<=mid)b[k++]=a[i++];
    }
    for(k=low; k<=high; k++)
    {
        a[k]=b[k-low];
    }
    delete []b;
}

//典型的分治法模式
void MSort(int *a,int low,int high)
{    
    if(low<high) //至少2个才排序
    {
        int mid=(low+high)/2;
        MSort(a,low,mid); //mid的位置是在当前的MSort()调用中还是下一个Msort()调用中,会影响Merge()函数的调用方式
        MSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}

//非递归的归并排序算法
void MergeSort(int *a, int n) {
    int step, i;
    for (step = 1; step < n; step *= 2) { //step=1,2,4,8...分别是对2个、4个、8个、16个相邻的为一组进行排序(每组分为前后两个有序的子文件使用归并排序),故循环的退出条件:(step*=2)>=n时,实际上数组刚刚对2*step>n个元素进行了排序
        for (i = 0; i + 2 * step -1 < n; i += 2 * step)
            Merge(a, i, i + step - 1, i + 2 * step - 1);
        if (i + step < n) //尚有两个子文件,其中后一个长度小于step
             Merge(a, i, i + step - 1, n - 1);
        //else: 只剩余1个长度小于等于step的子文件,故该子文件本身就是有序的,无需Merge
    }
}


三、分治法

基本思想:
1, 将原问题分解为规模更小的子问题.   ---算法设计
2, (递归)求解子问题.   ---实现功能的递归函数
3, 将子问题的解合并得到原问题的解.   ---合并函数

算法结构示意:

int Merge(int rst1, int rst2){
    //合并rst1和rst2的结果
    return xxx;
}

int Divide_and_conquer(int n){
    if(n <= BOUNDARY){
        //小于边界值,则直接求解结果
        return xxx;
    }
    int rst1, rst2;
    rst1 = Divide_and_conquer(n1); //分解求更小规模的n1解
    rst2 = Divide_and_conquer(n2); //分解求更小规模的n2解
    return Merge(rst1, rst2);
}



四、动态规划

基本思想:一般用于求解最优解问题.
1, 设计最优解结构,即确定记录表的结构和表中每项的意义(一般即为最优值),从而确定表中每项求解的递归式.
2, 自底向上递归求解,把所解子问题的结果填入表中.
3, 表中所得数据即为最优值,通过对表中的信息进一步处理可以获得最优解.

//0-1背包问题实例:

//求解可装的最大的物品价值
void Knapsack(int *v,int *w,int c,int n,int **m)
{
//v[]为物品价值,w[]为物品重量,c为背包容量,n为物品个数
//m[i][j]表示背包容量为j,可选物品为i,i+1,...,n时该问题的最优值
//    求解m[i][j]的递推公式如下:
//    m[i][j]=max{m[i+1][j],m[i+1][j-w[i]]+v[i]}     j>=w[i]
//    m[i][j]=m[i+1][j]                              j<w[i]&&j>=0
//    (初始值;当i=n时,若j>=w[n]则m[i][j]=v[n];否则m[i][j]=0.)
    int i,j;
    for(j=0; j<=c; j++) //初始化m[n][0-c]
    {
        if(j>=w[n])m[n][j]=v[n];
        else m[n][j]=0;
    }
    for(i=n-1; i>=1; i--) //对i从n-1到1求解
    {
        for(j=0; j<=c; j++) //使用递推公式计算m[i][0-c]的值
        {
            if(j>=w[i])
            {
                m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
            }
            else m[i][j]=m[i+1][j];
        }
    }
}

//求解最优解所装的物品
void Traceback(int **m,int *w,int c,int n,int *x)
{
    //x[]存储最优解,X[i]使用0和1表示第i个物品是否被装入包中(1<=i<=n)
    int i;
    for(i=1; i<n; i++)
    {
        if(m[i][c]==m[i+1][c])x[i]=0;
        else
        {
            x[i]=1;
            c-=w[i];
        }
    }
    if(m[n][c]>0)x[n]=1; //i=n时单独处理
    else x[n]=0;
}


五、贪心算法

贪心算法总是自顶向下地进行迭代,通过当前状态下的某种意义的最好选择来将问题转化成规模更小的子问题.

六、回溯法

回溯法在包含所有解的解空间树中,按照深度优先的策略,从根结点出发搜索整个解空间树.
往往用于找出解空间树中满足约束条件的所有解。

//n后问题实例:

//已经放置k-1个皇后,尝试放置第k个皇后(在k行x[k]列上),测试是否可行
bool Place(int *x,int k)
{
    int i;
    for(i=1; i<k; i++) //测试前k-1个位置是否与第k个位置冲突
    {
        if(x[i]==x[k] || x[k]-x[i]==k-i || x[i]-x[k]==k-i)return false;
    }
    return true;
}

//问题是求解n个皇后在n*n的键盘中的无冲突位置,已经摆放了k个皇后,在x[i]中保存了第i行的列位置(1<=i<=k)。注意x中是从1开始保存,长度为k+1
void QBacktrack(int *x,int n,int k)
{
    int i;
    if(k>=n) //找到一组解则打印出来
    {
        for(i=1; i<=n; i++)
        {
            cout<<x[i]<<' ';
        }
        cout<<endl;
    }
    else
    {
        for(i=1; i<=n; i++) //放置第k+1行的位置,尝试每一列
        {
            x[k+1]=i;
            if(Place(x,k+1))QBacktrack(x,n,k+1);
        }
    }
}


七、分支限界法

分支限界法是以广度优先或以最小耗费优先的方式搜索整个解空间树.(此方式便于使用剪枝函数缩小下一层的搜索范围)
往往用于找出解空间树中满足约束条件的一个解,或者在满足约束的解中找出最优解.
基本思想:
1. 初始化活结点表,加入解空间树的根节点。
2. 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。
3. 在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。
4. 从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。
5. 找到所需的解或活结点表为空时停止2-4步的循环。

//0-1背包问题实例:

//计算当前节点的总价值和总重量
inline void calVW(int* v, int* w, int level, int num, int* cv, int* cw)
{
    cv[0] = 0;
    cw[0] = 0;
    while(--level)
    {
        if(num&0x1)  //左孩子
        {
            cv[0] += v[level];
            cw[0] += w[level];
            num = (num+1)/2;
        }
        else
        {
            num = num/2;
        }
    }
}

//根据当前节点填充解
inline void getBag(int level, int num, int n, int* idx, int* x)
{
    int i = level;

    while(--i)
    {
        if(num&0x1)  //左孩子
        {
            x[idx[i]] = 1;
            num = (num+1)/2;
        }
        else
        {
            x[idx[i]] = 0;
            num = num/2;
        }
    }
    for(i=level; i<=n; i++)
    {
        x[idx[i]] = 0;
    }
}

//剪枝函数,(level,num)为尝试扩展的节点
inline bool bound(int *v,int *w, double *vpw,int c,int n, int level, int num, int cv, int cw, int maxv)
{
    //限界
    if(level > n+1) return false; //超出解空间树
    if(num&0x1 && cw+w[level-1]>c) return false; //左孩子并且加入后超重

    double cwd = num&0x1 ? cw+w[level-1] : cw;
    double cvd = num&0x1 ? cv+v[level-1] : cv;
    //剪枝,排除剩余的按贪心算法装满后也达不到最大值的情况
    for(int i=level; i<=n; i++)
    {
        if(cwd+w[i]<=c+0.5)  //浮点数和整数比较有误差
        {
            cwd += w[i];
            cvd += v[i];
        }
        else    //装一部分
        {
            cvd += v[i]*((c-cwd)/w[i]);
            break;
        }
    }
    return (cvd > maxv);
}

//分支限界法求解0-1背包问题
int Knapsack(int *_v,int *_w,int c,int n,int* x)
{
    //v[]为物品价值,w[]为物品重量,c为背包容量,n为物品个数
    //解空间树为左子树表示装入该节点,右子树不表示装入该节点;每层表示一个物品;
    //解空间构成了一个n+1层的满二叉树,而每个叶子节点表示一种可能解;
    //对每个节点从上至下,从左至右开始编号(层和节点均从1开始编号),第i层第k个节点编号(i,k),则其父节点为:(i-1,k%2?(k+1)/2:k/2),其左孩子为(i+1,2k-1),右孩子为(i+1,2k)
    double* vpw = new double[n+1]; //保存单位价值
    int* idx = new int[n+1]; //保存指针,用于在求解后还原背包中的物品;现在第i个位置保存的是第idx[i]个物品
    int* v = new int[n+1]; //保存_v和_w的值,因为需要调整物品顺序
    int* w = new int[n+1];
    int i, j, t;
    double td;
    int nNode_level; //当前处理的节点,记录层数
    int nNode_num; //当前处理的节点,记录在该层的位置
    int cv = 0, cw = 0; //当前价值和重量
    int maxv = 0, maxNode_level = 1, maxNode_num; //最大价值和对应的节点,maxNode_level初始化为1对应无解情况,参见getBag()
    queue<int> activeNodes_level; //活动节点表,记录层数
    queue<int> activeNodes_num; //活动节点表,记录在该层的位置

    //初始化,将物品按照最大单位价值降序排列
    for(i=1; i<=n; i++)
    {
        v[i] = _v[i];
        w[i] = _w[i];
        vpw[i] = 1.0*v[i]/w[i];
        idx[i] = i;
    }
    for(i=2; i<=n; i++) //插入排序
    {
        for(j=i; j>1; j--)
        {
            if(vpw[j]>vpw[j-1])
            {
                td = vpw[j];
                vpw[j] = vpw[j-1];
                vpw[j-1] = td;
                t = idx[j];
                idx[j] = idx[j-1];
                idx[j-1] = t;
                t = v[j];
                v[j] = v[j-1];
                v[j-1] = t;
                t = w[j];
                w[j] = w[j-1];
                w[j-1] = t;
            }
            else
            {
                break;
            }
        }
    }

    activeNodes_level.push(1);
    activeNodes_num.push(1);
    while(!activeNodes_level.empty())
    {
        nNode_level = activeNodes_level.front();
        nNode_num = activeNodes_num.front();
        calVW(v, w, nNode_level, nNode_num, &cv, &cw);

        if(cv > maxv)  //找到一个新的最大值,记录下来
        {
            maxv = cv;
            maxNode_level = nNode_level;
            maxNode_num = nNode_num;
        }
        if(bound(v, w, vpw, c, n, nNode_level+1, nNode_num*2-1, cv, cw, maxv))  //左孩子
        {
            activeNodes_level.push(nNode_level+1);
            activeNodes_num.push(nNode_num*2-1);
        }
        if(bound(v, w, vpw, c, n, nNode_level+1, nNode_num*2, cv, cw, maxv))  //右孩子
        {
            activeNodes_level.push(nNode_level+1);
            activeNodes_num.push(nNode_num*2);
        }
        activeNodes_level.pop(); //弹出队首节点
        activeNodes_num.pop();
    }

    //记录解
    getBag(maxNode_level, maxNode_num, n, idx, x);

    delete []vpw;
    delete []idx;
    delete []v;
    delete []w;

    return maxv;
}



2. B-树/B树


3. B+树


4. 2-3-4树

2-3-4 树在计算机科学中是阶为 4 的B树。大体上同B树一样,2-3-4 树是可以用做字典的一种自平衡资料结构。
2-3-4 树在多数程式语言中实现起来相对困难,因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些,所以可以用它来替代。

Tags: