免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › std::map会自动平衡吗?
123下一页
最近访问板块 发新帖
查看: 4240 | 回复: 22
打印 上一主题 下一主题

[C++] std::map会自动平衡吗? [复制链接]

asker160

论坛徽章:
1
2015年迎新春徽章 日期:2015-03-04 09:58:11
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2016-12-24 18:10 |只看该作者 |倒序浏览
std::map会自动平衡吗?
我想知道，主流STL的map/set用红黑树实现，这个红黑树会做自动的2叉树平衡吗?
考虑最坏的情况，每次带插入的元素都是排序过的，那么:
不自动平衡的树就相当于每次都插入到最右的子树，查找元素最差就是O(n)了。

想知道答案


平衡
fender0107401

论坛徽章:
89
水瓶座 日期:2014-04-01 08:53:31天蝎座 日期:2014-04-01 08:53:53天秤座 日期:2014-04-01 08:54:02射手座 日期:2014-04-01 08:54:15子鼠 日期:2014-04-01 08:55:35辰龙 日期:2014-04-01 08:56:36未羊 日期:2014-04-01 08:56:27戌狗 日期:2014-04-01 08:56:13亥猪 日期:2014-04-01 08:56:02亥猪 日期:2014-04-08 08:38:58程序设计版块每日发帖之星 日期:2016-01-05 06:20:00程序设计版块每日发帖之星 日期:2016-01-07 06:20:00
2楼 [报告]
发表于 2016-12-24 20:28 |只看该作者
我感觉标准库的实现者应该会尽量把这类问题都考虑在内的。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
shang2010

论坛徽章:
154
2022北京冬奥会纪念版徽章 日期:2015-08-07 17:10:5720周年集字徽章-年 日期:2022-10-26 16:44:2015-16赛季CBA联赛之深圳 日期:2022-11-02 14:02:4515-16赛季CBA联赛之八一 日期:2022-11-28 12:07:4820周年集字徽章-20 日期:2023-07-19 08:49:4515-16赛季CBA联赛之八一 日期:2023-11-04 19:23:5115-16赛季CBA联赛之广夏 日期:2023-12-13 18:09:34
3楼 [报告]
发表于 2016-12-24 20:36 来自手机 |只看该作者
用最简单的回复回答你，红黑树会自动做平衡。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
shang2010

论坛徽章:
154
2022北京冬奥会纪念版徽章 日期:2015-08-07 17:10:5720周年集字徽章-年 日期:2022-10-26 16:44:2015-16赛季CBA联赛之深圳 日期:2022-11-02 14:02:4515-16赛季CBA联赛之八一 日期:2022-11-28 12:07:4820周年集字徽章-20 日期:2023-07-19 08:49:4515-16赛季CBA联赛之八一 日期:2023-11-04 19:23:5115-16赛季CBA联赛之广夏 日期:2023-12-13 18:09:34
4楼 [报告]
发表于 2016-12-24 20:37 来自手机 |只看该作者
本帖最后由 shang2010 于 2016-12-24 20:38 编辑

运行时自动平衡，这个是有性能担保的，你放心好了。
这些算法是可以用来管理核武器的，
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cokeboL

论坛徽章:
36
子鼠 日期:2013-08-28 22:23:29黄金圣斗士 日期:2015-12-01 11:37:51程序设计版块每日发帖之星 日期:2015-12-14 06:20:00CU十四周年纪念徽章 日期:2015-12-22 16:50:40IT运维版块每日发帖之星 日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳 日期:2016-01-27 10:31:172016猴年福章徽章 日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建 日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛 日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控 日期:2016-06-20 17:38:50技术图书徽章 日期:2016-07-19 13:54:03程序设计版块每日发帖之星 日期:2016-08-21 06:20:00
5楼 [报告]
发表于 2016-12-25 11:02 |只看该作者
你知道是用红黑树了，却不知道红黑树是啥所以才有这疑问。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
yulihua49

