devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构精录&总结Episode.10 数据结构入门之高级数据结构（基于Visual C++）

作者：很楠不爱3 | 2024-05-31 20:24:51

赞

踩

数据结构精录&总结Episode.10 数据结构入门之高级数据结构（基于Visual C++）

这是。。数据结构入门精录总结的最后一篇文章。我大致使用了十篇篇幅，一百个不同的函数等总结了整个数据结构课程的所有知识点和C实现，更重要的是，如果让所有的学科都能免去数百页的冗长的教材，也不流于简单的放挂科教程的应试形式，是一件极其有意义的事情。但这很难，至少这段时间这些乱七八糟的事情直接导致了我某课程大作业汇报的当场爆炸。

对于一个从不玩游戏的人，疫情在家学习的这种日子怎么熬过去呢？有些时候我也无奈，我也无聊。汉景帝为平七国之乱，不得不杀了晁错；光武帝刘秀为了复兴汉室，连自己度兄长被杀也要忍耐，甚至为了稳定朝内政，都不能册封自己心爱的阴丽华为皇后，只能封郭氏女，但这之后，也是他们平定天下开创盛世。【P.S.摘自甄嬛传】

数据结构结束后我大致会规划FPGA芯片开发的程序（VerilogHDL）、硬件芯片电路设计的总结内容。只是时间很紧凑，还有半个多月就要考数电系统期末了，巨顶。

所谓高级数据结构，哪里是一篇CSDN博文能够讲完的呢？不过依据信息论编码课程的一些应用，加上我们课程学习的知识，以下总结了一些非计算机专业的同学时常会用到并且意义非凡的数据结构&算法，详细内容分为并查集、优先队列、B-树、B+树、红黑树几个部分。这几种进阶数据结构在之前的文章中也初有涉及。

一、并查集：

1、定义：

并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构。

2、操作：

合并(Union/Merge)：合并两个集合。
查询(Find/Get)：查询元素所属集合。
实际操作时，我们会使用一个点来代表整个集合，即一个元素的根结点(可以理解为父亲)。

3、算法描述：

我们建立一个数组fa[ ]或pre[ ]表示一个并查集，fa[i]表示i的父节点。
初始化：每一个点都是一个集合，因此自己的父节点就是自己fa[i]=i
查询：每一个节点不断寻找自己的父节点，若此时自己的父节点就是自己，那么该点为集合的根结点，返回该点。
修改：合并两个集合只需要合并两个集合的根结点，即fa[RootA]=RootB，其中RootA,RootB是两个元素的根结点。

路径压缩：
实际上，我们在查询过程中只关心根结点是什么，并不关心这棵树的形态(有一些题除外)。因此我们可以在查询操作的时候将访问过的每个点都指向树根，这样的方法叫做路径压缩，单次操作复杂度为O(logN)O(logN)。
结合下图食用更好(图为状态压缩的过程)：

4、特点附录：

并查集在Java的程序设计里面用的其实比C更多，它的使用范围可以参考以下问题（总结来源于@super_chris）：

①问题的开始 所有元素之间是没有关系的

②随着问题的进行 元素之间不断地集合在一起，变成新的集合

 

二、优先队列（堆）：

1、定义：

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

2、操作：

优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行。

优先级队列必须至少支持以下操作：

is_empty：检查队列是否没有元素。

insert_with_priority：使用关联的优先级向队列添加元素。

pull_highest_priority_element：从队列中删除具有最高优先级的元素，并将其返回。

这也称为“pop_element（Off）”，“get_maximum_element”或“get_front（most）_element”。

一些约定颠倒了优先级的顺序，将较低的值视为较高的优先级，因此这也可称为“get_minimum_element”，并且在文献中通常称为“get-min”。

这可以替代地被指定为单独的“peek_at_highest_priority_element”和“delete_element”函数，其可以被组合以产生“pull_highest_priority_element” [1]  。

此外，peek（在此上下文中通常称为find-max或find-min）返回最高优先级元素但不修改队列，它经常被实现，并且几乎总是在O（1）时间内执行。此操作及其O（1）性能对于许多优先级队列应用程序至关重要。

更高级的实现可能支持更复杂的操作，例如pull_lowest_priority_element，检查前几个最高或最低优先级元素，清除队列，清除队列子集，执行批量插入，将两个或多个队列合并为一个，增加优先级任何元素等。

3、区分优先队列与队列：

可以将优先级队列想象为已修改的队列，但是当一个人从队列中获取下一个元素时，将首先检索优先级最高的元素。

堆栈和队列可以被建模为特定类型的优先级队列。提醒一下，堆栈和队列的行为方式如下：

堆栈 - 元素以最后一个顺序被拉入（例如，一叠纸）

队列 - 元素先进先出（例如，自助餐厅中的一条线）

在堆栈中，每个插入元素的优先级是单调递增的;因此，插入的最后一个元素始终是第一个检索的元素。在队列中，每个插入元素的优先级是单调递减的;因此，插入的第一个元素始终是第一个检索到的元素。

4、算法图示：

 

三、B树以及B树的家庭成员：

1、B树总体简介（感谢参考@小小少年Boy的总结）：

利用平衡树的优势加快查询的稳定性和速度；
B+树的数据都存储在叶子结点中，分支结点均为索引，查询时只需要扫描叶子节点，常用于数据库索引；

B树其分支结点和叶子节点都存储着数据，查询时需要进行一个遍历，常用于文件索引；

B树和B+树区别：
关键字数量不同：B+树分支结点M个关键字，叶子节点也有M个；B树分支结点则存在 k-1 个关键码
数据存储位置不同：B+树数据存储在叶子结点上；B树存储在每个结点上；
查询不同：B+树是从根节点到叶子节点的路径；B树是只需要找到数据就可以
分支节点存储信息不同：B+树存索引信息；B树存的是数据关键字

小结：
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树： 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

2、B树的特点：

B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的，查询的时间复杂度时long2(n)；
其次是构造一个多阶B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息；
总结：利用平衡树的优势加快查询的稳定性和速度。

3、B树的操作：

插入：新结点一般插在第h层，通过搜索找到对应的结点进行插入，那么根据即将插入的结点的数量又分为下面几种情况。

  • 如果该结点的关键字个数没有到达m-1个，那么直接插入即可；
  • 如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

删除：

同样的，我们需要先通过搜索找到相应的值，存在则进行删除，需要考虑删除以后的情况，

  • 如果该结点拥有关键字数量仍然满足B树性质，则不做任何处理；
  • 如果该结点在删除关键字以后不满足B树的性质（关键字没有到达ceil(m/2)-1的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况。
    • 如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
    • 如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为ceil(m/2)-1，借的一方的关键字数量为ceil(m/2)-2的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；
  • 其余情况参照BST中的删除。

4、有关B-树的具体内容：

B-树是一种多路搜索树（并不是二叉的）：
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]；且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.所有叶子结点位于同一层；

 

B-树的搜索：

从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

 

B-树的特性：
1.关键字集合分布在整棵树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；

5、有关B+树的具体内容：

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；

 

B+的搜索：

与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

 

B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；

6、对比B-和B+树：

