std::map会自动平衡吗?
std::map会自动平衡吗?我想知道，主流STL的map/set用红黑树实现，这个红黑树会做自动的2叉树平衡吗?
考虑最坏的情况，每次带插入的元素都是排序过的，那么:
不自动平衡的树就相当于每次都插入到最右的子树，查找元素最差就是O(n)了。
想知道答案
我感觉标准库的实现者应该会尽量把这类问题都考虑在内的。 用最简单的回复回答你，红黑树会自动做平衡。 本帖最后由 shang2010 于 2016-12-24 20:38 编辑
运行时自动平衡，这个是有性能担保的，你放心好了。
这些算法是可以用来管理核武器的，
你知道是用红黑树了，却不知道红黑树是啥所以才有这疑问。 shang2010 发表于 2016-12-24 20:36
用最简单的回复回答你，红黑树会自动做平衡。
但是不是彻底的平衡。最深与最浅深度相差不超过1倍。
回复 1# asker160
什么是“自动平衡”？还有“自动平衡”的平衡二叉树和“不自动平衡”的平衡二叉树？{:yct26:}
红黑树所有路径的黑节点数目保持一致且红节点不能相连，也就是说最长的路径只会比最短的多一倍，也就是说不存在你所讲的单条路径长度等于N的情况，这算不算是“自动平衡”的结果呢？
lxyscls 发表于 2016-12-26 09:25
回复 1# asker160
什么是“自动平衡”？还有“自动平衡”的平衡二叉树和“不自动平衡”的平衡二叉树？{ ...
插、删比全平衡快很多。检索略慢。
yulihua49 发表于 2016-12-26 12:14
插、删比全平衡快很多。检索略慢。
插入3种情况，删除4种情况
插入是log(N)次着色+1次rotate
话说AVL树是不是没人用了？
lxyscls 发表于 2016-12-26 13:52
插入3种情况，删除4种情况
插入是log(N)次着色+1次rotate
AVL树继续用。要求平衡度高的场合。