問題描述
為什么 std::map 實現(xiàn)為 紅黑樹?
有幾種平衡的二元搜索樹 (BST).選擇紅黑樹的設(shè)計權(quán)衡是什么?
There are several balanced binary search trees (BSTs) out there. What were design trade-offs in choosing a red-black tree?
推薦答案
可能兩種最常見的自平衡樹算法是 紅黑樹 和AVL 樹.為了在插入/更新后平衡樹，兩種算法都使用旋轉(zhuǎn)的概念，其中樹的節(jié)點被旋轉(zhuǎn)以執(zhí)行重新平衡.
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)，但在紅黑樹重新平衡旋轉(zhuǎ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.
紅黑樹用于大多數(shù)集合庫，包括來自 Java 和 Microsoft .NET Framework 的產(chǎn)品.
Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.
這篇關(guān)于為什么 std::map 實現(xiàn)為紅黑樹?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！