这都是由于B+树和B具有这不同的存储结构所造成的区别，以一个m阶树为例。

  1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。
  2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
  3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
  4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

以下是一个B树生成网站，可以根据用户键入的B树来生成对应的图例，可以供理解学习使用：

https://www.cs.usfca.edu/~galles/visualization/BTree.html

 

四、红黑树：

由于前面讲查找树的那一部分的时候已经提到过平衡二叉查找树和红黑树的基本概念，故此处仅介绍大致深入的知识内容。

1、概念：

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

2、算法描述：

红黑树的时间复杂度为: O(lgn)
下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

定理：一棵含有n个节点的红黑树的高度至多为2log(n+1).

证明：
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。
    我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。

    从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明： 
    第1点：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！
    第2点：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点，则可以得出结论"bh(x) >= h/2"。进而，我们只需证明 "高度为h的红黑树，它的包含的黑节点个数至少为 2bh(x)-1个"即可。

    到这里，我们将需要证明的定理已经由
"一棵含有n个节点的红黑树的高度至多为2log(n+1)"
    转变成只需要证明
"高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。


下面通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。

(01) 当树的高度h=0时，
    内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。

(02) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！

    下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。

    当树的高度为 h 时，
    对于节点x(x为根节点)，其黑高度为bh(x)。
    对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。
    根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2bh(x)-1-1 个"；

    所以，节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。
    因此，原命题成立。

    由(01)、(02)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。
    因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

3、算法图例：

关于红黑树的大致操作，可以通过下述代码进行理解，若非计算机专业同学可以忽略，此处便不再费笔墨总结。

