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

链接[编辑]