algorithm - 红黑树在avl树

除了节点中的红色和黑色外，AVL和红色黑树都是自平衡的。选择红黑树而不是AVL树的主要原因是什么？红黑树有哪些应用？

最佳答案

red-black trees和AVL trees都是最常用的balanced binary search trees，它们都支持在有保证的O(logN) time中进行插入，删除和查找。但是，两者之间存在以下比较点:

AVL树更加严格地平衡，因此提供了更快的查找。因此，对于查找密集型任务，请使用AVL树。

对于密集型任务，请使用红黑树。

AVL树在每个节点上存储平衡因子。这需要O(N)额外的空间。但是，如果我们知道将要插入树中的键始终大于零，则可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，红黑树不会占用额外的空间。

红黑树是更通用的用途。它们在添加，删除和查找方面做得相对不错，但AVL树的查找速度更快，但添加/删除速度较慢。红黑树用于以下用途:

Java: java.util.TreeMap ， java.util.TreeSet

C++ STL(在大多数实现中):映射，多图，多集

Linux内核:完全公平的调度程序，linux / rbtree.h