PTA：Self-printable B+ Tree

原题

In this project, you are supposed to implement a B+ tree of order 3, with the following operations: initialize, insert (with splitting) and search. The B+ tree should be able to print out itself.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number , the number of integer keys to be inserted. Then a line of the positive integer keys follows. All the numbers in a line are separated by spaces.

Output Specification:

For each test case, insert the keys into an initially empty B+ tree of order 3 according to the given order. Print in a line Key X is duplicated where X already exists when being inserted. After all the insertions, print out the B+ tree in a top-down lever-order format as shown by the samples.

Sample Input 1:

6
7 8 9 10 7 4   

Sample Output 1:

Key 7 is duplicated
[9]
[4,7,8][9,10] 

Sample Input 2:

10
3 1 4 5 9 2 6 8 7 0 

Sample Output 2:

[6]
[2,4][8]
[0,1][2,3][4,5][6,7][8,9]

Sample Input 3:

3
1 2 3

Sample Output 3:

[1,2,3]

题意

给定N个整数，以给出的顺序保存到3阶B+树中，要求按照给定的格式输出B+树的层序遍历。

非常简洁的题目，一句话就能说完。

解析

关键词（主要知识点）

B+树、树的遍历。

分析题意

题意中只要我们将数字保存到B+树中，遇到重复的数字直接输出指定语句即可，即：只要求完成B+树的插入操作，没有删除操作。

对于这道题，我们只需要实现一个阉割版的3阶B+树即可，需要完成：插入、查找、分裂（B+树的特性，稍后提到）几个主要功能。

3阶B+树 （B+ tree of order 3）

主要从以下几个方面来对这个数据结构进行简单介绍：

• B+树是个啥，有啥特性。
• 3阶对于B+树来说意味着什么。
• 如何实现满足题意的3阶B+树。

这里仅针对本题做简要介绍（与题目无关的性质就先不说啦，譬如叶子节点会像链表一样互相连接），B+树是一种非常、非常、非常、非常……重要的数据结构，常见于计算机的文件系统、数据库的引擎和索引等，同时也是面试中热度很高的考点（亲身经历），所以大家有兴趣的可以多方查阅资料进行更加全面的了解。

About B+树

B+树是一种多路查找树，多路查找树可以通俗的称之为“多叉树”，大家一定学过的二叉树就是其中一种。

回顾、类比一下二叉查找树，二叉查找树中，每一个非叶子节点最多有2个子树，节点本身保存的数据用作索引，左子树中的所有数都比它小，右子树中比他大，总结一下就是：通过一个索引项，依照数据与这个索引的大小关系，将数据分成了两部分。

再回到B+树中，它和二叉查找树的主要区别就在于，它不止“二叉”，也就是说节点中不止一个索引项，不止两个子树，即可以通过个索引将数据分为部分。对于一个节点中的多个数据，我们需要维护其有序性，保证节点中的数据（叶子节点保存的是具体数据）或索引（非叶子节点保存的是索引）都是有序的。

其次它还需要维护一个“平衡”的特性，当一个节点中保存的数据太多时，它有一个分裂的操作，将一个节点分裂成两个节点。假设一个节点最多保存3条数据，当一个节点中已经存在1,2两个数据，在3插入到该节点后，该节点便会分裂，如下图所示：

B+树分裂

大家可以注意一下：

• 分裂后会将原来的数据分别存放到2个新节点中，由此会需要一个新的索引（如图中分裂后根节点的2）。
• 因为产生了新索引，所以会对父节点进行修改：有父节点就在父节点中把新的索引加进去，没有父节点就新建一个父节点（一般这种情况就是根节点分裂，树会长高）。
• 大家可以留意并思考一下叶子节点的分裂与非叶子节点的分裂有何不同（如下图对样例2的图解）。

案例2解析

About 3阶

关于这个3阶，就是表示一个节点最多保存2条数据，当有了3条时，就分裂。

这里有一个坑就是，我们可以看到第一个样例，它第二层的叶子节点为：[4,7,8][9,10]，第一个叶子节点有3个数据，与前面说好的最多保存2条数据不一样。

对于这个的现象，国内很多论坛里并没有给出原因，大部分讲解B+树的博客中，都是直接定性阶的B+树每个节点都最多保存个数据，叶子节点也是这样。

