查看“︁2-3树”︁的源代码

{{NoteTA
|G1= IT
}}
{{Infobox data structure
|name=2-3樹
|type=[[树 (数据结构)|樹]]
|invented_by=[[約翰·霍普克洛夫特]]
|invented_year=1970
|
|space_avg= <math>O(n)</math>
|space_worst= <math>O(n)</math>
|search_avg= <math>O(\log n)</math>
|search_worst= <math>O(\log n)</math>
|insert_avg= <math>O(\log n)</math>
|insert_worst= <math>O(\log n)</math>
|delete_avg= <math>O(\log n)</math>
|delete_worst= <math>O(\log n)</math>
}}

[[计算机科学]]中，'''2–3树'''（{{lang-en|2–3 tree}}）是一种[[树 (数据结构)|树型数据结构]]，由[[約翰·霍普克洛夫特|约翰·霍普克洛夫]]特于1970年发明<ref>{{Cite book|title = Introduction to Algorithms|url = https://archive.org/details/introductiontoal00corm_558|last = Cormen|first = Thomas|publisher = The MIT Press|year = 2009|isbn = 978-0262033848|location = London|pages = [https://archive.org/details/introductiontoal00corm_558/page/n524 504]}}</ref>。

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

<!-- Explanation of insert function needed -->
<gallery heights="95">
File:2-3-4 tree 2-node.svg|2节点
File:2-3-4-tree 3-node.svg|3节点
</gallery>

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

== 定义 ==

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

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

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

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

== 操作 ==

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

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

[[File:2-3 insertion.svg|thumb|800px|2-3树插入操作的三种情况]]

== 外部链接 ==
* [https://web.archive.org/web/20131008062759/http://www.cs.ucr.edu/cs14/cs14_06win/slides/2-3_trees_covered.pdf 2–3 Trees Complete Description]
* [https://web.archive.org/web/20081220033211/http://www.cosc.canterbury.ac.nz/mukundan/dsal/TwoThreeTree.html 2–3 Tree Java Applet]
* [http://www.aihorizon.com/essays/basiccs/trees/twothree.htm 2–3 Tree In-depth description]{{Wayback|url=http://www.aihorizon.com/essays/basiccs/trees/twothree.htm |date=20200917020831 }}
* [http://v2matveev.blogspot.com/2010/03/data-structures-2-3-tree.html 2–3 Tree in F#]{{Wayback|url=http://v2matveev.blogspot.com/2010/03/data-structures-2-3-tree.html |date=20200917030631 }}
* [http://code.google.com/p/risboo6909/source/browse/trunk/23tree/tttree.py 2–3 Tree in Python]{{Wayback|url=http://code.google.com/p/risboo6909/source/browse/trunk/23tree/tttree.py |date=20150612054639 }}

== 参考文献 ==
<references />

{{计算机科学中的树}}

{{Data structures}}

[[Category:树结构|B树]]