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–3 tree）是一种树型数据结构，由约翰·霍普克洛夫特于1970年发明。

2–3树中的内部节点可以有2个子节点和1个数据元素、或有3个子节点和2个数据元素，叶子节点有1至2个数据元素。

• 
  2节点
• 
  3节点

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

定义

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

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

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

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

操作

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

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

2-3树插入操作的三种情况

外部链接

• 2–3 Trees Complete Description
• 2–3 Tree Java Applet
• 2–3 Tree In-depth description（页面存档备份，存于互联网档案馆）
• 2–3 Tree in F#（页面存档备份，存于互联网档案馆）
• 2–3 Tree in Python（页面存档备份，存于互联网档案馆）