上述高级数据结构总结内容的代码对应如下，部分详析已嵌入代码注释中：

  1. // 第十章 高级数据结构.cpp : 此文件不包含 "main" 函数。程序执行将分别在下述的各个cpp中。编写—JoeyBG，算法尚有不足之处，敬请谅解。
  2. //
  3.  
  4. /*
  5. #include <iostream>
  6. #include<algorithm>
  7. #include<math.h>
  8. #include<iomanip>
  9. using namespace std;
  10. */
  11.  
  12. // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
  13. // 调试程序: F5 或调试 >“开始调试”菜单
  14. // 入门使用技巧: 
  15. //   1. 使用解决方案资源管理器窗口添加/管理文件
  16. //   2. 使用团队资源管理器窗口连接到源代码管理
  17. //   3. 使用输出窗口查看生成输出和其他消息
  18. //   4. 使用错误列表窗口查看错误
  19. //   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
  20. //   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
  1. //并查集
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N=100;
  6. int father[N];
  7. int n, m;
  8.  
  9. void Init(int n)//初始化
  10. {
  11.     for(int i=1;i<=n;i++)
  12.         father[i]=i;
  13. }
  14.  
  15. int Find(int x)//找祖宗
  16. {
  17.     if(x!=father[x])
  18.         father[x]=Find(father[x]);
  19.     return father[x];
  20. }
  21.  
  22. int Merge(int a,int b)//合并集合
  23. {
  24.     int p=Find(a);
  25.     int q=Find(b);
  26.     if(p==q) return 0;
  27.     if(p>q)
  28.         father[p]=q;//小的赋值给大的集合号
  29.     else
  30.         father[q]=p;
  31.     return 1;
  32. }
  33.  
  34. int main()
  35. {
  36.     int sum=0,u,v;
  37.     cout<<"输入人数n和亲戚关系数m:"<<endl;
  38.     cin>>n>>m;
  39.     Init(n);
  40.     cout<<"输入有亲戚关系的两个人编号u,v"<<endl;
  41.     for(int i=1;i<=m;i++)
  42.     {
  43.         cin>>u>>v;
  44.         Merge(u,v);
  45.     }
  46.     for(int i=1;i<=n;i++)//测试
  47.         cout<<father[i];
  48.     for(int i=1;i<=n;i++)//输出有多少个家族
  49.         if(father[i]==i)
  50.             sum++;
  51.     cout<<"家族数为："<<sum<<endl;
  52.     return 0;
  53. }
  1. //优先队列（堆）
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. #define maxN 1000
  6. int r[maxN];
  7.  
  8. void Sink(int k,int n)//下沉操作
  9. {
  10.     while(2*k<=n)//如果有左孩子
  11.     {
  12.         int j=2*k;//j指向左孩子
  13.         if(j<n&&r[j]<r[j+1])//如果有右孩子且左孩子比右孩子小
  14.             j++;    //j指向右孩子
  15.         if(r[k]>=r[j])//比较大的孩子大
  16.             break;    //已满足堆
  17.         else
  18.             swap(r[k],r[j]);//与较大的孩子交换
  19.         k=j;//k指向交换后的新位置，继续向下比较，一直下沉到叶子
  20.     }
  21. }
  22.  
  23. void Swim(int k)//上浮操作
  24. {
  25.     while(k>1&&r[k]>r[k/2])//如果大于双亲
  26.     {
  27.         swap(r[k],r[k/2]);//与双亲交换
  28.         k=k/2;//k指向交换后的新位置，继续向上比较，一直上浮到根
  29.     }
  30. }
  31.  
  32. void CreatHeap(int n)//构建初始堆
  33. {
  34.     for(int i=n/2;i>0;i--)//从最后一个分支结点n/2开始下沉调整为堆，直到第一个结点
  35.         Sink(i,n);
  36. }
  37.  
  38. void push(int n,int x)//入队
  39. {
  40.     r[++n]=x;//n加1后，将新元素放入尾部
  41.     Swim(n);//最后一个元素上浮操作
  42. }
  43.  
  44. void pop(int n)//出队
  45. {
  46.     cout<<r[1]<<endl;//输出堆顶
  47.     r[1]=r[n--];//最后一个元素代替堆顶，n减1
  48.     Sink(1,n);//堆顶下沉操作
  49. }
  50.  
  51. int main()
  52. {
  53.     int n,select,x;
  54.     cout<<"请输入待排序记录个数："<<endl;
  55.     cin>>n;
  56.     cout<<"请输入n个整数："<<endl;
  57.     for(int i=1;i<=n;i++)
  58.         cin>>r[i];
  59.     CreatHeap(n);//创建初始堆
  60.     while(true)
  61.     {
  62.         cout<<"请选择数字：1.入队；2.出队；0.退出"<<endl;
  63.         cin>>select;
  64.         switch(select)
  65.         {
  66.             case 1:
  67.                 cout<<"输入入队元素："<<endl;
  68.                 cin>>x;
  69.                 push(n,x);//入队
  70.                 break;
  71.             case 2:
  72.                 pop(n);//出队
  73.                 break;
  74.             case 0:
  75.                 return 0;
  76.         }
  77.     }
  78.     return 0;
  79. }
  1. //B树—btree.h头文件代码
  2. #ifndef _BTREE_H_
  3. #define _BTREE_H_
  4.  
  5. #define T 100
  6. #define BTREE_OK 0
  7. #define BTREE_ERR -1
  8.  
  9. typedef struct btree_node
  10. {
  11.      int key_num;
  12.      int key[2 * T - 1];
  13.      int seek[2 * T];
  14.      int self;
  15.      int parent;
  16. }btree_node;
  17.  
  18. typedef struct btree
  19. {
  20.      struct btree_node *root;
  21.      FILE *fp;
  22. }btree;
  23. int btree_insert(btree *tree, int key);
  24. int btree_split(btree *tree, btree_node *node);
  25. btree_node *btree_search(btree *tree, int key);
  26. btree *btree_create(const char *file);
  27. int btree_delete(btree *tree, int key);
  28. int btree_merge(btree *tree, btree_node *left, btree_node *right, btree_node *parent);
  29. #endif
  1. //B树——btree.c源程序代码
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "btree.h"
  6.  
  7. static int btree_read_disk(btree *tree, int seek, btree_node *node)
  8. {
  9.      if(fseek(tree->fp, seek, SEEK_SET) == -1)
  10.           return BTREE_ERR;
  11.      char *read_buf = calloc(1, sizeof(btree_node));
  12.      if(fread(read_buf, sizeof(btree_node), 1, tree->fp) == -1)
  13.           return BTREE_ERR;
  14.      memcpy(node, read_buf, sizeof(btree_node));
  15.      return BTREE_OK;
  16. }
  17.  
  18. static int btree_write_disk(btree *tree, int seek, btree_node *node)
  19. {
  20.      if(fseek(tree->fp, seek, SEEK_SET) == -1)
  21.           return BTREE_ERR;
  22.      if(fwrite((void *)node, sizeof(btree_node), 1, tree->fp) == -1)
  23.           return BTREE_ERR;
  24.      return BTREE_OK;
  25. }
  26.  
  27. static int btree_key_index(btree_node *node, int key)
  28. {
  29.      int low = 0;
  30.      int high = node->key_num - 1;
  31.      int middle = (low + high) / 2;
  32.      while(low <= high)
  33.      {
  34.           if(node->key[middle] == key)
  35.                return middle;
  36.           else if(node->key[middle] > key)
  37.                high = middle - 1;
  38.           else
  39.                low = middle + 1;
  40.           middle = (low + high) / 2;
  41.      }
  42.      return high + 1;
  43. }
  44.  
  45. static int btree_end_seek_of_file(btree *tree)
  46. {
  47.      if(fseek(tree->fp, 0, SEEK_END) == -1)
  48.           return BTREE_ERR;
  49.      return ftell(tree->fp);
  50. }
  51.  
  52. static void btree_view(btree *tree, btree_node *node)
  53. {
  54.      int i;
  55.      for(i = 0; i < node->key_num; i++)
  56.           printf("key:%d, self:%d, parent:%d, seek[0]:%d\n", node->key[i], node->self, node->parent, node->seek[0]);
  57.      if(node->seek[0] != -1)
  58.      {
  59.           btree_node *child = calloc(1, sizeof(btree_node));
  60.           if(child == NULL)
  61.                return;
  62.           for(i = 0; i < node->key_num + 1; i++)
  63.           {
  64.                if(btree_read_disk(tree, node->seek[i], child) == BTREE_ERR)
  65.                     return;
  66.                btree_view(tree, child);
  67.           }
  68.      }
  69. }
  70.  
  71. static btree_node *btree_node_create()
  72. {
  73.      btree_node *node = malloc(sizeof(btree_node));
  74.      node->self = -1;
  75.      node->parent = -1;
  76.      int i;
  77.      for(i = 0; i < 2 * T - 1; i++)
  78.           node->key[i] = 0;
  79.      for(i = 0; i < 2 * T; i++)
  80.           node->seek[i] = -1;
  81.      node->key_num = 0;
  82.      return node;
  83. }
  84.  
  85. static int btree_successor(btree *tree, btree_node *node, btree_node *successor, int index)
  86. {
  87.      if(node->seek[0] == -1)
  88.           return BTREE_ERR;
  89.      if(btree_read_disk(tree, node->seek[index], successor) == BTREE_ERR)
  90.           return BTREE_ERR;
  91.      while(successor->seek[0] != -1)
  92.           if(btree_read_disk(tree, successor->seek[0], successor) == BTREE_ERR)
  93.                return BTREE_ERR;
  94.      return BTREE_OK;
  95. }
  96.  
  97. btree *btree_create(const char *file)
  98. {
  99.      FILE *fp = fopen(file, "w+");
  100.      if(fp == NULL)
  101.           return NULL;
  102.      btree *tree = calloc(1, sizeof(btree));
  103.      if(tree == NULL)
  104.           return NULL;
  105.      tree->fp = fp;
  106.      tree->root = btree_node_create();
  107.      tree->root->self = 0;
  108.      if(btree_write_disk(tree, tree->root->self, tree->root) == BTREE_ERR)
  109.           return NULL;
  110.      return tree;
  111. }
  112.  
  113. btree_node *btree_search(btree *tree, int key)
  114. {
  115.      btree_node *node = calloc(1, sizeof(btree_node));
  116.      if(node == NULL)
  117.           return NULL;
  118.      *node = *tree->root;
  119.      int key_index = btree_key_index(node, key);
  120.      while(node->seek[0] != -1 && node->key[key_index] != key)
  121.      {
  122.           if(btree_read_disk(tree, node->seek[key_index], node) == BTREE_ERR)
  123.                return NULL;
  124.           key_index = btree_key_index(node, key);
  125.      }
  126.      if(node->key[key_index] == key)
  127.           return node;
  128.      return NULL;
  129. }
  130.  
  131. int main(int argc, char *argv[])
  132. {
  133.      int i;
  134.      btree *tree = btree_create("source");
  135.      for(i = 0; i < 100000; i++)
  136.           btree_insert(tree, i);
  137.      for(i = 0; i < 100000; i++)
  138.           btree_delete(tree, i);
  139.      return 0;
  140. }
  141.  
  142. int btree_insert(btree *tree, int key)
  143. {
  144.      btree_node *node = calloc(1, sizeof(btree_node));
  145.      if(node == NULL)
  146.           return BTREE_ERR;
  147.      *node = *tree->root;
  148.      if(btree_split(tree, node) == BTREE_ERR)
  149.           return BTREE_ERR;
  150.      int key_index = btree_key_index(node, key);
  151.      while(node->seek[0] != -1)
  152.      {
  153.           if(btree_read_disk(tree, node->seek[key_index], node) == BTREE_ERR)
  154.                return BTREE_ERR;
  155.           if(btree_split(tree, node) == BTREE_ERR)
  156.                return BTREE_ERR;
  157.           key_index = btree_key_index(node, key);
  158.      }
  159.      int i;
  160.      for(i = node->key_num; i > key_index; i--)
  161.           node->key[i] = node->key[i - 1];
  162.      node->key[key_index] = key;
  163.      node->key_num++;
  164.      if(btree_write_disk(tree, node->self, node) == BTREE_ERR)
  165.           return BTREE_ERR;
  166.      if(tree->root->self == node->self)
  167.           *tree->root = *node;
  168.      return BTREE_OK;
  169. }
  170.  
  171. int btree_split(btree *tree, btree_node *node)
  172. {
  173.      if(node->key_num < 2 * T - 1)
  174.           return BTREE_OK;
  175.      btree_node *brother = btree_node_create();
  176.      brother->self = btree_end_seek_of_file(tree);
  177.      int save_key = node->key[T - 1];
  178.      int i;
  179.      for(i = T; i < node->key_num; i++)
  180.           brother->key[i - T] = node->key[i];
  181.      if(node->seek[0] != -1)
  182.           for(i = T; i < node->key_num + 1; i++)
  183.           {
  184.                brother->seek[i - T] = node->seek[i];
  185.                btree_node *child = calloc(1, sizeof(btree_node));
  186.                if(child == NULL)
  187.                     return BTREE_ERR;
  188.                if(btree_read_disk(tree, node->seek[i], child) == BTREE_ERR)
  189.                     return BTREE_ERR;
  190.                child->parent = brother->self;
  191.                if(btree_write_disk(tree, child->self, child) == BTREE_ERR)
  192.                     return BTREE_ERR;
  193.           }
  194.      node->key_num = brother->key_num = T - 1;
  195.      btree_node *parent = calloc(1, sizeof(btree_node));
  196.      if(parent == NULL)
  197.           return BTREE_ERR;
  198.      if(node->parent == -1)
  199.      {
  200.           parent = btree_node_create();
  201.           tree->root = parent;
  202.           parent->self = brother->self + sizeof(btree_node);
  203.           node->parent = parent->self;
  204.      }
  205.      else
  206.           if(btree_read_disk(tree, node->parent, parent) == BTREE_ERR)
  207.                return BTREE_ERR;
  208.      int key_index = btree_key_index(parent, node->key[0]);
  209.      for(i = parent->key_num; i > key_index; i--)
  210.           parent->key[i] = parent->key[i - 1];
  211.      parent->key[i] = save_key;
  212.      for(i = parent->key_num + 1; i > key_index + 1; i--)
  213.           parent->seek[i] = parent->seek[i - 1];
  214.      parent->seek[key_index] = node->self;
  215.      parent->seek[key_index + 1] = brother->self;
  216.      parent->key_num++;
  217.      brother->parent = node->parent;
  218.  
  219.      btree_write_disk(tree, parent->self, parent);
  220.      btree_write_disk(tree, brother->self, brother);
  221.      btree_write_disk(tree, node->self, node);
  222.      if(btree_read_disk(tree, tree->root->self, tree->root) == BTREE_ERR)
  223.           return BTREE_ERR;
  224.      *node = *parent;
  225.      return BTREE_OK;
  226. }
  227.  
  228. int btree_delete(btree *tree, int key)
  229. {
  230.      btree_node *node = btree_search(tree, key);
  231.      if(node == NULL)
  232.           return BTREE_ERR;
  233.      int key_index = btree_key_index(node, key);
  234.      if(node->seek[0] != -1)
  235.      {
  236.           btree_node *successor = btree_node_create();
  237.           if(btree_successor(tree, node, successor, key_index + 1) == BTREE_ERR)
  238.                return BTREE_ERR;
  239.           node->key[key_index] = successor->key[0];
  240.           if(btree_write_disk(tree, node->self, node) == BTREE_ERR)
  241.                return BTREE_ERR;
  242.           if(node->self == tree->root->self)
  243.                *tree->root = *node;
  244.           node = successor;
  245.           key_index = 0;
  246.      }
  247.      int i;
  248.      for(i = key_index; i < node->key_num - 1; i++)
  249.           node->key[i] = node->key[i + 1];
  250.      node->key_num--;
  251.      btree_write_disk(tree, node->self, node);
  252.      while(node->key_num < T - 1 && node->self != tree->root->self)
  253.      {
  254.           btree_node *parent = btree_node_create();
  255.           if(btree_read_disk(tree, node->parent, parent) == BTREE_ERR)
  256.                return BTREE_ERR;
  257.           key_index = btree_key_index(parent, node->key[0]);
  258.           if(parent->key_num == key_index + 1 && parent->key[key_index] == node->key[0])
  259.                key_index++;
  260.           btree_node *brother = btree_node_create();
  261.           if(key_index == parent->key_num)
  262.           {
  263.                if(btree_read_disk(tree, parent->seek[key_index - 1], brother) == BTREE_ERR)
  264.                     return BTREE_ERR;
  265.                if(brother->key_num > T - 1)
  266.                {
  267.                     for(i = node->key_num; i > 0; i--)
  268.                          node->key[i] = node->key[i - 1];
  269.                     for(i = node->key_num + 1; i > 0; i--)
  270.                          node->seek[i] = node->seek[i - 1];
  271.                     node->key[0] = parent->key[parent->key_num - 1];
  272.                     node->seek[0] = brother->seek[brother->key_num];
  273.                     if(node->seek[0] != -1)
  274.                     {
  275.                          btree_node *child = btree_node_create();
  276.                          if(btree_read_disk(tree, brother->seek[brother->key_num], child) == BTREE_ERR)
  277.                               return BTREE_ERR;
  278.                          child->parent = node->self;
  279.                          if(btree_write_disk(tree, child->self, child) ==  BTREE_ERR)
  280.                          return BTREE_ERR;
  281.                     }
  282.                     node->key_num++;
  283.                     parent->key[parent->key_num - 1] = brother->key[brother->key_num - 1];
  284.                     brother->key_num--;
  285.                }
  286.                else
  287.                     btree_merge(tree, brother, node, parent);
  288.           }
  289.           else
  290.           {
  291.                if(btree_read_disk(tree, parent->seek[key_index + 1], brother) == BTREE_ERR)
  292.                     return BTREE_ERR;
  293.                if(brother->key_num > T - 1)
  294.                {
  295.                     node->key[node->key_num] = parent->key[key_index];
  296.                     parent->key[key_index] = brother->key[0];
  297.                     node->key_num++;
  298.                     for(i = 0; i < brother->key_num - 1; i++)
  299.                          brother->key[i] = brother->key[i + 1];
  300.                     node->seek[node->key_num] = brother->seek[0];
  301.                     if(node->seek[node->key_num] != -1)
  302.                     {
  303.                          btree_node *child = btree_node_create();
  304.                          if(btree_read_disk(tree, brother->seek[0], child) == BTREE_ERR)
  305.                               return BTREE_ERR;
  306.                          child->parent = node->self;
  307.                          if(btree_write_disk(tree, child->self, child) == BTREE_ERR)
  308.                          return BTREE_ERR;
  309.                     }
  310.                     for(i = 0; i < brother->key_num; i++)
  311.                          brother->seek[i] = brother->seek[i + 1];
  312.                     brother->key_num--;
  313.                }
  314.                else
  315.                     btree_merge(tree, node, brother, parent);
  316.           }
  317.           btree_write_disk(tree, parent->self, parent);
  318.           btree_write_disk(tree, node->self, node);
  319.           btree_write_disk(tree, brother->self, brother);
  320.           if(tree->root->self == parent->self)
  321.                *tree->root = *parent;
  322.           *node = *parent;
  323.      }
  324.      if(tree->root->self == node->self)
  325.           *tree->root = *node;
  326.      return BTREE_OK;
  327. }
  328.  
  329. int btree_merge(btree *tree, btree_node *left, btree_node *right, btree_node *parent)
  330. {
  331.      int key_index = btree_key_index(parent, left->key[0]);
  332.      int save_key = parent->key[key_index];
  333.      int i;
  334.      for(i = key_index; i < parent->key_num - 1; i++)
  335.           parent->key[i] = parent->key[i + 1];
  336.      for(i = key_index + 1; i < parent->key_num + 1; i++)
  337.           parent->seek[i] = parent->seek[i + 1];
  338.      parent->key_num--;
  339.  
  340.      left->key[left->key_num] = save_key;
  341.      left->key_num++;
  342.      for(i = 0; i < right->key_num; i++)
  343.           left->key[i + left->key_num] = right->key[i];
  344.      if(right->seek[0] != -1)
  345.           for(i = 0; i < right->key_num + 1; i++)
  346.           {
  347.                left->seek[i + left->key_num] = right->seek[i];
  348.                btree_node *child = calloc(1, sizeof(btree_node));
  349.                if(child == NULL)
  350.                     return BTREE_ERR;
  351.                if(btree_read_disk(tree, right->seek[i], child) == BTREE_ERR)
  352.                     return BTREE_ERR;
  353.                child->parent = left->self;
  354.                if(btree_write_disk(tree, child->self, child) == BTREE_ERR)
  355.                     return BTREE_ERR;
  356.                free(child);
  357.           }
  358.      left->key_num += right->key_num;
  359.      if(tree->root->self == parent->self && parent->key_num == 0)
  360.      {
  361.           left->parent = -1;
  362.           *tree->root = *left;
  363.      }
  364.      btree_write_disk(tree, parent->self, parent);
  365.      btree_write_disk(tree, left->self, left);
  366.      btree_write_disk(tree, right->self, right);
  367.      return BTREE_OK;
  368. }
  1. //红黑树
  2. #include <vector>
  3. #include <assert.h>
  4. #include <stdio.h>
  5. using namespace std;
  6.  
  7. enum E_COLOR {
  8.     BLACK,
  9.     RED
  10. };
  11.  
  12. struct RBNode {
  13.     RBNode(int k, E_COLOR c) :
  14.         key(k), color(c), p(nullptr), left(nullptr), right(nullptr)
  15.     { }
  16.     RBNode(int k, E_COLOR c, RBNode * ptr1, RBNode * ptr2, RBNode * ptr3) :
  17.         key(k), color(c), p(ptr1), left(ptr2), right(ptr3)
  18.     { }
  19.  
  20.     int key;
  21.     E_COLOR color;
  22.     RBNode * p;
  23.     RBNode * left;
  24.     RBNode * right;
  25. };
  26.  
  27. class RBTree {
  28. public:
  29.     RBTree() {
  30.         NIL = new RBNode(0, BLACK);
  31.         NIL->left = NIL;
  32.         NIL->right = NIL;
  33.         NIL->p = NIL;
  34.  
  35.         root = NIL;
  36.     }
  37.     ~RBTree() {
  38.         Clear();
  39.         delete NIL;
  40.     }
  41.  
  42.     RBNode * FindKey(int key) {
  43.         RBNode * pNode = root;
  44.  
  45.         while (pNode != NIL) {
  46.             if (pNode->key < key) {
  47.                 pNode = pNode->right;
  48.             }
  49.             else if (pNode->key > key) {
  50.                 pNode = pNode->left;
  51.             }
  52.             else {
  53.                 return pNode;
  54.             }
  55.         }
  56.  
  57.         return nullptr;
  58.     }
  59.  
  60.     RBNode * FindInsertPos(int key) {
  61.         RBNode * pNode = root;
  62.         while (pNode != NIL) {
  63.             if (pNode->key < key) {
  64.                 if (pNode->right == NIL) {
  65.                     return pNode;
  66.                 }
  67.                 else {
  68.                     pNode = pNode->right;
  69.                 }
  70.             }
  71.             else if (pNode->key > key) {
  72.                 if (pNode->left == NIL) {
  73.                     return pNode;
  74.                 }
  75.                 else {
  76.                     pNode = pNode->left;
  77.                 }
  78.             }
  79.             else {
  80.                 return NIL;
  81.             }
  82.         }
  83.  
  84.         return NIL;
  85.     }
  86.  
  87.     RBNode * FindDeletePos(int key) {
  88.         RBNode * pNode = root;
  89.  
  90.         while (pNode != NIL) {
  91.             if (pNode->key < key) {
  92.                 pNode = pNode->right;
  93.             }
  94.             else if (pNode->key > key) {
  95.                 pNode = pNode->left;
  96.             }
  97.             else {
  98.                 return pNode;
  99.             }
  100.         }
  101.  
  102.         return NIL;
  103.     }
  104.  
  105.     void InsertKey(int key) {
  106.  
  107.         RBNode * pNode = FindInsertPos(key);
  108.         if (root != NIL && pNode == NIL) {
  109.             return;
  110.         }
  111.         RBNode * new_node = new RBNode(key, RED, NIL, NIL, NIL);
  112.  
  113.         if (pNode == NIL) {
  114.             root = new_node;
  115.         }
  116.         else if (pNode->key < key) {
  117.             pNode->right = new_node;
  118.             new_node->p = pNode;
  119.         }
  120.         else {
  121.             pNode->left = new_node;
  122.             new_node->p = pNode;
  123.         }
  124.  
  125.         InsertAdjust(new_node);
  126.     }
  127.  
  128.     void InsertAdjust(RBNode * cur_node) {
  129.         if (root == cur_node) {
  130.             cur_node->color = BLACK;
  131.             NIL->left = cur_node;
  132.             cur_node->p = NIL;
  133.         }
  134.         else if (cur_node->p->color == RED) {
  135.             RBNode * grandpa = cur_node->p->p;
  136.             RBNode * pa = cur_node->p;
  137.             RBNode * uncle = NIL;
  138.             if (grandpa->left == cur_node->p) {
  139.                 uncle = grandpa->right;
  140.                 if (uncle->color == RED) {
  141.                     pa->color = BLACK;
  142.                     uncle->color = BLACK;
  143.                     grandpa->color = RED;
  144.                     InsertAdjust(grandpa);
  145.                 }
  146.                 else {
  147.                     if (pa->right == cur_node) {
  148.                         left_rotate(pa);
  149.                         pa = cur_node;
  150.                     }
  151.                     right_rotate(grandpa);
  152.                     grandpa->color = RED;
  153.                     pa->color = BLACK;
  154.                 }
  155.             }
  156.             else {
  157.                 uncle = grandpa->left;
  158.                 if (uncle->color == RED) {
  159.                     pa->color = BLACK;
  160.                     uncle->color = BLACK;
  161.                     grandpa->color = RED;
  162.                     InsertAdjust(grandpa);
  163.                 }
  164.                 else {
  165.                     if (pa->left == cur_node) {
  166.                         right_rotate(pa);
  167.                         pa = cur_node;
  168.                     }
  169.                     left_rotate(grandpa);
  170.                     grandpa->color = RED;
  171.                     pa->color = BLACK;
  172.                 }
  173.             }
  174.         }
  175.     }
  176.  
  177.  
  178.  
  179.     RBNode * FindSuccessor(RBNode * z) {  // assume z have right tree
  180.         assert(z->right != NIL);
  181.  
  182.         RBNode * p = z->right;
  183.         while (p->left != NIL) {
  184.             p = p->left;
  185.         }
  186.         return p;
  187.     }
  188.  
  189.     void DeleteKey(int key) {
  190.         RBNode * z = FindDeletePos(key);
  191.         if (z == NIL) return ;
  192.  
  193.         RBNode * y = NIL;
  194.         if (z->left == NIL || z->right == NIL) {
  195.             y = z;
  196.         }
  197.         else {
  198.             y = FindSuccessor(z);
  199.             swap(y->key, z->key);
  200.         }
  201.  
  202.         RBNode * yp = y->p;
  203.         RBNode * ychild = y->left != NIL ? y->left : y->right;
  204.  
  205.         ychild->p = yp;
  206.         if (yp->left == y) {
  207.             yp->left = ychild;
  208.         }
  209.         else {
  210.             yp->right = ychild;
  211.         }
  212.  
  213.         if (yp == NIL) {
  214.             root = ychild;
  215.         }
  216.  
  217.         if (y->color == BLACK)
  218.             DeleteAdjust(ychild);
  219.  
  220.         delete y;
  221.     }
  222.  
  223.     void DeleteAdjust(RBNode *cur_node) {
  224.         if (cur_node == root
  225.             || cur_node->color == RED) {
  226.             cur_node->color = BLACK;
  227.         }
  228.         else {
  229.             RBNode * x = cur_node;
  230.             RBNode * y = x->p;
  231.             if (y->left == x) {
  232.                 RBNode * z = y->right;
  233.                 RBNode * zleft = z->left;
  234.                 RBNode * zright = z->right;
  235.  
  236.                 if (z->color == RED) {
  237.                     left_rotate(y);
  238.                     y->color = RED;
  239.                     z->color = BLACK;
  240.                     DeleteAdjust(x);
  241.                 }
  242.                 else if (zleft->color == BLACK && zright->color == BLACK) {
  243.                     z->color = RED;
  244.                     DeleteAdjust(y);
  245.                 }
  246.                 else if (zleft->color == RED && zright->color == BLACK) {
  247.                     right_rotate(z);
  248.                     zleft->color = BLACK;
  249.                     z->color = RED;
  250.                     DeleteAdjust(x);
  251.                 }
  252.                 else {
  253.                     left_rotate(y);
  254.                     y->color = BLACK;
  255.                     z->color = RED;
  256.                     zright->color = BLACK;
  257.                 }
  258.  
  259.             }
  260.             else {
  261.                 RBNode * z = y->left;
  262.                 RBNode * zleft = z->left;
  263.                 RBNode * zright = z->right;
  264.  
  265.                 if (z->color == RED) {
  266.                     right_rotate(y);
  267.                     y->color = RED;
  268.                     z->color = BLACK;
  269.                     DeleteAdjust(x);
  270.                 }
  271.                 else if (zleft->color == BLACK && zright->color == BLACK) {
  272.                     z->color = RED;
  273.                     DeleteAdjust(y);
  274.                 }
  275.                 else if (zleft->color == BLACK && zright->color == RED) {
  276.                     left_rotate(z);
  277.                     zright->color = BLACK;
  278.                     z->color = RED;
  279.                     DeleteAdjust(x);
  280.                 }
  281.                 else {
  282.                     right_rotate(y);
  283.                     y->color = BLACK;
  284.                     z->color = RED;
  285.                     zleft->color = BLACK;
  286.                 }
  287.             }
  288.         }
  289.     }
  290.  
  291.     void left_rotate(RBNode * x) { // y 是 x 的右孩子
  292.         RBNode * y = x->right;
  293.         RBNode * xp = x->p;
  294.         RBNode * yleft = y->left;
  295.  
  296.         y->p = xp;
  297.         if (xp->left == x) {
  298.             xp->left = y;
  299.         }
  300.         else {
  301.             xp->right = y;
  302.         }
  303.  
  304.         y->left = x;
  305.         x->p = y;
  306.  
  307.         x->right = yleft;
  308.         yleft->p = x;
  309.  
  310.         if (root == x) {
  311.             root = y;
  312.         }
  313.     }
  314.  
  315.     void right_rotate(RBNode * x) { // y是 x的左孩子
  316.         RBNode * y = x->left;
  317.         RBNode * xp = x->p;
  318.         RBNode * yright = y->right;
  319.  
  320.         y->p = xp;
  321.         if (xp->left == x) {
  322.             xp->left = y;
  323.         }
  324.         else {
  325.             xp->right = y;
  326.         }
  327.  
  328.         y->right = x;
  329.         x->p = y;
  330.         x->left = yright;
  331.         yright->p = x;
  332.  
  333.         if (root == x) {
  334.             root = y;
  335.         }
  336.     }
  337.  
  338.     void Output(RBNode * pNode) {
  339.         if (pNode == NIL) return;
  340.  
  341.         Output(pNode->left);
  342.         printf("%d ", pNode->key);
  343.         Output(pNode->right);
  344.     }
  345.  
  346.     void Output() {
  347.         Output(root);
  348.     }
  349.  
  350.     void Clear(RBNode * pNode) {
  351.         if (pNode == NIL) {
  352.             return;
  353.         }
  354.  
  355.         Clear(pNode->left);
  356.         Clear(pNode->right);
  357.         delete pNode;
  358.     }
  359.  
  360.     void Clear() {
  361.         Clear(root);
  362.         root = NIL;
  363.     }
  364.  
  365. private:
  366.     RBNode * root;
  367. private:
  368.     RBNode * NIL;
  369. };
  370.  
  371. int main(int argc, char ** argv) {
  372.     RBTree tree;
  373.     vector<int> vecNum = { 1, 3, 2, 4, 5, 6, 10, 2, 19, -1, 20, 50, 22 };
  374.  
  375.     
  376.     for (int i = 0; i < vecNum.size(); ++i) {
  377.         tree.InsertKey(vecNum[i]);
  378.     }
  379.  
  380.     tree.Output();
  381.     puts("");
  382.  
  383.     for (int i = 0; i < vecNum.size(); ++i) {
  384.         tree.DeleteKey(vecNum[i]);
  385.     }
  386.  
  387.  
  388.     tree.Output();
  389.     puts("");
  390.     tree.DeleteKey(50);
  391.  
  392.     tree.Output();
  393.     puts("");
  394.  
  395.     tree.InsertKey(1000);
  396.     tree.Output();
  397.     puts("");
  398.  
  399.     return 0;
  400. }
  1. /*
  2. 参考文献：
  3. 1、陈小玉：趣学数据结构，人民邮电出版社，2019.09
  4. 2、IT孤独者：红黑树C++ 实现，
  5. https://www.jianshu.com/p/9134a977d532，2017.03
  6. 3、LyleMalik：C语言b树的实现，https://www.cnblogs.com/LyleMalik/archive/2012/12/14/2818040.html，2012.12
  7. */

