当前位置：首页 > news >正文

146.DS补充--红黑树的理解学习

news 2026/6/16 16:18:16

红黑树

废话少讲主要理解的就是：

红黑树的概念原理
结合例子来手绘理解
结合Java代码来理解

注：知识结合AI和java源代码来理解学习主要涉及插入的操作删除过于复杂了

一.红黑树的概念原理

本质其实还是一棵AVL树但是不需要达到完全平衡性
频繁插入删除老是调整代价大引入红黑树
先看它的规则：

结点只有红色(R)/黑色(B)
根结点必须为黑色(为了防止根乱变)
空NULL节点视为黑色
新插入的结点初始为红色
红节点不能连续(红红不能出现)
从任意节点到叶子节点的黑节点数量必须相同(为了平衡)

看到前面红红连续出现了就是红黑树要解决的问题
很简单就两个方式：变色/旋转
屏幕截图 2026-05-18 162425
关于旋转等同于AVL平衡二叉树的那四种情况：

概念原理就这些我们需要通过一个过程来手绘真正理解它

二.结合例子来手绘理解

比如插入10 5 1 7 15 20
我们一步一步结合原理概念来理解过程

1.插入10初始为红色但是根结点必须为黑色

2.插入5初始为红色然后<10左边现在没啥问题

3.插入1初始为红色通过BST概念排到5左边出现连续红红的情况了

叔叔是null空结点黑的所以旋转
按照AVL LL右旋

4.插入7初始化红色 BST排到10左边再次出现连续红红情况

叔叔是红色需要进行变色根据规则：叔父黑爷红

爷5是根结点必须为黑

5.插入15初始化为红色 BST排到10右边没啥问题

6.插入20初始化为红色 BST排到15右边连续红红情况

叔叔红色进行变色：叔父黑爷红

再往上检查没问题结束

插入的操作：依旧本质AVL平衡二叉树+BST排序二叉树

三.结合Java中的TreeMap理解

截取源码先看put插入

 private V put(K key, V value, boolean replaceOld) {Entry<K,V> t = root;if (t == null) {addEntryToEmptyMap(key, value);return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;else {V oldValue = t.value;if (replaceOld || oldValue == null) {t.value = value;}return oldValue;}} while (t != null);} else {Objects.requireNonNull(key);@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;else {V oldValue = t.value;if (replaceOld || oldValue == null) {t.value = value;}return oldValue;}} while (t != null);}addEntry(key, value, parent, cmp < 0);return null;}

这个没啥好说的就是BST实现过程

重点核心就是修复出现红红连续的情况如何处理fixAfterInsertion()

private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;}

我们重点解读这段代码

首先是插入初始为红色