std::map会自动平衡吗?

windoze

不会自动平衡的树肯定不是红黑树。

action08

楼上是学逻辑哲学的，说得也对，鼓掌

action08

回复 9# lxyscls

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




红黑树实时性强，100次每次插入都在1-2秒之间

avl这种树的缺点，可能100次插入用了1秒钟，第101次插入用了50秒钟

打比方的数值不真实代表场景数值，仅供参考性理解

cjaizss

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

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

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

action08

回复 14# cjaizss

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

sditmaner

支持一下 楼主加油

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.

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.

mr_sev

既然是红黑树肯定自平衡

mr_sev

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