论坛徽章:
15
射手座 日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛 日期:2017-11-17 13:20:09黑曼巴 日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川 日期:2017-02-07 21:08:572015年亚冠纪念徽章 日期:2015-11-06 12:31:58每日论坛发贴之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-07-12 22:20:002015亚冠之浦和红钻 日期:2015-07-08 10:10:132015亚冠之大阪钢巴 日期:2015-06-29 11:21:122015亚冠之广州恒大 日期:2015-05-22 21:55:412015年亚洲杯之伊朗 日期:2015-04-10 16:28:25
6楼 [报告]
发表于 2016-12-25 17:16 |只看该作者
shang2010 发表于 2016-12-24 20:36
用最简单的回复回答你，红黑树会自动做平衡。

但是不是彻底的平衡。最深与最浅深度相差不超过1倍。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
lxyscls

论坛徽章:
14
水瓶座 日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏 日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一 日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林 日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏 日期:2016-06-23 09:53:58程序设计版块每日发帖之星 日期:2016-02-11 06:20:00程序设计版块每日发帖之星 日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海 日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏 日期:2015-12-22 09:39:36程序设计版块每日发帖之星 日期:2015-08-24 06:20:002015亚冠之德黑兰石油 日期:2015-08-07 09:57:302015年辞旧岁徽章 日期:2015-03-03 16:54:15
7楼 [报告]
发表于 2016-12-26 09:25 |只看该作者
回复 1# asker160

什么是“自动平衡”？还有“自动平衡”的平衡二叉树和“不自动平衡”的平衡二叉树？
红黑树所有路径的黑节点数目保持一致且红节点不能相连，也就是说最长的路径只会比最短的多一倍，也就是说不存在你所讲的单条路径长度等于N的情况，这算不算是“自动平衡”的结果呢？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
yulihua49

论坛徽章:
15
射手座 日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛 日期:2017-11-17 13:20:09黑曼巴 日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川 日期:2017-02-07 21:08:572015年亚冠纪念徽章 日期:2015-11-06 12:31:58每日论坛发贴之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-07-12 22:20:002015亚冠之浦和红钻 日期:2015-07-08 10:10:132015亚冠之大阪钢巴 日期:2015-06-29 11:21:122015亚冠之广州恒大 日期:2015-05-22 21:55:412015年亚洲杯之伊朗 日期:2015-04-10 16:28:25
8楼 [报告]
发表于 2016-12-26 12:14 |只看该作者
lxyscls 发表于 2016-12-26 09:25
回复 1# asker160

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

插、删比全平衡快很多。检索略慢。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
lxyscls

论坛徽章:
14
水瓶座 日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏 日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一 日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林 日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏 日期:2016-06-23 09:53:58程序设计版块每日发帖之星 日期:2016-02-11 06:20:00程序设计版块每日发帖之星 日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海 日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏 日期:2015-12-22 09:39:36程序设计版块每日发帖之星 日期:2015-08-24 06:20:002015亚冠之德黑兰石油 日期:2015-08-07 09:57:302015年辞旧岁徽章 日期:2015-03-03 16:54:15
9楼 [报告]
发表于 2016-12-26 13:52 |只看该作者
yulihua49 发表于 2016-12-26 12:14
插、删比全平衡快很多。检索略慢。

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

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

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

评分

参与人数 1信誉积分 +5 收起 理由
action08 + 5 赞一个!

查看全部评分

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
yulihua49

论坛徽章:
15
射手座 日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛 日期:2017-11-17 13:20:09黑曼巴 日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川 日期:2017-02-07 21:08:572015年亚冠纪念徽章 日期:2015-11-06 12:31:58每日论坛发贴之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-08-04 06:20:00程序设计版块每日发帖之星 日期:2015-07-12 22:20:002015亚冠之浦和红钻 日期:2015-07-08 10:10:132015亚冠之大阪钢巴 日期:2015-06-29 11:21:122015亚冠之广州恒大 日期:2015-05-22 21:55:412015年亚洲杯之伊朗 日期:2015-04-10 16:28:25
10楼 [报告]
发表于 2016-12-28 21:09 |只看该作者
lxyscls 发表于 2016-12-26 13:52
插入3种情况，删除4种情况

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

AVL树继续用。要求平衡度高的场合。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP