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

问题描述

为什么 std::map 实现为 红黑树?

有几种平衡的二元搜索树 (BST).选择红黑树的设计权衡是什么?

There are several balanced binary search trees (BSTs) out there. What were design trade-offs in choosing a 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屋！