2-3树

维基百科,自由的百科全书
跳到导航 跳到搜索
2-3樹
类型
发明时间 1970
发明者 約翰·霍普克洛夫特
大O符号时间复杂度
算法 平均 最差
空间 O(n) O(n)
搜索 O(log n) O(log n)
插入 O(log n) O(log n)
删除 O(log n) O(log n)

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

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

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

定义[编辑]

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

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

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

  • T为空。即T不包含任何节点。
  • T为拥有数据元素a的2节点。若T的左孩子为L、右孩子为R,则
    • LR是等高的非空2–3树;
    • a大于L中的所有数据元素;同时
    • a小于等于R中的所有数据元素。
  • T为拥有数据元素ab的3节点,其中a < b。若T的左孩子为L、中孩子为M、右孩子为R,则
    • LM、和R是等高的非空2–3树;
    • a大于L中的所有数据元素,并且小于等于M中的所有数据元素;同时
    • b大于M中的所有数据元素,并且小于等于R中的所有数据元素。

链接[编辑]

参考文献[编辑]

  1. ^ Cormen, Thomas. Introduction to Algorithms. London: The MIT Press. 2009: 504. ISBN 978-0262033848.