概念
红黑树 (Red-Block Tree) 是一种近似平衡的二叉树, 因此拥有较高的查询效率, 但正因为是一棵近平衡树, 因此在插入或删除节点时, 会结构调整(变色, 左旋, 右旋), 使其接近平衡, 从而降低效率.
本文以 TreeMap 为例说明, TreeMap 用红黑树构建, 所以查询性能较高, 时间复杂度为 O(lgn),, 而 HashMap 和 LinkHashMap 的时间复杂度都为 O(n)(当 hash 不冲突时时间复杂度为 O(1), 但数量多起来后 hash 冲突显示不是我们能控制的, 故写为 O(n)), 显然查询时比 TreeMap 耗时, 关于时间复杂度分析, 可移步到: 时间复杂度分析 理解
** 重点:** 红黑树拥有 3 特征, 6 种行为, 行为的存在使得树在结构调整时, 让树符合三种特征. 这就是红黑树左旋, 右旋, 变色, 原理, 至于怎么设定的, 就是发明者 Rudolf Bayer 的厉害的地方了.
特征:
1. 根节点必须是黑色
2. 红色节点不能连续(即红节点的父子节点都得是黑色)
3. 对于每个节点, 从该节点到树末梢(为 null 的节点), 都有相同数量的黑色节点.
推导结论: 一个节点到末端的最长路径不大于最小路径的 2 倍.
行为 (就是源码(本文 jdk1.8) 的实现方式, 6 种情况): 看下文结构调整.
红黑树样子:
正文:
get():
get(key)通过 key 查找, 内部调 getEntry(key),TreeMap 每一个节点是一个 Entry, 有如下属性, 可以像钩子一样构成一棵树.
- static final class Entry<K, V> implements java.util.Map.Entry<K,V{
- K key;
- V value;
- TreeMap.Entry<K, V> left;
- TreeMap.Entry<K, V> right;
- TreeMap.Entry<K, V> parent;
- boolean color = true;
- }
其中 getEntry()方法做了些操作: 支持两种比较器, 如果在构造中传入比较器 comparator 则使用, 否则使用默认实现的 SortedMap 中的 comparator, 通过 key 值进行比对, 直至找到 entry 返回 entry.value, 否则为 null.
- final TreeMap.Entry<K, V> getEntry(Object var1) {
- if (this.comparator != null) {
- return this.getEntryUsingComparator(var1);
- } else if (var1 == null) {
- throw new NullPointerException();
- } else {
- Comparable var2 = (Comparable)var1;
- TreeMap.Entry var3 = this.root;
- while(var3 != null) {
- int var4 = var2.compareTo(var3.key);
- if (var4 <0) {// 向左
- var3 = var3.left;
- } else {
- if (var4 <= 0) {// 找到了
- return var3;
- }
- var3 = var3.right;// 向右
- }
- }
- return null;
- }
- }
- put()
插入和删除操作是结构变动的原因, 此处以插入说明.
- public V put(K var1, V var2) {
- TreeMap.Entry var3 = this.root;
- if (var3 == null) {
- this.compare(var1, var1);
- this.root = new TreeMap.Entry(var1, var2, (TreeMap.Entry)null);
- this.size = 1;
- ++this.modCount;
- return null;
- } else {
- Comparator var6 = this.comparator;
- int var4;
- TreeMap.Entry var5;
- if (var6 != null) {
- do {
- var5 = var3;
- var4 = var6.compare(var1, var3.key);
- if (var4 < 0) {
- var3 = var3.left;
- } else {
- if (var4 <= 0) {
- return var3.setValue(var2);
- }
- var3 = var3.right;
- }
- } while(var3 != null);
- } else {
- if (var1 == null) {
- throw new NullPointerException();
- }
- Comparable var7 = (Comparable)var1;
- do {
- var5 = var3;
- var4 = var7.compareTo(var3.key);
- if (var4 < 0) {
- var3 = var3.left;
- } else {
- if (var4 <= 0) {
- return var3.setValue(var2);
- }
- var3 = var3.right;
- }
- } while(var3 != null);
- }
- TreeMap.Entry var8 = new TreeMap.Entry(var1, var2, var5);
- if (var4 < 0) {
- var5.left = var8;
- } else {
- var5.right = var8;
- }
- this.fixAfterInsertion(var8);// 结构调整
- ++this.size;
- ++this.modCount;
- return null;
- }
- }
插入分两步, 第一步找位置, 然后插入, 没什么好说的, 第二步是重点: 结构调整. fixAfterInsertion 方法如下:
- private void fixAfterInsertion(TreeMap.Entry<K, V> var1) {
- var1.color = false;
- while(var1 != null && var1 != this.root && !var1.parent.color) {
- TreeMap.Entry var2;
- if (parentOf(var1) == leftOf(parentOf(parentOf(var1)))) {// 插入节点的父节点是爷爷节点的左节点
- var2 = rightOf(parentOf(parentOf(var1))); //xi 小叔节点
- if (!colorOf(var2)) {
- setColor(parentOf(var1), true); // 情况 1
- setColor(var2, true); //: 上色
- setColor(parentOf(parentOf(var1)), false);
- var1 = parentOf(parentOf(var1)); // 获取爷爷节点, 继续 while 中调整
- } else {
- if (var1 == rightOf(parentOf(var1))) { // 情况 2
- var1 = parentOf(var1);// 若 x 小叔节点是黑色或 null, 并且 current 插入的位置是右边, 则左旋转, 父节点变黑....... 以下不再赘述
- this.rotateLeft(var1);
- }
- setColor(parentOf(var1), true); // 情况 3
- setColor(parentOf(parentOf(var1)), false);
- this.rotateRight(parentOf(parentOf(var1)));
- }
- } else {
- var2 = leftOf(parentOf(parentOf(var1)));
- if (!colorOf(var2)) {
- setColor(parentOf(var1), true); // 情况 4
- setColor(var2, true);
- setColor(parentOf(parentOf(var1)), false);
- var1 = parentOf(parentOf(var1));
- } else {
- if (var1 == leftOf(parentOf(var1))) { // 情况 5
- var1 = parentOf(var1);
- this.rotateRight(var1);
- }
- setColor(parentOf(var1), true); // 情况 6
- setColor(parentOf(parentOf(var1)), false);
- this.rotateLeft(parentOf(parentOf(var1)));
- }
- }
- }
- this.root.color = true;
- }
源码很清晰, 调整的 6 种行为, 主要通过三个手段, 变色, 左旋, 右旋, 交互使用, 使得树最终满足三个特征.
** 右旋图解示例:**
** 左旋图解示例:**
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
我不能保证理解都是对的和实践都是最佳的, 这是个人的一些理解和实践, 如发现问题, 请联系笔者做出更改, 交流 ->分享 ->进步.
认真工作, 热爱生活. 享受现在, 拥抱未来~
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
来源: https://www.cnblogs.com/leige109/p/9783181.html