2-3树
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
2-3树 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | 树 | ||||||||||||||||||||
发明时间 | 1970 | ||||||||||||||||||||
发明者 | 约翰·霍普克洛夫特 | ||||||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||||||
|
电脑科学中,2–3树(英语:2–3 tree)是一种树型数据结构,由约翰·霍普克洛夫特于1970年发明[1]。
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节点,成为新的根节点。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/4/44/2-3_insertion.svg/800px-2-3_insertion.svg.png)
外部链接
- 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(页面存档备份,存于互联网档案馆)
参考文献
- ^ Cormen, Thomas. Introduction to Algorithms. London: The MIT Press. 2009: 504. ISBN 978-0262033848.
|
|