红黑二叉树
红黑二叉树(简称：红黑树)，它首先是一棵二叉树，同时也是一棵自平衡的排序二叉树。
红黑树在原有的排序二叉树增加了如下几个要求：
1. 每个节点要么是红色，要么是黑色。
2. 根节点永远是黑色的。
3. 所有的叶节点都是空节点(即 null)，并且是黑色的。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
这些约束强化了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。
红黑树是一个更高效的检索二叉树，JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。
红黑树的基本操作：插入、删除、左旋、右旋、着色。 每插入或者删除一个节点，可能会导致树不在符合红黑树的特征，需要进行修复，进行 “左旋、右旋、着色”操作，使树继续保持红黑树的特性。
红黑二叉树 红黑二叉树(简称：红黑树)，它首先是一棵二叉树，同时也是一棵自平衡的排序二叉树。 红黑树在...
啥是红黑树，红黑树 = 二叉树
红黑树原理 学习红黑树之前，你首先要有查询二叉树的知识储备，和平衡二叉树（AVL）的知识储备。 红黑树是基于AVL...
红黑树 BBST：自平衡的二叉树（1）根结点为黑，外部节点为黑。（2）其余节点，若为红，则只能有黑孩子。（3）外部...
红黑树是在二叉树的基础上加了红、黑两种颜色。 树： 有序树无序树 二叉树：所有结点的度都小于等于2前序遍历，中序遍...
1、什么是红黑树？ 红黑树是一个要求不那么严格的平衡二叉树搜索树（平衡二叉搜索树/AVL树=平衡二叉树+二叉搜索树...
红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树 红黑树是一种特化的AVL树（平衡二叉树[h...
JDK1.8引入了红黑树(HashMap,CurrentHashMap) 红黑树是一个平衡的二叉树，但不是一个完美...
TreeMap是在java.util包下面，也是有序的map集合，它的原理是“红黑树”实现的： 使用了红黑二叉树的...
红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。 对于一棵有效的红黑树二叉...
本文标题：红黑二叉树
本文链接：https://www.haomeiwen.com/subject/ybnfchtx.html
网友评论