2-3-4 Tree_2-3-4tree是什么-程序员宅基地

技术标签: 2-4-Tree  ● 数据结构和相关算法  2-3-4-Tree  ------------【数据结构】  

2-3-4 Tree

简介

2-3-4 Tree又叫2-4 Tree,属于一种平衡查找树,其高度满足:<=$\log_2 x N$,关于性能问题,以后会专门出个小专题来讨论。

– 以下出自[维基百科]

  • 2-节点,就是说,他包含1个元素和2个子节点
  • 3-节点,就是说,他包含2个元素和3个子节点
  • 4-节点,就是说,他包含3个元素和4个子节点

从上面我们可以看出一个非叶子节点的子节点的个数总是比它的元素个数少一个。
2-4Tree是一棵查找树,因此它的元素的排列也是具有一定的顺序。具体可自行查阅。本文主要给出2-4Tree相关操作的主要算法。
为了行文方便,下面统一将2-3-4 Tree成为2-4 Tree。

操作算法分析

本文所用代码取自倪升武的博客,本人只是对其代码进行了一些注解和说明。在此对倪升武 表示感谢!

2-4Tree操作节点的定义代码

这里我们将节点内部的值包装进DataItem类,首先是DataItem类:

// 数据项
class DataItem
{
    public long dData;

    public DataItem(long data)
    {
        dData = data;
    }

    public void displayItem()
    {
        System.out.print("/" + dData);
    }
}

然后是2-4Tree的节点定义类:

// 节点
class Node2
{
    private static final int ORDER = 4;
    private int numItems; // 表示该节点存有多少个数据项
    private Node2 parent; //父节点
    private Node2 childArray[] = new Node2[ORDER]; // 存储子节点的数组,最多4个子节点
    private DataItem itemArray[] = new DataItem[ORDER - 1];// 该节点中存放数据项的数组,每个节点最多存放3个数据项

    // 将child节点连接到节点的childNum的位置上
    public void connectChild(int childNum, Node2 child)
    {
        childArray[childNum] = child;
        if (child != null)
        {
            child.parent = this;
        }
    }

    // 断开与子节点的连接,并返回该子节点
    public Node2 disconnectChild(int childNum)
    {
        Node2 tempNode = childArray[childNum];
        childArray[childNum] = null;
        return tempNode;
    }
    //得到childNum位置上的子节点
    public Node2 getChild(int childNum)
    {
        return childArray[childNum];
    }

