为什么std :: map实现为一个红黑树？ [英] Why is std::map implemented as a red-black tree?

问题描述

为什么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?

推荐答案

可能两种最常见的自平衡树算法是<一个href =http://en.wikipedia.org/wiki/Red-black_tree =noreferrer>红黑树和 AVL树。为了在插入/更新之后平衡树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新平衡。

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树的情况下，重新平衡轮换是 O（1）操作，而AVL这是一个 O（log n）操作，使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实现为一个红黑树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！