map底层为什么要用红黑树实现
Map 实现 为什么 底层 要用
2023-09-27 14:27:45 时间
红黑树的特点
红黑树是二叉查找树,但在每个节点增加一个存储为表示节点的颜色,可以是红色或黑色(非红即黑),通过对任意一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其他路径长两倍。因此,它是一种弱平衡二叉树,相对于严格的AVL树来说,它的旋转次数少,所以对于查找、插入、删除较多的情况下,通常使用红黑树。
红黑树与AVL比较:
1. AVL是严格平衡的,频繁的插入和删除,会引起频繁的rebalance,导致效率降低;红黑树是弱平衡的,算是一种折中,插入最多旋转2次,删除最多旋转3次。
所以红黑树在查找、插入删除的复杂度都是O(logn),且性能稳定,所以STL里面很多结构包括map底层都是使用的红黑树。
相关文章
- 报错:(未解决)java.lang.VerifyError: Instruction type does not match stack map
- ‘map’ does not name a type
- C/C++知识要点2——STL中Vector、Map、Set容器的实现原理
- Go map中一个很重要的特性
- Google Earth Engine(GEE)——两种方式进行数据的遍历map和iterate的使用
- Java.util.Map的常用实现类有哪些?
- Map的实现类中,哪些是有序的,哪些是无序的,如何保证其有序性?
- ES6 通过 set 和 map 实现对象数组去重
- 32 MAPREDUCE的map端join算法实现
- Map Task内部实现分析
- 让 webpack 加载 Source Map
- ES6新特性:Javascript中的Map和WeakMap对象
- MapReduce案例—分别通过Reduce端和Map端实现JOIN操作
- 浅析Golang map的实现原理
- java Map接口
- SwiftUI 内功之整合腾讯地图map实现地图导览卫星路况手绘大头钉合集 在Swift中使用Objective-C类(教程含源码)
- MAP的get与containskey
- Collection与Map的对比
- 微信小程序~map组件z-index无效
- 使用Jackson实现Map与Bean互转
- 如何实现JavaScript的Map和Filter函数?
- 【Map与Set】之LeetCode&牛客练习
- JS 实现Map
- java程序:set改造成map
- C++ unordered_map remove 实现哈希表移除
- Java list、map、set、vector集合类型中的null值