最终在国外一个论坛中找到了相关的解释：

For a B+ tree the order of a node is the maximum number of keys that it can contain. This satisfies the definition of maximum number of children because for a leaf node number of record pointers(children) is same as number of keys. The last pointer present in a leaf node is not considered a children since it links one leaf to another(is not a record pointer).

摘自：Order of a leaf node in B+ Tree

其大意是说：叶子节点中最后一个元素往往不视为数据节点，还起到了一个指针的作用（前面提到的B+树叶子节点会像链表一样相连，只是由于本题中用不到该性质，故不过多介绍）。

所以总结一下，这个题里边的3阶的含义为：

• 对于非叶子的索引节点，只能保存最多2个索引数据，当第三个数据插入时，需要分裂。
• 而对于叶子节点，则可以保存最多3个数据，当第四个数据插入时才需要分裂。

如果直接参考国内一些博客中对B+树的解析，很少有提到这个的，如果没考虑到这个，基本上只能得到一个“部分正确”了。

无法通过的案例

如何实现

按照前面说的，对于这个3阶B+树，主要需要定义3个操作函数：插入、分裂、查找。

• 查找：为了进一步提高代码的复用性，我们可以将“查找”操作定义为，只找到这个数应在的叶子节点，这样得到的结果既能用于判断这个数是否存在，又能用于完成插入操作。

• 分裂：分裂需要对父节点插入一个新的索引，会导致父节点中数据项增加（需要维护有序性），故每次分裂完后需要不断向上检查父节点是否需要分裂，可以将检查是否需要分裂也加入到这个操作中，该操作可用递归实现。

• 插入：直接在查找函数找到的叶子节点中，插入数据（需要维护有序性），然后调用分裂的函数递归地进行检查并分裂。

单次数字插入的流程图如下所示，具体实现参考下一章节代码：

流程图

代码

代码已包含注释。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

#define ORDER 3

using namespace std;

class Node
{
public:
    int cnt_data = 0;  // 该节点所保存的数据量
    int cnt_child = 0;  // 子节点数
    int data[ORDER + 1];   // 该节点所保存的具体数据（非叶子节点为索引，叶子节点为数据）
    Node *child[ORDER + 2]; // 子节点
    Node *parent = NULL; // 父节点，节点分裂时使用，根节点为NULL
    Node *next; // 作为叶子节点时的相邻节点，实际上并没有用到这个
    Node ()
    {}

    /**
     * 通过给定的数据进行初始化
     * @param pra 父节点
     * @param data_src 用来赋值data的数据源
     * @param data_interval [first,second)左闭右开的区间，表示data_src具体传入的数据区间
     * @param child_src 用来赋值child的数据源
     * @param child_interval 同data_interval
     */
    Node (Node *pra, int data_src[], pair<int, int> data_interval, Node *child_src[], pair<int, int> child_interval)
    {
        this->parent = pra;
        this->cnt_data = data_interval.second - data_interval.first;
        memcpy(this->data, data_src + data_interval.first, this->cnt_data * sizeof(data_src[0]));
        this->cnt_child = child_interval.second - child_interval.first;
        memcpy(this->child, child_src + child_interval.first, this->cnt_child * sizeof(child_src[0]));
        // 将子节点的父节点指针指向该节点
        for (int i = 0; i < cnt_child; ++i)
        {
            child[i]->parent = this;
        }
    }

    void print ()
    {
        printf("[");
        for (int i = 0; i < cnt_data; ++i)
        {
            if (i)
                printf(",");
            printf("%d", data[i]);
        }
        printf("]");
    }
};

int n;
Node *Root = new Node();

// DEBUG
int split_time = 0;

/**
 * 后续再插入新的子节点后，为某一个节点的子节点属性排序时用到
 * 排序依据为节点第一个数据项的大小
 * @param p1
 * @param p2
 * @return
 */
bool cmp (Node *p1, Node *p2)
{
    return p1->data[0] < p2->data[0];
}

/**
 * 层序遍历并打印
 */