最后讨论我们C++数据结构课程的第二次大作业，在我们组员开会之后，我们一致认为这个自动生成迷宫是最麻烦的，因为这个东西涉及生成的迷宫能否实际上把路走通。如果是完全随机生成，那么大致有90%的概率会生成一个根本走不通的迷宫，这是我们的为难之处。

于是我找到了我的老同学，交谈一番之后，了解到其实迷宫的自动生成正是可以用先前提到的高级数据结构中的并查集实现。而且，实现迷宫实际上比建立完整的并查集算法还要简单一点，因为所有的数据类似于二进制，没够黑框的是0，有黑框的是1走不通，设计难度反而相对下降了。

以下详细介绍从他那里学到的并查集实现方法：

问题描述：
给定一个n个序列的对象，有两种操作：
     -Union command：连接两个对象；
     -Find/connected query：两个对象是否连接（有路径）
算法实现：
1.用一个数组保存着每个对象所在的connected component，这种方式可以快速进行FIND，但是在union操作时需要遍历整个对象数组
2.利用树的观点，在数组中保存每个对象节点的parent，这个每个connected component就是一棵树，这种方式union很高效，只需要更新相应节点的parent即可，但是在find的时候可能就会遍历整个树，特别是当一棵树比较高的时候。
3.在上述2中实现union(p,q)的时候，我们用一种特定的方式将p所在的树的置为q所在树的孩子，没有考虑到树的大小，就会导致严重失衡的情况。Weighted quick-union 引入一个新的数组来保存每棵树的尺寸，总是将小树链入到大树下，实现相对的平衡。
4.利用path compression进一步对上述算法进行优化，在每一次root操作的时候，不单单只是追溯查询一个节点的根，而是动态的将其根节点往上推进。从而使得component tree 越来越平坦化。如下要查询节点6的根节点，在查询的最后会更新6直接指向根节点。
 

回过头来看，假设在互联网中有两台计算机需要互相通信，那么该怎么确定它们之间是否已经连接起来以确定是否需要架设新的线路连接这两台计算机。这就是动态连通性问题。动态连通性问题在日常生活中十分常见。通过并查集这种数据结构及union-find算法可以解决动态连通性问题，这也是所谓的有路径的迷宫如何自动生成。有一点需要强调：因为我们需要的迷宫有上下左右墙的影响，且行数不能太少。所以创建迷宫规模的时候，强制通过输入x,y和建立2x-1，2y-1规模的迷宫模型来避免一些错误发生。
 

在小组讨论中，我提到了可以用queue和stack头文件完成队列和堆栈的功能，这并不是捷径，而是直接利用已有的东西简化我们的开发步骤。这个头文件包含的实际只是队列和栈的模板，具体的操作还是需要我们自己来写。但是部分诸如指针怎么指，原结构体怎么创建的工作就交给编译器自己完成了。

例如定义一个队列：

queue<(结构体的名字)> （你定义的队列名字）;
queue<node> M;

queue中有几个可以调用的函数，我们直接可以使用:

1、empty(); 如果队列空则返回真
2、push(          （这个里面加入你需要加入的元素或者结构体）         ); 在末尾加入一个元素
3、front(); 返回第一个元素
4、back();返回最后一个元素
5、pop(); 删除第一个元素
6、size();返回队列中元素的个数
一般你定义完一个队列后最好判断一下该队列是否为空，这是empty这个函数的意义所在。

