java数据结构和算法07（2-3-4树）
上一篇我们大概了解了红黑树到底是个什么鬼，这篇我们可以看看另外一种树-----2-3-4树，看这个树的名字就觉得很奇怪。。。。
我们首先要知道这里的2、3、4指的是任意一个节点拥有的子节点个数，所以我们就大概知道2-3-4树中的每一个节点应该最多有四个子节点；注意：2-3-4树中的任意一个节点不能只有一个子节点，应该只有几种情况：0、2、3、4
有个东西一直忘记说了，就是那个大o表示法，或者叫做时间复杂度，感觉最开始不要纠结于用这个大o表示法比较好，因为直接看这个你会觉得很蒙，学了一定的数据结构回头再来看这个大o表示法，其实就那样吧！下面就先简单说说我个人对大o表示法的理解；
1.大o表示法
记得以前初中学过一次函数，二次函数，y=kx，y=ax2
我们一般是怎么理解这两种函数的，对于一次函数来说y与x成正比，二次函数也可以说y与x2成正比，那么我们有没有什么简单的表示方法呢？于是大o表示法就有作用了，在编程中我们就可以用o（n）和o（n2）这种方式来表示一次函数和二次函数。。。其实n就是相当于这里的x
在算法中，上面提到的y代表运行某个算法所需要的时间，x通常代表数据的个数，k和a代表常数可以不考虑，因为常数变化只会跟微处理器、编译程序生成代码的效率等因素有关；
说起来可能有点抽象，举个很简单的例子，假如我们要遍历包含10个元素的集合，此时遍历所需要的时间就是y，n就是10，我们遍历所需要的时间是和集合中数据的数量成正比的，于是用大o表示法就是o(n)；假如你要往一个无序数组中随便插入一个数字，因为无论数组中有多少个元素，你都只需要一步就解决战斗，所以时间复杂度就是n（1）；
进一步说说o（n），这表示运行时间受数据项个数的影响的程度，也就是说括号中的值越小，运行时间受到的影响越小，效率就越高，通常括号中是都是关于数据项个数n的函数，比如o（n）,o（n2），o(log2n）等，根据我们高中学的数学知识画一下常用的几个函数图像：
根据图像可知我们可以知道o（1）最平缓，运行时间受到数据数量的影响最小，效率最高；o（n2）的效率最慢，下面我们就简单看看前面我们实现的几种数据结构的时间复杂度；
无序数组的插入：o（1），向插入一个数据直接插入就好，跟数组中有多少个数据无关
有序数组的插入：o（n），在向有序数组插入数据的时候，会和数组中的数据进行比较才能确定插入的位置，很明显和数组中的数据个数有关
无序数组的删除、有序数组的删除：o（n），删除的话都跟数组中的数据个数有关，因为都是一个一个的遍历到删除的位置那里，删除数据
链表的插入和删除：o（1）
链表查询：o（n）
很平衡的搜索二叉树查询：o（log2n）
很平衡搜索二叉树添加节点：o(log2n)
红黑树：所有操作都是o(log2n)
可以看得出红黑树是一个几乎很完美的数据结构了，各种操作效率都很高，但是所有的数据结构都有得必有失，提升效率的同时，该数据结构的内部逻辑就越复杂，二者不可兼得；还有那些排序也可以根据大o表示法看的出来其效率高低。。。后面有时间再说排序的东西；
2. 2-3-4树的简单介绍
什么是2-3-4树呢？就比如前面我们说的搜索二叉树、红黑树都是属于二叉树，每个节点中只有一个数据，而且最多只有两个子节点；那能不能在节点中存多个数据呢？一个节点可以有很多个子节点？于是就有了2-3-4树，2-3-4树属于多叉树，跟红黑树一样是平衡的，效率比红黑树略低，但是编程容易很多，而且通过2-3-4树我们可以更容易理解b树，那有人就要问了，b树是干嘛的？暂时我们就不要纠结这个，后面有时间自然会说到的。
不知道大家理解节点中的数据是怎么看的，反正我是当作一个数轴来看的，就比如搜索二叉树，个人感觉根据这种方式更好理解节点中数据项和子节点数量的关系，嘿嘿！
那么如果节点中的数据不止一个呢？其实就是把上面这个做一个简单的变形就ok了，道理还是一样的，我们的2-3-4树中的2、3、4指的是除了叶节点之外，任意一个节点可能有的子节点的个数，换句话来说就是任意节点中存的数据最多为3个
下面我们看看画的比较好看的2-3-4树，可以简单的知道：节点的子节点个数=节点数据项+1
3. 2-3-4树的各种操作
粗略的知道了这些之后我们可以简单的分析一下各种操作的原理；
首先我们可以简单想想节点类里面到底是什么属性，首先应该有一个有序数组，里面可以按照一定的顺序存放三个数据；然后还有一个数组，用于存放子节点的引用；还需要有一个变量指向父节点的引用，最好还有一个int变量标识当前节点中数据项的数目；
我们用最简单的来，节点中就存整数，而且为了好写代码，我们把节点中的空位置用0,1,2来标识一下，把每个节点的子节点也用0,1,2,3,来标识一下；为什么不从1开始呢？因为节点中的数据和存放子节点的引用都是保存在数组中，数组都是从0开始的啊。。。。
所以节点类如下所示：
详细的节点类代码：
public static class node{
//当前节点中存的数据个数
private int length;
//当前节点存有父节点的引用
private node parent;
//当前节点中有三个空位置可以存放数据
private integer[] data = new integer[3];
//每个节点最多可以有四个子节点，我们准备四个位置随时存放子节点引用
private node[] childs = new node[4];
//根据传入子节点的为索引，我们将当前节点连接到子节点
public void connectnode(int childnum,node child){
childs[childnum] = child;
if (child!=null) {
child.parent = this;
}
}
//根据传入的子节点索引，我们断开该子节点的连接，返回断开的子节点
public node cutnode(int nodenum){
node node = childs[nodenum];
childs[nodenum] = null;
return node;
}
//获取指定索引的子节点
public node getchild(int nodenum){
return childs[nodenum];
}
//获取当前节点的父节点
public node getparent(){
return this.parent;
}
//判断当前节点是不是叶节点
public boolean isleaf(){
if (childs[0]==null&&childs[1]==null&&childs[2]==null) {
return true;
}
return false;
}
//获取当前节点保存数据的个数
public int getlength(){
return this.length;
}
//判断当前节点有没有装满
public boolean isfull(){
return (length==3)?true:false;
}
//根据数据找到在节点中的位置索引
public int index(int value){
for (int i = 0; i < 3; i++) {
if (data[i] == null) {
break;
}else if (value == data[i]) {
return 1;
}
}
return -1;
}
//将我们的数据插入到节点中，其实这里用到一个有序数组
//这里的逻辑其实很有意思，我们是遍历存数据的那个数组，从后往前，先找到非空的位置存放的数据key，和value比较，如果是value比较大，
// 直接在key后面插入;如果value比较小，则将key往后挪一个位置，继续循环往前遍历，重复上面的步骤，直到value比该位置存放的数据大为止，然后
// 直接插入到该位置后面即可；
//假如经过for循环了还能往下执行，说明一直都是执行for循环中的第一个if中，换句话来说数组中数据都为null，那就直接在数组索引为0的位置插入value即可
public int inserttonode(int value){
length++;
if (length>3) {
return -1;
}
for(int i = 2 ; i >= 0 ; i--){
if(data[i] == null){
continue;
}else{
int key = data[i];
if(value < key){
data[i+1] = data[i];
}else{
data[i+1] = value;
return i+1;
}
}
}
//如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置
data[0] = value;
return 0;
}
//移除节点中最右端的数据
public int removedata(){
int temp = data[length-1];
data[length-1] = null;
length--;
return temp;
}
//打印当前节点中的所有数据,例如 /30/40/50/
public void displaynode(){
system.out.print("/");
for (int i = 0; i < length; i++) {
system.out.print(data[i]+"/");
}
system.out.println("");
}
}
3.1.查询操作
其实查询操作很容易，类似搜索二叉树，我们在查询一个数据在哪一个节点的时候，还是一样首先和根节点中的数据比较（假设根节点有两个数据10和30），如果比10小那就去第一个孩子节点那里继续去找；如果是比10大比30小，那就去第二个孩子那里继续找；如果比30大，那就去第三个孩子那里接着找.....直到找到为止；
代码如下：
//去2-3-4树中查找有没有一个数字value
public int find(int value){
node current = root;
int index ;
//这里一个无限循环，假如当前根节点有这个数据，那就返回1；假如当前只有一个根节点，还没有保存数据value，那就
//直接返回-1；假如根节点还有子节点，那就让current这个指针指向下一个子节点，再重复上面的步骤
while(true){
if((index = current.index(value))!=-1){
return index;
}else if(current.isleaf()){//节点是叶节点
return -1;
}else{
current = getnextchild(current,value);
}
}
}
3.2 插入节点
这个也很容易，记住一点，插入节点始终都是在插入到叶节点中，也就是插入到最下面一层的节点中，可不会创建新的节点哦~这点和二叉树有点不同！仔细一想也对，每个节点中不是最多可以有三个数据吗，也就是有三个空位置可以让你插入数据，而且这三个空位置还是有顺序的；
我们在插入数据的时候会首先检查一下叶节点空位置有没有满，没有满的话就按照那个顺序插入到合适的位置，满了的话就要想办法把这个满了的节点拆开，变成几个节点然后再进行插入数据就ok了！这个拆开节点的操作也叫做分裂，下面我们会好好看看这个分裂到底是什么？也正是因为这个分裂才使得2-3-4树保持了平衡；
代码如下：
//插入数据项，其中这里的循环是最重要的一个
public void insert(int value){
node current = root;
while(true){
//如果当前节点数据满了，就分裂该节点，再把当前指针移动到合适的子节点那里，然后跳出循环向当前节点添加数据
if(current.isfull()){
split(current);//分裂节点方法在下面
current = current.getparent();
current = getnextchild(current, value);
//如果当前节点恰好是一个叶节点，直接跳出该循环，直接向当前节点添加数据
}else if(current.isleaf()){
break;
//如果当前节点既不是叶节点，也没有装满，那就继续进入该子节点
}else{
current = getnextchild(current, value);
}
}
//向当前节点插入数据
current.inserttonode(value);
}
3.3.节点分裂
节点分裂就是2-3-4树为了维护平衡所做的一些变化，和红黑树中的旋转不同，由于往2-3-4树中插入数据只会插入到叶节点中，我们来看看一个最简单的插入操作。
什么最简单呢？就只有一个根节点的时候是最简单的，我先把根节点装满之后继续往添加节点，看看是怎样变化，比如我插入节点30,50,80,10，如下图所示：
这就是所谓的2-3-4树所有的分裂了，记住，数据插入只能是在叶节点，假如该叶节点三个位置已经满了，就要把这个节点的三个数据分开来放，一个数据在本身所在的节点，一个数据放到父节点，另一个数据放到新创建的节点中。。。。。其实还是挺有趣的吧！
当然我们还可以想想上面最后一个图中，当另外两个子节点中的数据也满了之后会分裂，分别会向父节点丢进去一个数据，此时根节点就满了就会分裂，这个分裂就有点东西了，也是分裂最复杂的一种，看看下图所示：
代码：
//分裂节点,这个逻辑可以说是最复杂的一个，我把大概的逻辑说一下：
//首先把节点中数据项分别拆分成三部分，一份还是留给自己thisnode，一份是datab，另外一份是datac
//然后要新建一个兄弟节点newright，还要改变当前节点thisnode的子节点引用（假如当前节点thisnode是根节点，那么父节点也会变化），
//之后就是将datab和datac插入到父节点和兄弟节点中，最后就是将原来的节点thisnode的所有子节点分配给thisnode和newright
public void split(node thisnode){
node parent,child2,child3;
int dataindex;
int datac = thisnode.removedata();
int datab = thisnode.removedata();
child2 = thisnode.cutnode(2);
child3 = thisnode.cutnode(3);
node newright = new node();
if(thisnode == root){//如果当前节点是根节点，执行根分裂
root = new node();
parent = root;
root.connectnode(0, thisnode);
}else{
parent = thisnode.getparent();
}
//处理父节点
dataindex = parent.inserttonode(datab);
int n = parent.getlength();
for(int j = n-1; j > dataindex ; j--){
node temp = parent.cutnode(j);
parent.connectnode(j+1, temp);
}
parent.connectnode(dataindex+1, newright);
//处理新建的右节点
newright.inserttonode(datac);
newright.connectnode(0, child2);
newright.connectnode(1, child3);
}
3.4 删除
说实话，删除这个操作的逻辑有点复杂，而且在《java数据结构和算法第二版》也没有涉及到删除操作，我自己查了一下相关的资料是这样说的：需要处理节点的合并和调整，比较复杂，由于没有太大的必要，因此建议采用最简单的做法：给删除节点打标记，然后在业务处理时跳过即可。
然而我就是不信邪，我就要看看删除的操作是什么。。。。知道我真的看到了删除的代码，我就信邪了！表示暂时对删除节点兴趣不大。。。
想看看删除操作的小伙伴，可以参考这个大佬的博客：https://www.cnblogs.com/xzjxylophone/p/7542884.html
4.完整代码
2-3-4树完整代码：
package com.wyq.test;
public class my234tree {
//根节点，通过下面的构造器初始化一个根节点
private node root;
public my234tree(){
root = new node();
}
//节点类
public static class node{
//当前节点中存的数据个数
private int length;
//当前节点存有父节点的引用
private node parent;
//当前节点中有三个空位置可以存放数据
private integer[] data = new integer[3];
//每个节点最多可以有四个子节点，我们准备四个位置随时存放子节点引用
private node[] childs = new node[4];
//根据传入子节点的为索引，我们将当前节点连接到子节点
public void connectnode(int childnum,node child){
childs[childnum] = child;
if (child!=null) {
child.parent = this;
}
}
//根据传入的子节点索引，我们断开该子节点的连接，返回断开的子节点
public node cutnode(int nodenum){
node node = childs[nodenum];
childs[nodenum] = null;
return node;
}
//获取指定索引的子节点
public node getchild(int nodenum){
return childs[nodenum];
}
//获取当前节点的父节点
public node getparent(){
return this.parent;
}
//判断当前节点是不是叶节点
public boolean isleaf(){
if (childs[0]==null&&childs[1]==null&&childs[2]==null) {
return true;
}
return false;
}
//获取当前节点保存数据的个数
public int getlength(){
return this.length;
}
//判断当前节点有没有装满
public boolean isfull(){
return (length==3)?true:false;
}
//根据数据找到在节点中的位置索引
public int index(int value){
for (int i = 0; i < 3; i++) {
if (data[i] == null) {
break;
}else if (value == data[i]) {
return 1;
}
}
return -1;
}
//将我们的数据插入到节点中，其实这里用到一个有序数组
//这里的逻辑其实很有意思，我们是遍历存数据的那个数组，从后往前，先找到非空的位置存放的数据key，和value比较，如果是value比较大，
// 直接在key后面插入;如果value比较小，则将key往后挪一个位置，继续循环往前遍历，重复上面的步骤，直到value比该位置存放的数据大为止，然后
// 直接插入到该位置后面即可；
//假如经过for循环了还能往下执行，说明一直都是执行for循环中的第一个if中，换句话来说数组中数据都为null，那就直接在数组索引为0的位置插入value即可
public int inserttonode(int value){
length++;
if (length>3) {
return -1;
}
for(int i = 2 ; i >= 0 ; i--){
if(data[i] == null){
continue;
}else{
int key = data[i];
if(value < key){
data[i+1] = data[i];
}else{
data[i+1] = value;
return i+1;
}
}
}
//如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置
data[0] = value;
return 0;
}
//移除节点中最右端的数据
public int removedata(){
int temp = data[length-1];
data[length-1] = null;
length--;
return temp;
}
//打印当前节点中的所有数据,例如 /30/40/50/
public void displaynode(){
system.out.print("/");
for (int i = 0; i < length; i++) {
system.out.print(data[i]+"/");
}
system.out.println("");
}
}
//去2-3-4树中查找有没有一个数字value
public int find(int value){
node current = root;
int index ;
//这里一个无限循环，假如当前根节点有这个数据，那就返回1；假如当前只有一个根节点，还没有保存数据value，那就
//直接返回-1；假如根节点还有子节点，那就让current这个指针指向下一个子节点，再重复上面的步骤
while(true){
if((index = current.index(value))!=-1){
return index;
}else if(current.isleaf()){//节点是叶节点
return -1;
}else{
current = getnextchild(current,value);
}
}
}
//怎么进入到下一个子节点中呢？利用一个for循环遍历当前节点中的数据，然后根据value是在哪一个范围里面就对应哪一个子节点
//这里的for循环有点东西，可以仔细看看
public node getnextchild(node node,int value){
int j;
int datanum = node.getlength();
for(j = 0 ; j < datanum ; j++){
if(value<node.data[j]){
return node.getchild(j);
}
}
return node.getchild(j);
}
//插入数据项，其中这里的循环是最重要的一个
public void insert(int value){
node current = root;
while(true){
//如果当前节点数据满了，就分裂该节点，再把当前指针移动到合适的子节点那里，然后跳出循环向当前节点添加数据
if(current.isfull()){
split(current);//分裂节点方法在下面
current = current.getparent();
current = getnextchild(current, value);
//如果当前节点恰好是一个叶节点，直接跳出该循环，直接向当前节点添加数据
}else if(current.isleaf()){
break;
//如果当前节点既不是叶节点，也没有装满，那就继续进入该子节点
}else{
current = getnextchild(current, value);
}
}
//向当前节点插入数据
current.inserttonode(value);
}
//分裂节点,这个逻辑可以说是最复杂的一个，我把大概的逻辑说一下：
//首先把节点中数据项分别拆分成三部分，一份还是留给自己thisnode，一份是datab，另外一份是datac
//然后要新建一个兄弟节点newright，还要改变当前节点thisnode的子节点引用（假如当前节点thisnode是根节点，那么父节点也会变化），
//之后就是将datab和datac插入到父节点和兄弟节点中，最后就是将原来的节点thisnode的所有子节点分配给thisnode和newright
public void split(node thisnode){
node parent,child2,child3;
int dataindex;
int datac = thisnode.removedata();
int datab = thisnode.removedata();
child2 = thisnode.cutnode(2);
child3 = thisnode.cutnode(3);
node newright = new node();
if(thisnode == root){//如果当前节点是根节点，执行根分裂
root = new node();
parent = root;
root.connectnode(0, thisnode);
}else{
parent = thisnode.getparent();
}
//处理父节点
dataindex = parent.inserttonode(datab);
int n = parent.getlength();
for(int j = n-1; j > dataindex ; j--){
node temp = parent.cutnode(j);
parent.connectnode(j+1, temp);
}
parent.connectnode(dataindex+1, newright);
//处理新建的右节点
newright.inserttonode(datac);
newright.connectnode(0, child2);
newright.connectnode(1, child3);
}
//打印树中所有节点
public void displaytree(){
recdisplaytree(root,0,0);
}
//这里的level表示当前节点在树中的层数；childnumber表示在当前节点属于父节点的第几个子节点
private void recdisplaytree(node thisnode,int level,int childnumber){
system.out.println("levle="+level+" child="+childnumber+" ");
thisnode.displaynode();
int numitems = thisnode.getlength();
for(int j = 0; j < numitems+1 ; j++){
node nextnode = thisnode.getchild(j);
if(nextnode != null){
recdisplaytree(nextnode, level+1, j);
}else{
return;
}
}
}
public static void main(string[] args) {
my234tree tree = new my234tree();
tree.insert(1);
tree.insert(10);
tree.insert(100);
tree.insert(1111);
tree.insert(14);
tree.insert(18);
tree.insert(132);
tree.insert(16);
tree.insert(15);
tree.insert(1);
tree.insert(10);
tree.insert(100);
tree.insert(1111);
tree.insert(14);
tree.insert(18);
tree.insert(132);
tree.insert(16);
tree.insert(15);
tree.displaytree();
int find = tree.find(99);
system.out.println(find);
}
}
测试结果：
5. 2-3-4树和红黑树
感觉这个部分就了解一下即可，根据自己的需要可以选择看或者不看；
在历史上，先发展出来的是2-3-4树，而所谓的红黑树是在这个基础上进一步发展才得到的，那么这两种树肯定有着某种不可告人的秘密，那么到底是什么秘密呢？
偷个懒，就不自己画图了，就随便看看下面这两个图，一个是2-3-4树，另一个是红黑树，这两个是等效的！
两种树看似完全不一样，其实真要说起来的话也差不多，我们只需要通过某些规则就可以使一个2-3-4树转化为一个红黑树，虽然实际应用时肯定不会这样去转化，了解一下还是挺有趣的；
5.1简单的看看一些规则（记住子节点都是红色就ok了）
（1） 2-3-4树的节点只有一个数据项的情况
（2）2-3-4树的节点只有两个数据项的情况
（3） 2-3-4树的节点有三个数据项的情况
基于上述三种规则就可以将一个2-3-4树变为一个红黑树了，下面就随意看看一个例子：
5.2 2-3-4树和红黑树的等效操作
那么就有人要问了，红黑树中有变化颜色和旋转啊，2-3-4树中有什么操作是与之相对应的吗？当然有啦，我们可以简单的看看两者对应的关系：
红黑树中的颜色变换---------->2-3-4树中节点分裂
红黑树中的左旋和右旋------------>2-3-4树中选取哪个数据作为父节点，就像上面5.2那里一样
首先是对于2-3-4树中的节点分裂应该就不用多说了吧，你把分裂前对应的红黑树画出来，再把分裂后的红黑树画出来，就能明显的看出来：
而对于2-3-4树中节点数据选择哪一个作为父节点，就等效于红黑树的左旋右旋，下面图中以80为父节点的红黑树--------------------->以70为父节点的红黑树，就要经过右旋；
5.3. 2-3-4树和红黑树的效率
说过了大o表示法，我们就简单的来看看2-3-4树和红黑树的小路，前面说过2-3-4树查询的效率比红黑树略低一点，为什么呢？
首先从速度方面来来看看，因为红-黑树的层数（平衡二叉树）大约是log2(n+1)，而2-3-4树每个节点可以最多有4个数据项，如果节点都是满的，那么高度和log4n成正比。因此在所有节点都满的情况下，2-3-4树的高度大致是红-黑树的一半。不过他们不可能都是满的，所以2-3-4树的高度大致在log2(n+1)和log2(n+1)/2，按理来说减少2-3-4树的高度可以使它的查找时间比红-黑树的短一些，可是2-3-4树中每一个节点的数据项变多了，这也会影响查询时间；
2-3-4树总的查找时间和m*log4n成正比，由于树中节点可能存一个数据项，两个数据项，三个数据项，取平均数都按两个算查找时间跟2*log4n成正比，在大o表示法中2这个常数可以忽略不计，而且在2-3-4树中每个节点数据项增加了抵消了树高度比较矮的优势，一增一减之下其实和红黑树差不多，都是o（logn）,话说大o表示法中的logn是以2为底数的，其实写成lgn也无所谓，底数不同的对数可以相互转化的，无非是乘以一个常数而已，这就不多说了。。。
然后我们从存储需求的角度看看，2-3-4树中的节点的数据项不可能填满，我们仔细说说大概利用率是多少！
一个节点中有两个数组，这两个数组的大小是确定了的分别为3和4，假如一个节点中存的数据只有一个，那么就会浪费2/3的数据存储空间和1/2的子节点存储空间；假如节点中存的数据有两个，数据存储空间浪费1/3，子节点存储空间浪费1/4;平均一下按照每一个节点只有两个数据项来算一下，2-3-4树浪费了2/7的空间；反观红黑树所有的能用到的存储空间都用了，利用率就比2-3-4树更高；由于在java中的2-3-4树中存储的是对象的引用，所以这种效率还不是很明显，在有的编程语言保存的不是对象的引用，那么2-3-4树和红黑树的存储的效率差异就显现出来了；