扁扁笨算法-B树的插入与删除

扁扁笨简述

扁扁笨算法是将不平衡子树打成一条中序遍历的直链（实质是一条升序链），然后按照寻找中点并提起中点构造二叉树的一种朴素做法。扁扁笨算法是一种确定平衡树调整结构之后填入数字的辅助手段，本身并没有什么出彩的地方。

理论简介

B树是一种强结构弱数据的数据结构。从B树的定义我们可以看到，B树的大部分要求都是在规范B树具有怎样的结构。从纯粹的数据排列上看，它只是一种扩展版的二叉排序树，但是B树之所以为B树就在于它的结构要求，其中比较重要的有，结点的元素个数、结点的指针个数。结点的元素个数描述了一个结点可以画几个格格，结点的指针个数描述了每个格格之间的边边指向下一层的结点。

之所以说，B树具备强结构弱数据的特点，是因为B树的操作和删除并不是很关系，数据的组织，因为排序树的特性，数据只需要按照简单的大小关系填入B树的框架里即可。或者说，给定一组数据序列，我们不能确定唯一的B树，而且异构的B树是复杂的。但一旦确定了B树的结构，我们就可以确定唯一的一棵B树，至于数据，依次填上去就好了。

所以，我们可以利用扁扁笨算法将结构与数据抽离开。将B树中某个数据元素的删除或者插入，转化为一种结构是如何演变为另一个结构的。在这种抽象的结构研究中，我们不关心结点的大小，但关心结点的个数和大小关系。

我们假设这是一棵5阶B树，那么首先我们应该写出它每个结点所容纳的结点范围：2~4，即一个非根结点最少不能少于2个结点，最多不能多于4个结点。

在开始删除操作之前，我们引入一些新的概念，我们将元素个数等于结点最少元素数的结点称为饥饿结点/贫瘠结点，元素个数等于结点最多元素的结点称为肿胀结点，除此之外我们称为温饱结点。在5阶B树的语境下，元素数为2的结点为饥饿结点，元素数为4的为肿胀结点，元素数为3的结点为温饱结点。如果整棵B树的结点均为贫瘠结点，那么我们称这棵树是贫瘠的。

我们不妨进行一下讨论，当我们的删除发生在并不饥饿的结点（肿胀结点或者温饱结点）上时，整棵B树的结构不会发生改变。而当我们的删除发生在饥饿结点时，一定会引起结构的改变。

既然饥饿结点中元素的删除会引发结构改变，那我们的诉求就转变为了寻找这种结构改变。当删除贫瘠B树的贫瘠结点元素时，B树为了维持结构要求会通过“降层”的方式去填补下层缺失的结点。当删除非贫瘠B树的贫瘠结点时，贫瘠结点会被周围同层的温饱结点吸收。而吸收动作会引发下层结构缺位，这时降层得到的新的顶层就需要贡献一个结点给下层，用以维持结构。

插入操作有着类似的讨论，我们在下面进行展开。

当我们的插入发生在一个并不肿胀的结点（贫瘠结点或温饱结点）上时，，整棵B树的结构不会发生改变。而当我们的插入发生在肿胀结点时，一定会引起结构的改变。当元素插入到肿胀结点中时，就会引发结点爆炸，这个结点会分裂成为两个新的结点（这两个结点通常是温饱的）。但需要注意的是，为了维持该层多一个结点的结构，上层的指针也需要多一个，多一个指针需要下层结点为上层结点贡献一个元素。注意，在这种情况下，下层多一个结点导致上层也多一个结点，而上层多的这个结点也是有可能因为肿胀结点的插入而分裂，这种情况就会不断传递给上层，直到根结点。