再例如建立一个栈：

stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要
的，在不指定容器类型时，默认的容器类型为deque。具体定义代码如下：

stack<int> s1;
stack<string> s2;

stack 的基本操作有：

s.push(x);    入栈
s.pop();        出栈，注意，出栈操作只是删除栈顶元素，并不返回该元素。
s.top()；      访问栈顶元素
s.empty()， 判断栈空，当栈空时，返回true。
s.size()        访问栈中元素个数

如果没有自动生成迷宫的操作，利用上面两个STL模板库，的确50行就可以完成解迷宫的算法，具体的解迷宫的代码我是从网上找的，粘贴在下面的ubuntu网址中。
https://paste.ubuntu.com/p/fwVncZcVGv/

基于上面的解迷宫方法，再利用前面的自动生成迷宫的算法，以及堆栈队列的STL模板，给出C++版的迷宫游戏如下：

  1. //并查集生成迷宫
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<time.h>
  5. #include<queue>
  6. #include<stack>
  7. using namespace std;
  8. using std::queue;
  9. using std::stack;
  10. typedef struct Point
  11. {
  12.  int x;
  13.  int y;
  14.  int d;//方向 若方向为-1，则表示起点
  15. }Point;
  16. queue<Point> mqueue;
  17. stack<Point> mstack;
  18. Point pos, pos1;
  19. int m, n;//迷宫行（tm-1）/2和列（tn-1）/2
  20. int tm, tn;//实际作图
  21. int x, y, tx1, tx2, ty1, ty2;//点坐标
  22. int d;
  23. int s[10000000];
  24. int maze[1000][1000], mark[1000][1000];//最大迷宫
  25. int sign[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };//上下左右四个方向 0上 1下 2上 3下
  26. Point start;
  27. int Find_x(int x);
  28. void unionSets(int node1, int node2);
  29. void Init();
  30. int getAdd(int x, int y);
  31. void foundpath();
  32. void fixmaze();
  33. int connected(int node1, int node2);
  34. void Findpath();
  35. void changemaze();
  36. int main()
  37. {
  38.  Init();
  39.  cout << "请输入迷宫规模2x-1,2y-1：（x y）" << endl;
  40.  cin >> m >> n;
  41.  tm = m * 2 + 1;
  42.  tn = n * 2 + 1;
  43.  start.x = 1;
  44.  start.y = 1;
  45.  start.d = -1;
  46.  mqueue.push(start);
  47.  for (int i = 0; i < tm; i++)
  48.  {
  49.  for (int j = 0; j < tn; j++)
  50.  {
  51.   maze[i][j] = 1;
  52.   mark[i][j] = 0;
  53.  }
  54.  }
  55.  for (int i = 1; i < tm - 1; i += 2)
  56.  {
  57.  for (int j = 1; j < tn - 1; j += 2)
  58.   maze[i][j] = 0;
  59.  }
  60.  srand(time(NULL));
  61.  foundpath();
  62.  fixmaze();
  63.  cout << "迷宫全图：" << endl;
  64.  for (int i = 0; i < tm; i++)
  65.  {
  66.  for (int j = 0; j < tn; j++)
  67.  {
  68.   if (maze[i][j] == 1)
  69.   cout << "▇";
  70.   else if (maze[i][j] == 0) cout << "□";
  71.  }
  72.  cout << endl;
  73.  }
  74.  Findpath();
  75.  changemaze();
  76.  cout << "找到的通路：“..”表示：" << endl;
  77.  for (int i = 0; i < tm; i++)
  78.  {
  79.  for (int j = 0; j < tn; j++)
  80.  {
  81.   if (maze[i][j] == 1)
  82.   cout << "▇";
  83.   else if (maze[i][j] == 0) cout << "□";
  84.   else if (maze[i][j] == -1) cout << "..";
  85.  
  86.  }
  87.  cout << endl;
  88.  }
  89.  system("pause");
  90.  return 0;
  91. }
  92. int connected(int node1, int node2)
  93. {
  94.  return Find_x(node1) == Find_x(node2);
  95. }
  96. int Find_x(int x)
  97. {
  98.  if (s[x] < 0)
  99.  return x;
  100.  else
  101.  return Find_x(s[x]);
  102.  
  103.  
  104. };
  105. void unionSets(int node1, int node2)
  106. {
  107.  int root1 = Find_x(node1);
  108.  int root2 = Find_x(node2);
  109.  if (root1 == root2)
  110.  return;
  111.  if (s[root2] < s[root1])
  112.  s[root1] = root2;
  113.  else {
  114.  if (s[root1] == s[root2])
  115.   s[root1]--;
  116.  s[root2] = root1;
  117.  }
  118. };
  119. int getAdd(int x, int y)
  120. {
  121.  return (x*tn + y);
  122. };
  123. void Init()
  124. {
  125.  for (int i = 0; i < 10000000; ++i)
  126.  s[i] = -1;
  127. };
  128. void foundpath()
  129. {
  130.  while (connected(getAdd(1, 1), getAdd(tm - 2, tn - 2)) != 1)
  131.  {
  132.  do
  133.  {
  134.   x = rand() % (tm - 2) + 1;
  135.   y = rand() % (tn - 2) + 1;
  136.  } while (maze[x][y] == 0);
  137.  d = x % 2;
  138.  if (d == 0)
  139.  {
  140.   tx1 = x + 1;
  141.   ty1 = y;
  142.   tx2 = x - 1;
  143.   ty2 = y;
  144.   if (connected(getAdd(tx1, ty1), getAdd(tx2, ty2)) != 1)
  145.   {
  146.   maze[x][y] = 0;
  147.   unionSets(Find_x(getAdd(tx1, ty1)), Find_x(getAdd(tx2, ty2)));
  148.   }
  149.  }
  150.  else if (d == 1)
  151.  {
  152.   tx1 = x;
  153.   ty1 = y + 1;
  154.   tx2 = x;
  155.   ty2 = y - 1;
  156.   if (connected(getAdd(tx1, ty1), getAdd(tx2, ty2)) != 1)
  157.   {
  158.   maze[x][y] = 0;
  159.   unionSets(Find_x(getAdd(tx1, ty1)), Find_x(getAdd(tx2, ty2)));
  160.   }
  161.  }
  162.  }
  163. }
  164. void fixmaze()
  165. {
  166.  for (int i = 1; i < tm - 1; i++)
  167.  {
  168.  for (int j = 1; j < tn - 1; j++)
  169.  {
  170.   if (maze[i - 1][j] == 1 && maze[i + 1][j] == 1 && maze[i][j + 1] == 1 &&
  171. maze[i][j - 1] == 1)
  172.   {
  173.   maze[i][j] = 1;
  174.   }
  175.  }
  176.  }
  177.  for (int i = 1; i < tm - 1; i++)
  178.  {
  179.  for (int j = 1; j < tn - 1; j++)
  180.  {
  181.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  182. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  183. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  184.   {
  185.   maze[i][j] = 1;
  186.   }
  187.   if (maze[i - 1][j - 1] == 1 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  188. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  189. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  190.   {
  191.   maze[i][j] = 1;
  192.   }
  193.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 1 && maze[i - 1][j + 1] == 0 &&
  194. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  195. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  196.   {
  197.   maze[i][j] = 1;
  198.   }
  199.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 1 &&
  200. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  201. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  202.   {
  203.   maze[i][j] = 1;
  204.   }
  205.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  206. maze[i][j - 1] == 1 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  207. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  208.   {
  209.   maze[i][j] = 1;
  210.   }
  211.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  212. maze[i][j - 1] == 0 && maze[i][j] == 1 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  213. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  214.   {
  215.   maze[i][j] = 1;
  216.   }
  217.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  218. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 1 && maze[i + 1][j - 1]
  219. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  220.   {
  221.   maze[i][j] = 1;
  222.   }
  223.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  224. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  225. == 1 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 0)
  226.   {
  227.   maze[i][j] = 1;
  228.   }
  229.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  230. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  231. == 0 && maze[i + 1][j] == 1 && maze[i + 1][j + 1] == 0)
  232.   {
  233.   maze[i][j] = 1;
  234.   }
  235.   if (maze[i - 1][j - 1] == 0 && maze[i - 1][j] == 0 && maze[i - 1][j + 1] == 0 &&
  236. maze[i][j - 1] == 0 && maze[i][j] == 0 && maze[i][j + 1] == 0 && maze[i + 1][j - 1]
  237. == 0 && maze[i + 1][j] == 0 && maze[i + 1][j + 1] == 1)
  238.   {
  239.   maze[i][j] = 1;
  240.   }
  241.  }
  242.  }//局部优化，防止出现大面积通路
  243. }
  244. void Findpath()
  245. {
  246.  int flag = 0;
  247.  int i, j;
  248.  while (!mqueue.empty())
  249.  {
  250.  i = mqueue.front().x;
  251.  j = mqueue.front().y;
  252.  mark[i][j] = 1;
  253.  for (int k = 0; k < 4; k++)
  254.  {
  255.   if (mark[i + sign[k][0]][j + sign[k][1]] == 0 && maze[i + sign[k][0]][j
  256. + sign[k][1]] == 0)
  257.   {
  258.   pos.x = i + sign[k][0];
  259.   pos.y = j + sign[k][1];
  260.   pos.d = k;
  261.   mark[pos.x][pos.y] = 1;
  262.   mqueue.push(pos);
  263.   if (mqueue.back().x == tm - 2 && mqueue.back().y == tn - 2)
  264.   {
  265.    mstack.push(mqueue.front());
  266.    mstack.push(mqueue.back());
  267.    flag = 1;
  268.    break;
  269.   }
  270.   }
  271.  }
  272.  if (flag) break;
  273.  mstack.push(mqueue.front());
  274.  if (!mqueue.empty())
  275.   mqueue.pop();
  276.  }
  277. }
  278. void changemaze()
  279. {
  280.  int i, j, k;
  281.  i = mstack.top().x;
  282.  j = mstack.top().y;
  283.  k = mstack.top().d;
  284.  maze[i][j] = -1;
  285.  while (mstack.size()>0)
  286.  {
  287.  if (mstack.top().x == i - sign[k][0] && mstack.top().y == j - sign[k][1])
  288.  {
  289.   i = i - sign[k][0];
  290.   j = j - sign[k][1];
  291.   k = mstack.top().d;
  292.   maze[i][j] = -1;
  293.   if (!mstack.empty())
  294.   mstack.pop();
  295.  }
  296.  else if (!mstack.empty())
  297.   mstack.pop();
  298.  
  299.  }
  300. }

据了解我们学校信息&自动化专业，包括徐特立学院在内，都是只学到树和森林，后面的内容也都没怎么涉及了。然而无限风光在险峰，这也不失为一种遗憾。这一专栏十篇博文，想必即使有人看，也顶多是嫖走学校平台上的题目解答，或者是只看文字，但很多经典的东西只有在代码里面才体会得到。那句话怎么说的呢？“我会给你幸福的”，这是故事的开始，“祝你幸福”，这是故事的结束。 

 

 

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/654225
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号