Кратко
Нижний слой TreeMap представляет собой красно-черное дерево.java8 HashMapТакже введено красно-черное дерево, так что же такое красно-черное дерево?Красно-черное дерево — это двоичное дерево поиска, которое добавляет бит хранения к каждому узлу для представления цвета узла, который может быть КРАСНЫМ или ЧЕРНЫМ . Ограничивая цвета узлов на любом простом пути от корня к листу, красно-черное дерево гарантирует, что ни один путь не будет в два раза длиннее других, и, таким образом, будет приблизительно сбалансирован. (из Введение в алгоритмы)
бинарное дерево поиска
Поскольку красно-черное дерево — это бинарное дерево поиска, давайте сначала разберемся в его свойствах:
① Значение всех узлов левого поддерева меньше или равно значению его корневого узла.
② Значение всех узлов в правом поддереве больше или равно значению его корневого узла.
③ Левое и правое поддеревья любого узла также являются бинарными деревьями поиска соответственно.
следующее:
красно-черное дерево
Красно-черное дерево — это бинарное дерево поиска, в котором каждый узел имеет атрибут цвета, красный или черный. Помимо соответствия основным свойствам бинарного поиска, он также обладает следующими свойствами:
①.Узел красный или черный
② Корневой узел черный
③ Каждый листовой узел (узел NIL, пустой узел) черный.
④ Два дочерних узла каждого красного узла черные. (Не может быть двух последовательных красных узлов на всех путях от каждого листа к корню)
⑤ Все пути от любого узла к каждому его листу содержат одинаковое количество черных узлов.
Типичное красно-черное дерево:
Левая рука:
Правое вращение:
TreeMap
Вернемся к treeMap, давайте посмотрим на его диаграмму наследования:
Важные поля TreeMap
// 比较器用于排序，若为null使用自然排序维持key顺序
private final Comparator comparator;
// 根节点
private transient Entry root;
// 节点数
private transient int size = 0;
// 修改次数，fail-fast
private transient int modCount = 0;
//节点颜色
private static final boolean RED = false;
private static final boolean BLACK = true;
/**
* 节点
*/
static final class Entry implements Map.Entry {
K key; //键
V value; //值
Entry left; //左子树
Entry right; //右子树
Entry parent; //父亲
boolean color = BLACK; //颜色
Entry(K key, V value, Entry parent) {...}
public K getKey() {...}
public V getValue() {...}
public V setValue(V value) {...}
public boolean equals(Object o) {...}
public int hashCode() {...}
public String toString() {...}
}
Метод строительства
/**
* 无参构造，自然排序(从小到大)。要求key实现Comparable接口，会调用key重写的compareTo方法进行比较
* 若key没有实现comparable接口，运行时报错(java.lang.ClassCastException)
*/
public TreeMap() {
comparator = null;
}
/**
* 指定比较器，若不为null会调用其compare方法进行比较，无需键实现comparable接口
*/
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
/**
* 将map转为treeMap，比较器为null，注意key
*/
public TreeMap(Map m) {
comparator = null;
putAll(m);
}
/**
* 将map转为treeMap，比较器为SortMap中的comparator
*/
public TreeMap(SortedMap m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
положить метод
public V put(K key, V value) {
// 获取根节点
Entry t = root;
// 若TreeMap为空则直接插入
if (t == null) {
//校验:若比较器为null则key必须实现Comparable接口，若不为null，key可为null
compare(key, key); // type (and possibly null) check
//设为头节点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 记录key排序比较结果
int cmp;
// 记录父节点
Entry parent;
// split comparator and comparable paths
Comparator cpr = comparator;
// 若存在比较器，循环查找位置cmp小于0往左找，大于0往右找，直至等于0进行替换
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
return t.setValue(value);
} while (t != null);
}
// 若不存在比较器，key必须实现Comparable接口
else {
//null无法实现Comparable接口没有compareTo方法故抛异常
if (key == null)
throw new NullPointerException();
//获取比较器，处理方式与上面一致
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//若当前TreeMap中没有此key则新建结点，无论上述哪个分支成立parent一定指向当前某个叶子结点
Entry e = new Entry<>(key, value, parent);
//小于0则为左子树
if (cmp < 0)
parent.left = e;
//大于0则为右子树
else
parent.right = e;
//保证红黑树性质
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
получить метод
Метод get примерно такой же, как и метод put.
public V get(Object key) {
Entry p = getEntry(key);
//找到对应节点返回其值，没有找到返回null
return (p==null ? null : p.value);
}
final Entry getEntry(Object key) {
// Offload comparator-based version for sake of performance
// 若比较器不为null
if (comparator != null)
return getEntryUsingComparator(key);
// 若比较器为null，则key必须实现Comparable接口，null不能抛异常
if (key == null)
throw new NullPointerException();
//用key的compareTo方法，从根节点寻找，若没有找返回null
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
final Entry getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator cpr = comparator;
//处理方式一致
if (cpr != null) {
Entry p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
метод containsValue
Используйте аналогичный метод обхода по порядку (LDR слева, корень справа), чтобы пройти по всему красно-черному дереву, чтобы найти соответствующее значение.
public boolean containsValue(Object value) {
for (Entry e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
/**
* 返回最小节点
*/
final Entry getFirstEntry() {
Entry p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
/**
* 找后继节点
*/
static TreeMap.Entry successor(Entry t) {
if (t == null)
return null;
//若存在右子树，则返回右子树中最小节点
else if (t.right != null) {
Entry p = t.right;
while (p.left != null)
p = p.left;
return p;
//若不存在，从当前节点往上找，若其父节点不为null且它是父节点的右子树则继续找父节点
//直至条件不成立，返回父节点
} else {
Entry p = t.parent;
Entry ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Метод преемника находит узел-преемник узла:
① Если узел пуст, преемника нет.
② Если узел имеет правое поддерево, преемником является крайний левый узел правого поддерева.
③ Если узел не имеет правого поддерева, преемником является первый узел-предок левого поддерева, в котором находится узел.
О первом много говорить не нужно, второе тоже легко, взгляните на следующий узел s графа p:
Если его родительский узел пуст, вернуть null;
Если он имеет родительский узел и является левым поддеревом родительского узла, вернуть его родительский узел;
Если у него есть родительский узел и он является правым поддеревом родительского узла, посмотрите на первый узел-предок левого поддерева, где он расположен (преемником p является s), и просматривайте один за другим, чтобы увидеть p и A как целое по отношению к B. Его правое поддерево, а затем посмотрите, рассматриваются ли P, B, A как целое по отношению к C или его правому поддереву, а затем найдите, что P, B, A, C является его левым относительным поддеревом к S в целом и вернуть общий первый узел-предок - это узел S
метод удаления
public V remove(Object key) {
//获取key所对应的节点
Entry p = getEntry(key);
//若节点为空返回null
if (p == null)
return null;
//若不为null，删除节点返回其值
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry p) {
modCount++;
size--;
//若p左子树和右子树都不为null，将p的key与value替换成后继的，将p指向后继
if (p.left != null && p.right != null) {
Entry s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// replacement为替代节点
Entry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
//若p没有父节点，则根节点设为replacement
if (p.parent == null)
root = replacement;
//若p为左节点，则用replacement替换左节点
else if (p == p.parent.left)
p.parent.left = replacement;
//若p为右节点，则用replacement替换右节点
else
p.parent.right = replacement;
//删除p节点
p.left = p.right = p.parent = null;
// 若p为黑色则需要调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
//若p没有父节点即p为根节点，根节点置空
} else if (p.parent == null) { // return if we are the only node.
root = null;
//p没有子节点
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
//删除p节点
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
Есть три случая:
①. Листовой узел: непосредственно очистить соответствующий дочерний элемент его родительского узла, если левый листовой узел удален, левое поддерево его родительского узла будет пустым, а если правый листовой узел удален, правое поддерево его родительского узла будет пустым нулем
Удалить узел А:
Удалить узел G:
③ Два дочерних элемента: сначала найдите преемника, после его нахождения замените содержимое текущего узла узлом-преемником, а затем удалите узел-преемник, поскольку этот узел-преемник не должен иметь левого дочернего элемента, поэтому ситуация с двумя дочерними элементами преобразуется в первые два условия
Удалить узел Б:
резюме
① Нижний слой TreeMap представляет собой красно-черное дерево, а поток заказов на сбор небезопасен.
②.Если компаратор пуст, ключ не должен быть нулевым.Если компаратор не пуст, ключ может быть нулевым.Это зависит от компаратора карты дерева.
③ Метод .containsValue использует обход по порядку (LDR левый корень правый) для обхода всего TreeMap
В предыдущей статье (java8HashMap) я писал, что связанный список и красно-черное дерево взаимозаменяемы.В этой статье кратко упоминаются соответствующие знания о красно-черном дереве и в основном описываются некоторые методы TreeMap вокруг исходного кода.Следующая Статья в основном посвящена тому, как сохранить свои характеристики после вставки и удаления TreeMap.
Ссылаться на
https://juejin.cn/post/6844903450598178830
http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
https://blog.csdn.net/v_july_v/article/details/6105630