计算机科学中，2–3树（）是一种树型数据结构，由约翰·霍普克洛夫特于1970年发明。
2–3樹中的内部节点可以有2个子節點和1个数据元素、或有3个子節點和2个数据元素，叶子节点有1至2个数据元素。
File:2-3-4 tree 2-node.svg|2节点
File:2-3-4-tree 3-node.svg|3节点
2–3树和AA树是等距同构的，意味着它们是同一种数据结构。换句话说，对于每个2–3树，都至少存在1種AA树和它的元素排列是相同的。2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。
定义
如果一个内部节点拥有一个数据元素、两个子节点，则此节点为2节点。
如果一个内部节点拥有两个数据元素、三个子节点，则此节点为3节点。
当且仅当以下叙述中有一条成立时，为2–3树：
- 为空。即不包含任何节点。
- 为拥有数据元素的2节点。若的左子節點为、右子節點为，则：
** 和是等高的2–3树；
** 大于中的所有数据元素；同时
** 小于等于中的所有数据元素。
- 为拥有数据元素和的3节点，其中 。若的左子節點为、中子節點为、右子節點为，则：
** 、、和是等高的2–3树；
** 大于中的所有数据元素，并且小于等于中的所有数据元素；同时
** 大于中的所有数据元素，并且小于等于中的所有数据元素。
操作
查找
2–3树的查找元素操作与二叉搜索树的查找类似。因为节点中的数据元素都是有序的，所以查找函数可以据此进入正确的子树进行查找，最终找到正确的节点。
插入
进行插入操作时，可以先通过查找操作确定合适的位置，然后将数据插入对应节点。如果插入后的节点变成4节点（包含三个数据元素），则需将该节点拆分为两个2节点，中间的数据元素进入父节点。这样一来，该父节点也可能也会因此变成4节点，则该父节点也会拆分为两个2节点，中间的数据元素进入该父节点的父节点，以此类推，直到修改后的父节点不需要分裂，或者被拆分的是根节点，此时中间数据元素就会单独形成2节点，成为新的根节点。
刪除
從非葉子節點刪除一個鍵，可以先用它的直接前驅或後繼來替換，然後再到葉子節點中刪除這個前驅或後繼。
從葉子節點刪除一個鍵就比較簡單，若該葉子是 3-節點，直接刪掉即可。否則，刪除後可能會產生一個暫時的 1-節點，而這個 1-節點可能需要透過調整樹來「吸收」。這個調整過程可能會一路向上傳遞，類似插入操作中可能產生暫時的 4-節點再被分裂的情況。
另一種方法是採用一種「自上而下與自下而上結合」的演算法：在往下搜尋的過程中，暫時建立 4-節點，等到返回往上時再將這些暫時節點銷毀
平行操作
由於 2–3 樹在結構上與紅黑樹相似，因此針對紅黑樹設計的平行演算法同樣也可以套用在 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]
- [http://v2matveev.blogspot.com/2010/03/data-structures-2-3-tree.html 2–3 Tree in F#]
- [http://code.google.com/p/risboo6909/source/browse/trunk/23tree/tttree.py 2–3 Tree in Python]
参考文献
评论 (0)