std::map会自动平衡吗?

lxyscls

回复 1# asker160

什么是“自动平衡”？还有“自动平衡”的平衡二叉树和“不自动平衡”的平衡二叉树？
红黑树所有路径的黑节点数目保持一致且红节点不能相连，也就是说最长的路径只会比最短的多一倍，也就是说不存在你所讲的单条路径长度等于N的情况，这算不算是“自动平衡”的结果呢？

lxyscls

yulihua49 发表于 2016-12-26 12:14
插、删比全平衡快很多。检索略慢。

插入3种情况，删除4种情况

插入是log(N)次着色+1次rotate

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

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.