为什么将std::map实现为red-black tree？
那里有几个平衡的binary search trees(BST)。选择红黑树时在设计上要进行哪些取舍？
最佳答案
两种最常见的自平衡树算法可能是Red-Black trees和AVL trees。为了在插入/更新之后平衡树，两种算法都使用旋转的概念，在该概念中，树的节点被旋转以执行重新平衡。
在两种算法中，插入/删除操作均为O(log n)，在红黑树重新平衡旋转的情况下，它是O(1)操作，而在AVL中，这是O(log n)操作，这使得红黑树在重新平衡阶段的这一方面，以及更常用的可能原因之一。
红黑树用于大多数集合库中，包括Java和Microsoft .NET Framework提供的产品。