ZSGG_ACM
2016-05-19 01:23
采纳率: 100%
浏览 6.2k
已采纳

C++中的STL标准库map为什么是用红黑树,而不是用其它的平衡二叉搜索树

C++中的STL标准库map为什么是用红黑树,而不是用其它的平衡二叉搜索树

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • oyljerry 2016-05-19 01:47
    已采纳

    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.

    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.

    Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

    点赞 评论
  • ZSGG_ACM 2016-05-19 01:24

    面试的时候,被问到了,一脸懵逼,只说了红黑树的节点可以保存更多的信息

    点赞 评论
  • sayes01 2016-05-19 01:27

    一个红黑树的节点,有左右节点指针,和父节点指针,这就是三个指针的大小+value_type的大小;
    unordered_map呢,开放地址法,就value_type,如果是开链法,那就是prev指针和next指针,俩指针+value_type

    也就是说,当你的value_type越小,红黑树越浪费内存.
    而hash table呢,主要是填充因子,比如0.5的填充因子,那么那些桶是要浪费一些内存的.

    点赞 评论