相关疑难解决方法(0)

红黑树的应用是什么？是否有任何应用程序只能使用RB树而没有其他数据结构？

用于链接存储器映射的可执行文件的各个部分的vm_area_struct结构存储为红黑树.现在,据我所知和这里的帖子提到太红黑树和AVL树之间的区别 AVL树比RB树执行更快的查找.

此树由进程引用的虚拟地址编制索引,并在进程开始执行时创建.我希望这棵树可以用于查找,有时也可以用于插入和删除.如果是这种情况,那么为什么AVL树不优于RB树作为相同的实现.

此外,如果我的理解不正确并且树涉及大量插入和删除,与查找相比,请提供参考以支持此声明.

我已经看到一些关于tldp的文章提到早期的AVL树也被用于相同的文章.请解释这种变化带来的原因是什么？

据我所知,AVL树和二进制搜索树之间的时间复杂度在平均情况下是相同的,在最坏的情况下AVL击败BST.这给了我一个提示,即AVL总是优于BST以各种可能的方式与它们进行交互,在平衡实现方面可能会增加一些复杂性.

是否有任何理由首先应该使用BST而不是AVL？

是O(1)还是O(logN)但系数较小？

如果这是未指定的,我至少想知道基于合理假设的答案,即地图/集是使用红黑或AVL树实现的.我认为,插入元素的一般算法是这样的:

• 找到合适的地方 - O(logN)
• 做实际插入 - ？
• 必要时重新平衡树 - ？

现在,如果我们提供正确的迭代器提示,那么第一步就变成O(1).其他步骤是O(1)还是O(logN)？

为什么有人会喜欢红黑树到安德森树,因为后者比前者简单得多,据说它在实践中达到了几乎相同的性能？