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("");
            
        }

    }
View Code

 

  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);
        
    }
    
    
}
View Code

  测试结果:

 

 

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树和红黑树的存储的效率差异就显现出来了; 


作者:java小新人,发布于:2019/05/15
原文:https://www.cnblogs.com/wyq1995/p/10847088.html