← 返回目录

1. 为什么既有2-3树要有红黑树

第 74 / 320 卷作者:付政委日期:

  1. 黑高,从任一节点到齐每个叶子节点,经过的路径都包含相同数目的黑色节点

那么,这些规则是怎么总结定义出来的呢?接下里我们一步步分析讲解。

1. 为什么既有 2-3 树要有红黑树

首先 2-3 树(读法:二三树)就是一个节点有 1 个或者 2 个元素,而实际上 2-3 树

转红黑树是由概念模型 2-3-4 树转换而来的。-4 叉就是一个节点里有 3 个元素,

这在 2-3 树中会被调整,但是在概念模型中是会被保留的。

虽然 2-3-4 树也是具备 2-3 树同样的平衡树的特性,但是如果直接把这样的模型

用代码实现就会很麻烦,且效率不高,这里的复杂点包括;

1.2-叉、3-叉、4-叉,三种结构的节点类型,互相转换复杂度较高 2.3-叉、4-叉,节点在数据比较上需要进行多次,不像 2-叉节点,直接布尔类型比

较即可非左即右

3.代码实现上对每种差异,都需要有额外的代码,规则不够标准化

所以,希望找到一种平衡关系,既保持 2-3 树平衡和 O(logn)的特性,又能在代

码实现上更加方便,那么就诞生了红黑树。

2. 简单 2-3 树转红黑树

2-3 树转红黑树,也可以说红黑树是 2-3 树和 2-3-4 树的另外一种表现形式,也就

是更利于编码实现的形式。

简单转换示例;

图 110-1
图 110-1

2-叉、3-叉、4-叉,转换红黑树示意图

