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

推荐答案

可能两个最常见的自平衡树算法< a href =http://en.wikipedia.org/wiki/Red-black_tree>红黑树和 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），在红黑树的情况下，重新平衡旋转是O(1）操作，而使用AVL时，这是一个 O（log n）操作，使得红黑树在重新平衡阶段的这个方面更有效，并且是更常使用的可能原因之一。

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屋！