问题描述
为什么std :: map实现为？
Why is std::map implemented as a red-black tree?
有几个平衡的（BST）。
There are several balanced binary search trees (BSTs) out there. What were design trade-offs in choosing a red-black tree?
推荐答案
可能两种最常见的自平衡树算法是红黑树和。为了在插入/更新之后平衡树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新平衡。
Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.
在这两种算法中，插入/删除操作是O（log n），在Red-Black树的情况下，重新平衡轮换是操作，而AVL这是一个操作，使Red-Black树在重新平衡阶段的这个方面更有效率，而且是更常用的可能原因之一
While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.
大多数集合库都使用红黑树，包括来自Java和Microsoft .NET Framework的产品。
Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.
这篇关于为什么std :: map实现为一个红黑树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！