2-3树

✍ dations ◷ 2025-10-24 20:56:30 #树结构,数据结构

计算机科学中,2–3树是一种树型数据结构,内部节点(存在子节点的节点)要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素。

2–3树由约翰·霍普克洛夫特于1970年发明。

2节点

3节点

2–3树和AA树是等距同构的,意味着它们是同一种数据结构。换句话说,对于每个2–3树,都至少有1个AA树和它的元素排列是相同的。2–3树是平衡树,意味着右边,左边,中间的子树的元素数量都是相同或接近的。

如果一个内部节点拥有一个数据元素、两个子节点,则此节点为2节点。

如果一个内部节点拥有两个数据元素、三个子节点,则此节点为3节点。

当且仅当以下叙述中有一条成立时,T为2–3树:

2–3树的查找元素操作与二叉搜索树的查找类似。因为节点中的数据元素都是有序的,所以查找函数可以据此进入正确的子树进行查找,最终找到正确的节点。

进行插入操作时,可以先通过查找操作确定合适的位置,然后将数据插入对应节点。如果插入后的节点变成4节点(包含三个数据元素),则需将该节点拆分为两个2节点,中间的数据元素进入父节点。这样一来,该父节点也可能也会因此变成4节点,则该父节点也会拆分为两个2节点,中间的数据元素进入该父节点的父节点,以此类推,直到修改后的父节点不需要分裂,或者被拆分的是根节点,此时中间数据元素就会单独形成2节点,成为新的根节点。

相关

  • 意大利共和国日意大利共和国日 (意大利语:Festa della Repubblica)是意大利的国庆日,在每年的6月2日庆祝,以纪念意大利在1946年6月2日至3日以公民投票形式废君主国体并建立共和国体。主要庆祝活
  • 四大发明四大发明是关于中国科学技术史的一种观点,是指古代中国的四种发明,一般是指造纸术、指南针、火药及印刷术。“三大发明”最早由英国哲学家弗兰西斯·培根提出,后来被麦都思、马
  • 马丁·福勒马丁·福勒(英语:Martin Fowler,1963年-),生于英国英格兰沃尔索尔,软件工程师,也是一个软件开发方面的著作者和国际知名演说家,专注于面向对象分析与设计,统一建模语言,领域建模,以及敏
  • Nasub2/subHsub2/subPsub2/subOsub7/sub>酸式焦磷酸钠,化学式Na2H2P2O7。酸式焦磷酸钠是一种白色单斜结晶性粉末或熔融状固体,溶于水,不溶于乙醇。稍有吸湿性,吸水后形成六水合物。水溶液用稀酸加热则水解成磷酸。加热
  • 库内纳河库内纳河(安哥拉︰Cunene River,纳米比亚︰Kunene River)是南部非洲的河流,从安哥拉的高地流经与纳米比亚接壤的边界进入大西洋,是区内常流河之一。库内纳河全长1,050公里(652英哩),流域
  • 五秒规则五秒规则或称、五秒钟理论、五秒不沾菌、五秒钟定律等,是一种世界范围内广泛存在的迷信说法。是一种判断掉在地上的食物是否可以食用的方法。其核心理论阐述为:如果食物掉在地
  • 阿拉斯代尔·麦金泰尔阿拉斯代尔·查莫斯·麦金泰尔(Alasdair Chalmers MacIntyre,1929年1月12日-)出生于苏格兰格拉斯哥,哲学家,在道德哲学、政治哲学、哲学史和神学等领域都作出了杰出的贡献。他目前
  • 教会大楼教会大楼(Church Office Building)是位于美国犹他州盐湖城的一座28层建筑,也是耶稣基督后期圣徒教会的总部办公地点。教会大楼高128米,修建于1962年至1972年,耗资3100万美元。参
  • 阿帕斯檀跋阿帕斯檀跋(印地语:आपस्तंब;英语:Āpastamba),古印度几何学家,生活在公元前600年前后,著有《阿帕斯檀跋法经》(Āpastamba Dharmasūtra),是《乔达摩法经》和《达耶那法经》的系
  • 欲女《欲女》(英文:),又名《悍妇岗》,1999年5月12日上映的伦理片和情色片。大日本帝国侵华期间,大日本帝国在东北扶持清朝末代皇帝爱新觉罗·溥仪建立满洲国,溥仪为傀儡,听从大日本帝国