void print_tree ()
{
    Node *BlankLine = NULL; // 换行标记，标记一层节点
    queue<Node *> que;
    que.push(Root);
    que.push(BlankLine);
    while (!que.empty())
    {
        Node *t = que.front();
        que.pop();
        if (t == BlankLine)
        {
            printf("\n");
            if (!que.empty())
                que.push(BlankLine);
            continue;
        }
        t->print();
        for (int i = 0; i < t->cnt_child; ++i)
        {
            que.push(t->child[i]);
        }

    }
}

/**
 * 检查并分裂当前节点，当前节点分裂完成后递归检查父节点是否需要分裂。
 * @param node 待分裂的节点
 */
void split (Node *node)
{
    // 用node指针获取变量太长，用局部变量简化
    int cntData = node->cnt_data;
    int cntChild = node->cnt_child;
    bool is_leaf = cntChild == 0;
    Node **child = node->child;
    int *data = node->data;

    // 不需要分裂
    if ((is_leaf && cntData <= ORDER) ||
        (!is_leaf && cntData < ORDER))
    {
        return;
    }

    // 当前节点为根节点，则生成新的根节点
    if (node->parent == NULL)
    {
        Root = node->parent = new Node();
    }

    Node *pra = node->parent;

    int mid ;

    // 分裂为左右两个节点
    Node *l ;
    Node *r ;

    // 对于叶子节点和非叶子节点分别处理
    if (is_leaf)
    {
        // mid = 2; // 等效
        mid = ceil(1.0*ORDER/2);
        
        l = new Node(pra, data, make_pair(0, mid), child, make_pair(0, 0));
        r = new Node(pra, data, make_pair(mid, cntData), child, make_pair(0, 0));
    } else
    {
        // mid = 1; // 等效
        mid = ceil(1.0*(ORDER-1)/2);
        
        l = new Node(pra, data, make_pair(0, mid), child, make_pair(0, mid+1));
        r = new Node(pra, data, make_pair(mid+1, cntData), child, make_pair(mid+1, cntChild));
    }
    
    // 更新父节点的索引
    pra->data[pra->cnt_data++] = data[mid];

    // 替换父节点的子节点列表中保存的当前节点（当前节点已经分裂为2个子节点）
    if (pra->cnt_child > 0)
        for (int i = 0; i < pra->cnt_child; ++i)
        {
            if (pra->child[i] == node)
            {
                pra->child[i] = l;
                break;
            }
        }
    else
        pra->child[pra->cnt_child++] = l;
    pra->child[pra->cnt_child++] = r;

    // 排序，上一步直接插入可能会导致乱序
    sort(pra->data, pra->data + pra->cnt_data);
    sort(pra->child, pra->child + pra->cnt_child, cmp);

    // 释放当前节点的所占的空间
    delete node;

    // 递归检查父节点是否需要分裂
    split(pra);
}


/**
 * 插入数据
 * @param node
 * @param n
 */
void insert (Node *node, int n)
{
    if (node == NULL)
    {
        node = new Node();
    }
    node->data[node->cnt_data++] = n;
    sort(node->data, node->data + node->cnt_data);
    split(node);
}

/**
 * 查找n应在的Node对象，实际上n不一定存在B+树中
 * 数据被m个索引分成了m+1段，即子树的数量比索引的数量多1，所以用upper_bound找到的第一个大于n的索引下标，放到其孩子列表中恰好为n所在的子树的下标
 * @param root
 * @param n
 * @return 返回n应在的叶子节点的指针
 */
Node *find (Node *root, int n)
{
    if (root == NULL)
        return root;
    // 叶子节点
    if (root->cnt_child == 0)
        return root;
    
    int i = upper_bound(root->data, root->data + root->cnt_data, n) - root->data;
    return find(root->child[i], n);

}


/**
 * 判断n是否存在
 * @param node 用find方法找到的n应在的叶子节点
 * @param n
 * @return
 */
bool exist (Node *node, int n)
{
    if (node == NULL)
        return false;
    return binary_search(node->data, node->data + node->cnt_data, n);
}

int main ()
{

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int num;
        scanf("%d", &num);
        Node *leaf = find(Root, num);
        if (!exist(leaf, num))
            insert(leaf, num);
        else
        {
            printf("Key %d is duplicated\n", num);
        }
    }

    print_tree();

    return 0;
}