std::map会自动平衡吗?

asker160

std::map会自动平衡吗?
我想知道，主流STL的map/set用红黑树实现，这个红黑树会做自动的2叉树平衡吗?
考虑最坏的情况，每次带插入的元素都是排序过的，那么:
不自动平衡的树就相当于每次都插入到最右的子树，查找元素最差就是O(n)了。

想知道答案

action08

lxyscls 发表于 2016-12-26 09:25
回复 1# asker160

什么是“自动平衡”？还有“自动平衡”的平衡二叉树和“不自动平衡”的平衡二叉树？{ ...

咬文嚼字，做技术跟做人一样，都是靠悟性

shang2010

听不懂你们在说什么，

mr_sev

满足红黑树的特性 必须要左旋右旋降低高度来平衡

mr_sev

既然是红黑树肯定自平衡

action08

AVL trees require storing 2 bits (or one trit) of information in each node, while red-black trees require just one bit per node. The bigger difference between the two data structures is their height limit.

lxyscls

回复 14# cjaizss

AVL树对红黑树的劣势不在这里,而在整体统计上,红黑树时间较少.

Both AVL trees and red–black trees are self-balancing binary search trees and they are related mathematically. Indeed, every AVL tree can be colored red–black.[citation needed] The operations to balance the trees are different; both AVL trees and red-black require O(1) rotations in the worst case, while both also require O(log n) other updates (to colors or heights) in the worst case (though only O(1) amortized). AVL trees require storing 2 bits (or one trit) of information in each node, while red-black trees require just one bit per node. The bigger difference between the two data structures is their height limit.

sditmaner

支持一下 楼主加油

action08

回复 14# cjaizss

AVL 树我都没有听说过，不过红黑树的算法倒是在算法导论里面看过

cjaizss

action08 发表于 2016-12-29 12:33
回复 9# lxyscls

话说AVL树是不是没人用了？

AVL树的插入最坏情况也是对数级别,不会发生你说的情况.AVL树对红黑树的劣势不在这里,而在整体统计上,红黑树时间较少.
另外,AVL树是绝对的平衡,红黑树不是.