==主要功能目的：==手动实现一个红黑树和B树，并在此基础上建立一个English word information frequency list.

1、RB红黑树的实现

设计细节与想法

对于English word information frequency list的设计：

• 和关键字相关的satellite data被和关键字key一同封装在了结构PAIR中，以此作为一个单元放入红黑树的一个个子节点中。而且对于这样的一个对象，分别对输入、输出、比较等运算符进行了重载。

• 构造出的一整棵红黑树是一个RBtree的类，其中包括了一个内部类RB_TreeNode表示每一个红黑树的节点（用0表示红色，1表示黑色）、整个红黑树的根节点root、虚拟节点NIL、以及需要实现的一系列的功能接口。

• Initialization功能直接写在了RBtree类的构造函数里面，默认使用当前目录下的init.txt文件里的数据进行整棵红黑树的初始化，同样对于insert_by_file 和delete_by_file也默认使用当前目录下的文件进行操作

• 在insert功能实现过程中，首先先调用search_key()函数进行搜索是否存在关键字重复的情况发生。否则，输出conflict的提示信息，直接return，避免了进行额外的比较操作以及程序由于冲突而意外中止的情况发生。其次，默认将新插入的节点设置为红色，然后调用insert_fixup()对于与红黑树规则起冲突的节点分三种情况进行递归调整：

  • 第一种：插入节点的叔叔是红色，调整方式是父节点和叔叔节点变为黑色，然后递归处理爷爷节点
  • 第二种：插入节点的叔叔是黑色，而且插入节点和父节点在同侧，调整方式是进行单旋转
  • 第三种：插入节点的叔叔是黑色，而且插入节点和父节点在不同测，调整方式是进行双旋转，转化为上一种情况处理

• 在delete操作实现的过程中，同样的先调用search_key()搜索是否出现了该红黑树内部不存在关键字key的情况发生。否则，输出key missing的提示信息，同时return。如果删除的节点是红色，则直接使用子节点替代；如果删除的节点是黑色，就分四种情况分别进行处理。

  • 第一种：删去节点的兄弟节点是红色，单旋转使得转化为以下三种情况
  • 第二种：兄弟节点是黑色，而且兄弟的两个儿子也是黑色，解决方式是将兄弟变为红色，再递归处理父节点
  • 第三种：兄弟节点是黑色，而且兄弟的不同侧儿子为红色，调整方式是通过双旋转转化为第四种情况
  • 第四种：兄弟节点是黑色，而且兄弟的同侧儿子是黑色，调整方式是单旋转

• 对于红黑树的想法： 红黑树使用了红色和黑色的标记，对于平衡树的一系列操作进行了简化（特别是旋转操作），而且大大减少了需要回溯到根节点的情况发生，非常适合于map库的实现

2、B树实现

• 同红黑树一样，也使用了一个类VALUE来封装关键字key和所附带的satellite data.在用来表示B树的每一个节点的类B_TreeNode中，用一个长度为2*T-1的entries[]数组来表示一个节点中所储蓄的关键字，长度为2 *T的child[]数组来储蓄子节点；同时B_TreeNode中还有表示节点中的关键字数量keysize和表示该节点是否是叶节点的标志leaf.

• 初始化操作和插入删除操作的默认文档位置与红黑树文档相同

• 在insert操作实现的过程之中，主要是需要有一个分裂节点操作的实现。首先对于根节点是否是满的进行分类讨论：如果是满的，就对根节点进行分裂操作；否则就进行insert_notfull操作。在insert_notfull操作中每次搜索范围深入一层的时候，需要对下一个节点进行是否满的判断，并进行分裂，随后进行递归插入处理

• delete操作的实现则非常复杂，每次的操作都从根节点开始递归进行，分为以下几种情况区分处理

  1. 当要寻找的key在当前节点x中，而且x是叶节点，解决方式：直接删除

  2. 要寻找的key在当前节点x中，但是x不是叶节点，解决方式：

     1. 若x的左儿子和右儿子至少有一个节点的keysize>=t，则分别找到key的前驱和后继，并将目标改为删除key的前驱或者后继，同时代替原来的key
     2. 若x的左右儿子的keysize都只有t-1，则将key下移，进行merge操作，形成一个满节点

  3. key不在节点x中（但是key一定在x的某一个子节点中），先找到包含key的子节点x->child[i],并且只要满足以下条件就进行调整，之后开始对x->child[i]进行递归删除

     1. 若x->child[i]的keysize=t-1，而且有一个相邻兄弟的keysize>=t，那就调用shift_to_right_child或者shift_to_left_child，即从相邻的兄弟那里借来一个
     2. 若x->child[i]的keysize=t-1，而且所有的相邻兄弟的keysize=t-1,则选择一个兄弟进行merge操作

• 对于B树的想法 ：B树由于有着一个节点可以存储多个关键字，并且可以不止有2个子节点的特征，使得一棵B树的高度远远低于其他种类的树，所以在树的各种操作都复杂度和操作时间远远低于其他数据结构，是一个构造实现数据库的非常好的模型