1 Star 0 Fork 4K

刘谱 / JavaGuide

forked from SnailClimb / JavaGuide 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
red-black-tree.md 1015 Bytes
一键复制 编辑 原始数据 按行查看 历史
SnailClimb 提交于 2022-03-03 09:14 . ✨[docs feat]vuepress主题更新
category tag
计算机基础
数据结构

红黑树

红黑树特点 :

  1. 每个节点非红即黑;
  2. 根节点总是黑色的;
  3. 每个叶子节点都是黑色的空节点(NIL节点);
  4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
  5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。

红黑树的应用 :TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。

为什么要用红黑树? 简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 漫画:什么是红黑树?(也介绍到了二叉查找树,非常推荐)

相关阅读《红黑树深入剖析及Java实现》(美团点评技术团队)

Java
1
https://gitee.com/6582886lp/JavaGuide.git
git@gitee.com:6582886lp/JavaGuide.git
6582886lp
JavaGuide
JavaGuide
main

搜索帮助