全站分卷索引 · 320 卷
  1. 1介绍
  2. 23. 阅读建议
  3. 3目录
  4. 4第 5 章 JVM 虚拟机
  5. 5本书源码
  6. 6第 1 章 谈谈面试(4节)
  7. 7二、谢飞机简历
  8. 8三、面试框架
  9. 91. 自我介绍
  10. 103. 算法
  11. 114.1.2 Redis
  12. 124.2 框架
  13. 134.2.2 Mybatis
  14. 144.3.4 Hbase
  15. 154.5.4 分布式任务
  16. 165.3 技术沉淀
  17. 176. 个人&面试官
  18. 18第 2 节:认知自己的技术栈盲区
  19. 192. 汇总出来的技术栈列表
  20. 20二、汇总技术架构图
  21. 211. 负载
  22. 223. 架构
  23. 238. 环境
  24. 24一、我的简历都石沉大海
  25. 25二、修改后电话约面不断
  26. 26三、简历好也要做好准备
  27. 271.4 Rpc框架 - Dubbo
  28. 282. 源码理解
  29. 29五、总结
  30. 30第 4 节:大厂都爱聊啥
  31. 312. 地理位置
  32. 322. 大厂考题
  33. 332.1 阿里、百度、腾讯
  34. 343. 考点总结
  35. 35三、总结
  36. 36第 2 章 数据结构和算法(11节)
  37. 37二、资源下载
  38. 382. 来自stackoverflow的回答
  39. 393. Hash值碰撞概率统计
  40. 403.3 Hash碰撞概率计算
  41. 414. Hash值散列分布
  42. 424.1 哈希值分段存放
  43. 434.2.1 乘数2散列
  44. 44四、总结
  45. 45第 2 节:HashMap 源码分析(上)
  46. 461.1 代码实现
  47. 471.2 Hash散列示意图
  48. 481.3 这个简单的HashMap有哪些问题
  49. 492. 扰动函数
  50. 502.2 实验验证扰动函数
  51. 512.2.2 扰动函数散列图表
  52. 523. 初始化容量和负载因子
  53. 533.2 负载因子
  54. 544. 扩容元素拆分
  55. 554.2 数据迁移
  56. 56第 3 节:HashMap 源码分析(下)
  57. 573. 扩容机制
  58. 584. 链表树化
  59. 595. 红黑树转链
  60. 60二、查找
  61. 61三、删除
  62. 62四、遍历
  63. 633. 测试结果分析
  64. 64五、总结
  65. 65第 4 节:2-3树与红黑树学习(上)
  66. 662. 二叉搜索树退化链表
  67. 673. 2-3树解决平衡问题
  68. 68三、2-3树使用
  69. 692. 数据插入
  70. 703. 数据删除
  71. 714. 数据索引
  72. 72四、总结
  73. 73第 5 节:2-3树与红黑树学习(下)
  74. 741. 为什么既有2-3树要有红黑树
  75. 753. 复杂2-3树转红黑树
  76. 761.1 左旋转
  77. 771.3 左右旋综合运用
  78. 781.4 染色
  79. 793. 删除操作
  80. 803.2.1 被删节点兄弟为黑色&含右子节点
  81. 813.3. 删除右侧节点
  82. 82四、总结
  83. 83第 6 节:ArrayList 详细分析
  84. 84二、数据结构
  85. 851.1 方式01;普通方式
  86. 861.3.1 ArrayList构造函数
  87. 871.3.2 Arrays.asList
  88. 881.4 方式04;Collections.ncopies
  89. 892.2 插入时扩容
  90. 902.3 指定位置插入
  91. 912.3.2 元素迁移
  92. 923. 删除
  93. 934. 扩展
  94. 944.2 代码操作(获取元素)
  95. 95第 7 节:LinkedList、ArrayList,插入分析
  96. 96二、数据结构
  97. 97三、源码分析
  98. 982. 插入
  99. 992.1.1 源码
  100. 1002.1.2 验证
  101. 1012.2 尾插
  102. 1022.2.2 验证
  103. 1032.3 中间插
  104. 1042.3.1 源码
  105. 1052.3.2 验证
  106. 1063. 删除
  107. 1073.2 源码
  108. 1084. 遍历
  109. 1094.2 增强for循环
  110. 110四、总结
  111. 111第 8 节:双端队列、延迟队列、阻塞队列
  112. 112一、面试题
  113. 113二、数据结构
  114. 1141.1 功能使用
  115. 1151.2 源码分析
  116. 1162. 双端队列ArrayDeque
  117. 1172.1 功能使用
  118. 1182.2.1 初始化
  119. 1192.2.3 两倍扩容,数据迁移
  120. 1203. 双端队列LinkedList
  121. 1213.1 功能使用
  122. 1223.2 源码分析
  123. 1234. 延时队列DelayQueue
  124. 1244.2 源码分析
  125. 1254.2.2 元素出栈
  126. 1265. 还有哪些队列?
  127. 1275.2 使用案例
  128. 128四、总结
  129. 129第 9 节:java.util.Collections、排序、二分、洗牌、旋转算法
  130. 1301. Collections.sort 排序
  131. 1311.4 reverseOrder倒排
  132. 1322. Collections.binarySearch 二分查找
  133. 1332.2 源码分析
  134. 1343. Collections.shuffle 洗牌算法
  135. 1354. Collections.rotate 旋转算法
  136. 1364.1 功能应用
  137. 1374.2.1 旋转算法,rotate1
  138. 1384.2.2 旋转算法,rotate2
  139. 1395. 其他API介绍
  140. 1405.3 连续集合位置判断
  141. 141第 10 节:StringBuilder 与 String 对比
  142. 1421.1 String
  143. 1432. StringBuilder 比 String 快, 为什么?
  144. 144三、String 源码分析
  145. 1452. 不可变(final)
  146. 1463. intern()
  147. 1473.3 问题图解
  148. 1481. 初始化
  149. 1492.2 扩容操作
  150. 1502.4 toString()
  151. 151六、常用API
  152. 152七、总结
  153. 153第 11 节:ThreadLocal 源码分析
  154. 154二、ThreadLocal 分析
  155. 1551.1.1 线程不安全验证
  156. 1561.1.2 使用 ThreadLocal 优化
  157. 1571.2 链路追踪
  158. 1581.2.2 测试结果
  159. 1592. 数据结构
  160. 1603. 散列算法
  161. 1613.2 验证散列
  162. 1623.2.2 单元测试
  163. 1634. 源码解读
  164. 1644.2 设置元素
  165. 1654.2.2 源码分析
  166. 1664.3 扩容机制
  167. 1674.4 获取元素
  168. 1684.5 元素清理
  169. 1694.5.2 启发式清理[cleanSomeSlots]
  170. 170三、总结
  171. 171第 3 章 码农会锁(5节)
  172. 172二、volatile 讲解
  173. 1732. 加上volatile关键字
  174. 1743. volatile怎么保证的可见性
  175. 1754. 反编译解毒可见性
  176. 1764.2 查看汇编指令
  177. 1775. 不加volatile也可见吗
  178. 178三、总结
  179. 179第 2 节:synchronized
  180. 1801. 对象结构
  181. 1811.2 验证对象结构
  182. 1821.2.2 指针压缩关闭
  183. 1831.2.3 对象头哈希值存储验证
  184. 1841.3 Monitor 对象
  185. 1852. synchronized 特性
  186. 1862.2 可见性
  187. 1872.3 有序性
  188. 1882.4 可重入性
  189. 1893. 锁升级过程
  190. 1903.1 偏向锁
  191. 1913.2 轻量级锁
  192. 192四、傅诗一手
  193. 193第 3 节:ReentrantLock 和 公平锁
  194. 1942. ReentrantLock 知识链条
  195. 1953.2 公平锁、非公平锁,选择
  196. 196三、什么是公平锁
  197. 197四、公平锁实现
  198. 1981.3 代码讲解
  199. 1992. MCSLock
  200. 2002.1 代码讲解
  201. 2013. TicketLock
  202. 2023.3 代码讲解
  203. 203二、ReentrantLock 和 AQS
  204. 2042. 写一个简单的 AQS 同步类
  205. 2052.2 单元测试
  206. 2063. CAS 介绍
  207. 2074.2 lock
  208. 2084.3 compareAndSetState
  209. 2094.4 (AQS)acquire
  210. 2104.6 addWaiter
  211. 2114.7 acquireQueued
  212. 2124.8 parkAndCheckInterrupt
  213. 213第 5 节:AQS 共享锁,Semaphore、CountDownLatch
  214. 2142. Semaphore 共享锁使用
  215. 2153. Semaphore 源码分析
  216. 2163.3 acquire 释放信号量
  217. 2173.5 非公平锁实现
  218. 2183.6 获取信号量失败,加入同步等待队列
  219. 2194. CountDownLatch 共享锁使用
  220. 220三、总结
  221. 221第 4 章 多线程(4节)
  222. 222二、线程启动分析
  223. 223三、线程启动过程
  224. 2242. Java 层面 Thread 启动
  225. 2252.2 start0() 本地方法
  226. 2263. JVM 创建线程
  227. 2273.2 JavaThread
  228. 2283.3 os::create_thread
  229. 2293.4 java_start
  230. 2304. JVM 启动线程
  231. 2314.2 os::start_thread(thread)
  232. 2324.3 pd_start_thread(thread)
  233. 233四、总结
  234. 234第 2 节:Thread,状态转换、方法使用、原理分析
  235. 235三、Thread 状态测试
  236. 2364. WAITING
  237. 2375. TIMED_WAITING
  238. 2386. TERMINATED
  239. 2392. wait & notify
  240. 2403. join
  241. 241五、总结
  242. 242第 3 节:ThreadPoolExecutor
  243. 243二、线程池讲解
  244. 2442.2 实现代码
  245. 2453. 线程池源码分析
  246. 2463.2 高3位与低29位
  247. 2473.2 线程池状态
  248. 2483.3 提交线程(execute)
  249. 2493.5 添加执行任务(addWorker)
  250. 2503.6 执行线程(runWorker)
  251. 2513.7 队列获取任务(getTask)
  252. 252三、总结
  253. 253第 4 节:线程池讲解以及JVMTI监控
  254. 2542. newSingleThreadExecutor
  255. 2553. newCachedThreadPool
  256. 2564. newScheduledThreadPool
  257. 257三、线程池使用场景说明
  258. 258四、获取线程池监控信息
  259. 2592. 基于IVMTI方式监控
  260. 2602.1 先做一个监控例子
  261. 2612.2 扩展线程监控
  262. 262五、总结
  263. 263第 5 章 JVM 虚拟机(5节)
  264. 264三、JDK 目录结构和作用
  265. 265四、JDK 是什么?
  266. 266五、JRE 是什么?
  267. 267六、JVM 是什么?
  268. 2682. JVM 结构和执行器
  269. 269第 2 节:JVM 类加载实践
  270. 270二、类加载过程描述
  271. 271三、写个代码加载下
  272. 2722. 代码讲解
  273. 2732.3 压缩包形式路径(ZipEntry)
  274. 2742.4 混合形式路径(CompositeEntry)
  275. 2752.5 通配符类型路径(WildcardEntry)
  276. 2762.6 类路径解析(Classpath)
  277. 2772.7 加载类测试验证
  278. 278四、解析字节码文件
  279. 2793. 解析版本号信息
  280. 2804. 解析全部内容对照
  281. 281五、总结
  282. 282第 3 节:JVM 内存模型
  283. 283三、内存模型各区域介绍
  284. 2842. Java虚拟机栈
  285. 2853. 本地方法栈
  286. 2865. 常量池
  287. 2872. 重点代码
  288. 288五、jconsole监测元空间溢出
  289. 2892. 调整元空间大小
  290. 2904.2 测试结果
  291. 2914.3 监控截图
  292. 292第 4 节:JVM 故障处理工具
  293. 293二、基础故障处理工具
  294. 2941.2 jps -l,输出当前运行类全称
  295. 2951.4 jps -v,输出虚拟机进程启动时JVM参数[-Xms24m -Xmx256m]
  296. 2962. jcmd 虚拟机诊断命令
  297. 2972.1 jcmd pid VM.flags,查看JVM启动参数
  298. 2982.5 jcmd pid Thread.print,查看线程堆栈信息
  299. 2992.7 jcmd pid GC.heap_dump 路径,导出heap dump文件
  300. 3003. jinfo Java配置信息工具
  301. 3014.01 jstat -class,类加载统计
  302. 3024.04 jstat -gccapacity,堆内存统计
  303. 3034.06 jstat -gcnew,新生代垃圾回收统计
  304. 3044.08 jstat -gcoldcapacity,老年代内存统计
  305. 3054.11 jstat -printcompilation,JVM编译方法统计
  306. 3065.1 jmap,打印共享对象映射
  307. 3075.3 jmap -clstats,打印加载类
  308. 3085.4 jmap -dump,堆转储文件
  309. 3097. jstack Java堆栈跟踪工具
  310. 310三、可视化故障处理工具
  311. 3112. VisualVM,多合故障处理工具
  312. 312四、总结
  313. 313第 5 节:GC 垃圾回收
  314. 314三、JVM 垃圾回收知识框架
  315. 3151. 判断对象已死
  316. 3162. 垃圾回收算法
  317. 3172.2 标记-复制算法(mark-copy)
  318. 3183. 垃圾回收器
  319. 3193.2 老年代
  320. 320结尾