binary-tree - 2-3-4树的应用

Question

2-3-4树有哪些应用？它们是否广泛用于应用程序以提供更好的应用程序性能？

编辑 :哪些算法最能利用 2-3-4 棵树？

Answer 1

2-3-4 树是自平衡的，通常对于查找、添加和删除元素通常非常有效，因此与所有树一样，它们可用于以非线性顺序存储和检索元素。不幸的是，它们往往比其他树使用更多的内存，因为即使只有 2 个数据项的节点仍然需要有足够的内存来存储其中的 4 个。

这就是为什么使用 2-3-4 树作为红黑树模型的原因，红黑树与标准 BST 类似，只是节点可以是红色或黑色，并且存在关于如何选择节点颜色的各种规则。

关键是在 2-3-4 树中搜索/添加/删除的算法与红黑树的算法非常相似，因此通常研究 2-3-4 树作为理解红黑的一种方式树木。红黑树本身的使用非常广泛——我相信标准的 Java 集合框架树是一棵红黑树。