    public Node2 getParent()
    {
        return parent;
    }
    //判断是否是叶子节点,依据:因为对于非叶子节点,总是满足子节点个数=父节点元素个数+1;在满足这种条件的情况下,子节点的排列总是从childArray[0]开始。
    public boolean isLeaf()
    {
        return (childArray[0] == null);
    }
    
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_16811963/article/details/51646533

智能推荐

MMDeploy详解-程序员宅基地

文章浏览阅读2k次,点赞3次,收藏6次。MMDeploy理解_mmdeploy

最流行的android组件大全_android热门组件-程序员宅基地

文章浏览阅读1.3k次。原文链接:http://blog.csdn.net/smallnest/article/details/38658593/Android 是目前最流行的移动操作系统之一。 随着新版本的不断发布, Android的功能也日益强大, 涌现了很多流行的应用程序, 也催生了一大批的优秀的组件。本文试图将目前流行的组件收集起来以供参考, 如果你发现本文还没有列出的组件,欢迎在评论中贴出来,我会定_android热门组件

python小练习5:如何判断一个数能否被3整除_用python编写一个小程序,用来判断任意一个数是否能被3整除-程序员宅基地

文章浏览阅读7.7w次,点赞6次,收藏28次。题:如何判断一个数能否被3整除?(或者被其他任意一个数整除)方法一:取余 x = input(&amp;amp;quot;input an number:&amp;amp;quot;) if x % 3 == 0: print &amp;amp;quot;%d 能被3整除&amp;amp;quot; %(x) else: print &amp;amp;quot;%d 不能被3整除&amp;amp;quot;_用python编写一个小程序,用来判断任意一个数是否能被3整除

网桥_网桥下设备广播-程序员宅基地

文章浏览阅读925次。先装好网卡,连上网线,然后开始!设置linux让网桥运行 配置网桥我们需要让linux知道网桥,首先告诉它,我们想要一个虚拟的以太网桥接口:(这将在主机bridge上执行,不清楚的看看测试场景)root@bridge:~> brctl addbr br0其次,我们不需要STP(生成树协议)等。因为我们只有一个路由器,是绝对不可能形成一个环的。我们可以关闭这个功能。(这_网桥下设备广播

linux|tgz解压出错_linux tgz解压 失败-程序员宅基地

文章浏览阅读1.1k次。[stu01@localhost pointer]$ tar -xzvf cnn-stories.tgztar (child): cnn-stories.tgz: Cannot open: No such file or directorytar (child): Error is not recoverable: exiting nowtar: Child returned statu_linux tgz解压 失败

小小君的C语言第五课_创建一个字符串数组(内容是你周围一圈人的姓名),输出最长字符串的长度。-程序员宅基地

文章浏览阅读596次。二维数组、字符串数组、多维数组 //声明一个二维数组 // 数据类型 + 数组名[第一维长度][第二维长度] = {值1,值2, ...}; //一般第一维 叫行 第二维叫列 //需求_创建一个字符串数组(内容是你周围一圈人的姓名),输出最长字符串的长度。

随便推点

Kubernetes业务日志收集与监控-程序员宅基地

文章浏览阅读732次。随着容器技术以及容器编排技术的成熟,越来越多的中小型企业也在将服务迁移到Kubernetes中,更智能,更便捷的管理服务,降低运维成本,而在迁移过程中,业务日志的收集以及业务服务的监控,..._kubemate日志监控

前端面试题—2021年web前端开发面试题_2021年前端开发面试题-程序员宅基地

文章浏览阅读796次。【前端面试】前端面试题—2021年web前端开发面试题本文章作为2021届应届毕业生在实习面试期间所接受的前端面试的面试题。2021年最新面试题CSS盒子模型的要素 ,https://www.cnblogs.com/clearsky/p/5696286.html;CSS中常用伪元素选择符;Position属性四个值:static、fixed、absolute和relative的区别和用法 ;解释CSS样式中display中inline、block、inline-block的区别 ;var和l_2021年前端开发面试题

用函数实现两个数的加法_7)编写一个函数,参数包括两个运算数x,y以及进位,通过调用全加器计算x,y的求和结果-程序员宅基地

文章浏览阅读4.5k次,点赞6次,收藏3次。1,加法#define _CRT_SECURE_NO_WARNINGS#include &lt;stdio.h&gt;int add(int x, int y){int z = x + y;return z;}int main(){int num1 = 0;int num2 = 0;int sum = 0;printf(“请输入两个操作数\n”);scanf("%d %..._7)编写一个函数,参数包括两个运算数x,y以及进位,通过调用全加器计算x,y的求和结果

对tableView的contentOffset的理解_tableview.contentoffset-程序员宅基地

文章浏览阅读4.1k次。tableView往上滚动, contentOffset.y为正,此时对于tableView内部控件而言,原点在哪里?如图所示:未开始滚动时,可以把contentOffset.y == 0看成一条分割线,随着向上滚动的进行,对于tableView内部控件而言原点已经滚动到原来contentOffset.y == 0这条分割线的上方了,而此时这个位置的分割线变成contentOffset.y ==_tableview.contentoffset

关于MyBatis读取Mapper文件的一个坑_mybatis读取resources下的mapper文件-程序员宅基地

文章浏览阅读1.9k次。最近在Idea上开发MyBatis,准备随便先写一点东西,结果一写就出了问题。Exception in thread "main" org.apache.ibatis.exceptions.PersistenceException: ### Error querying database. Cause: java.lang.IllegalArgumentException: Mapped S..._mybatis读取resources下的mapper文件

数据比你更懂用户:Tensorflow2 情感分析实战-程序员宅基地

文章浏览阅读496次。楔子达尔文曾说过,情感在人类的进化过程中起到了非常重要的作用。但他一定没有想到,有一天,机器也能读懂人类的情感了。把情感引入计算机学科,把 “主观的情感” 变得可计算,最早可追溯到上世纪..._tensorflow 分析用户收藏

推荐文章

热门文章

相关标签