为什么我们不使用2-3或2-3-4-5树？

Question

我对2-3-4树在操作后如何维持高度平衡属性操作有了基本的了解,以确保即使最坏的情况操作也是O(n logn).

但我不明白它知道为什么只有2-3-4？

为什么不2-3或2-3-4-5等？

Answer 1

2-3-4树的实现通常需要多个类(2NODE,3NODE,4NODE)或者您只有具有项目数组的NODE.在多个类的情况下,您浪费了大量时间来构造和破坏节点实例并重新创建它们是麻烦的.如果您使用带有数组的单个类来保存项目和子项,那么您要么不断地调整数组的大小,这同样是浪费的,或者您在未使用的数组元素上浪费了超过一半的内存.与红黑树相比,它效率不高.

红黑树只有一种节点结构.由于红黑树具有2-3-4树的二元性,RB树可以使用与2-3-4树完全相同的算法(不需要在Cormen,Leiserson和Rivest中描述的愚蠢混淆/复杂实现到AA树,其复杂程度不低于2-3-4算法.)

因此,Red-Black树易于实现,还有内存/ CPU效率.(AVL树也很好.它们可以生成更平衡的树,并且只是简单地编写代码,但由于过于频繁地只维护一个稍微紧凑的树,它们往往效率较低.)

哦,2-3-4-5-6 ......等等都没有完成,因为没有获得任何东西.2-3-4具有超过2-3个树的净增益,因为它们可以在没有递归的情况下完成(递归往往效率较低,尤其是当它不能以递归方式编码时).但是,B-Trees和Bplus-Trees几乎是2-3-4-5-6-7-8-9-etc树,其中选择节点的最大大小n,以便可以存储n个记录单个磁盘扇区.(即每个磁盘扇区是树中的一个节点,扇区的大小等于节点中存储的项目数.)这是因为在内存中线性搜索512条记录的时间仍然比遍历下来快得多树中的一个级别,需要另一个磁盘搜索/获取.并且O(512)仍然是O(1)并因此保持树的O(lg n).

Answer 2

说实话，我不知道2-3-4树。在我的数据结构课上，我们学习了 2-3 棵树，说实话，我们大多数人都在练习的湿部分实现了 AVL 树。

但显然，这种类型的树有一个概括： (a,b) 树。