введение
В первой статье серии я упомянул интерфейс Map
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
Рамки
TreeMap
//SortedMap接口包含的比较方法comparator
public interface SortedMap<K,V> extends Map<K,V> {
Comparator<? super K> comparator();
}
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}
//TreeMap构造函数传入比较器Comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public Comparator<? super K> comparator() {
return comparator;
}
//TreeSet构造函数传入比较器Comparator
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public Comparator<? super E> comparator() {
return m.comparator();
}
структура данных
TreeMap
- Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, также известное как симметричное бинарное дерево B. Временная сложность поиска, вставки и удаления красно-черного дерева составляет O(logn), и оно широко используется .
- По сравнению с деревом AVL (сбалансированное бинарное дерево) красно-черное дерево жертвует частичным балансом (красно-черное дерево не является полностью сбалансированным бинарным деревом) в обмен на меньшее количество операций вращения во время операций вставки/удаления и общую производительность вставка/удаление лучше в дереве AVL. Так много структур данных, отсортированных в памяти, хранятся с использованием красно-черных деревьев вместо деревьев AVL.
- По сравнению с B-деревьями и B+-деревьями красно-черное дерево намного глубже, чем B- и B+-деревья в случае одного и того же узла, и оно очень часто читает и записывает ввод-вывод, поэтому подходит для небольшого объем чтения в памяти. , а деревья B- и B+ имеют относительно мало обращений ввода-вывода из-за большого количества элементов в каждом узле и подходят для больших объемов данных, хранящихся на дисках, аналогично структуре хранения записей базы данных. Из-за ограниченного объема этой статьи она будет посвящена бинарным деревьям и красно-черным деревьям и не будет слишком много объяснять деревья AVL, B-деревья и деревья B+.
бинарное отсортированное дерево
Прежде чем анализировать исходный код TreeMap
- Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
- Если правое поддерево любого узла не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла;
- Левое и правое поддеревья любого узла также являются соответственно бинарными деревьями поиска;
- Нет узлов с одинаковыми ключами.
На следующем рисунке показано типичное бинарное дерево:
Обход бинарного дерева
Как древовидная структура, цель обхода бинарного дерева состоит в том, чтобы посетить все узлы в дереве по очереди и сделать так, чтобы каждый узел посещался только один раз. Существует много способов его обхода, обычно есть четыре вида обхода: обход в пре-среднем-пост-порядке и обход по слою. Обход по порядку состоит в том, чтобы сначала посетить левое поддерево, затем корневой узел и, наконец, правый узел.В соответствии с природой двоичного дерева сортировки мы можем знать, что отсортированная последовательность от меньшего к большему (по умолчанию) может быть полученный обходом по порядку. Поэтому обход по порядку используется чаще всего. На следующем рисунке представлена легенда и кодовая реализация обхода по порядку:
public class BinaryTree {
public void traversalBinaryTree(TreeNode tree) {
//如果到了叶子节点则退出当前方法，继续向下寻找
if (tree == null) {
return;
}
//迭代查找左节点，一直到最左边的叶子节点
traversalBinaryTree(tree.left);
System.out.println(tree.value);
//迭代查找右节点，一直到最左边的叶子节点
traversalBinaryTree(tree.right);
}
class TreeNode {
//节点的值
int value;
//左节点
TreeNode left;
//右节点
TreeNode right;
//父节点
TreeNode parent;
public TreeNode(int treeValue, TreeNode parentNode) {
value = treeValue;
parent = parentNode;
left = null;
right = null;
}
}
}
Обход предзаказа и постзаказа:
//前序遍历
System.out.println(tree.value);
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
//后序遍历
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
System.out.println(tree.value);
Добавить бинарное дерево
После понимания обхода двоичного дерева очень просто понять добавление двоичного дерева.Посредством обхода по порядку от малого к большому, чтобы найти пустой листовой узел для добавления значения, давайте реализуем метод для добавления бинарное дерево:
public void addBinaryTreeNode(int value) {
//根节点
TreeNode tree = root;
if (tree == null) {
//根节点为空则新建一个跟节点
root = new TreeNode(value, null);
return;
}
//用来存储新节点的父节点
TreeNode parentNode;
do {
//使用上次循环后的节点做为引用
parentNode = tree;
//如果新插入的 value 小于当前value，则向左边查找
if (value < tree.value) {
tree = tree.left;
//如果新插入的 value 大于当前value，则向右边查找
} else if (value > tree.value) {
tree = tree.right;
//如果相等则证明有相同节点，不添加
} else {
return;
}
} while (tree != null);
//新建节点，parentNode为新节点的父节点
TreeNode node = new TreeNode(value, parentNode);
//新节点为左节点或者右节点
if (value < parentNode.value) {
parentNode.left = node;
} else {
parentNode.right = node;
}
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.addBinaryTreeNode(10);
binaryTree.addBinaryTreeNode(5);
binaryTree.addBinaryTreeNode(20);
binaryTree.addBinaryTreeNode(7);
binaryTree.addBinaryTreeNode(6);
binaryTree.addBinaryTreeNode(3);
binaryTree.addBinaryTreeNode(15);
binaryTree.addBinaryTreeNode(30);
binaryTree.traversalBinaryTree(binaryTree.root);
}
// Console:
// 3
// 5
// 6
// 7
// 10
// 15
// 20
// 30
По логике добавления узлов в бинарное дерево выше, давайте проанализируем реализацию добавления узлов в исходном коде TreeMap
public V put(K key, V value) {
//根节点
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
//根节点为空则新建一个跟节点
root = new Entry<>(key, value, null);
//记录Map元素的数量
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果comparator不为空则代表使用定制的比较器进行排序
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
//如果新插入的key小于当前key，则向左边查找
if (cmp < 0)
t = t.left;
//如果新插入的key大于当前key，则向右边查找
else if (cmp > 0)
t = t.right;
//相等则覆盖
else
return t.setValue(value);
} while (t != null);
}
//如果comparator为空则使用默认比较器进行排序
else {
if (key == null)
throw new NullPointerException();
@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
return t.setValue(value);
} while (t != null);
}
//通过上面查找到插入节点的父节点parent并初始化新节点Entry<K,V>
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新插入的key小于父节点的key，则将插入节点作为父节点的左孩子
if (cmp < 0)
parent.left = e;
//如果新插入的key大于父节点的key，则将插入节点作为父节点的右孩子
else
parent.right = e;
//重点：修复红黑树（后面会说）
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
Удаление бинарного дерева
Удалить бинарное дерево немного сложнее, чем добавить, потому что, если удаляемый узел не является конечным узлом, он должен учитывать этот узел, чтобы заменить позицию текущего узла. Удаление можно разделить на 6 ситуаций:
- Если удаленный узел не имеет левого и правого дочерних узлов и родительского узла, он является корневым узлом и может быть удален напрямую;
- У удаленного узла нет левого или правого дочернего узла, но есть родительский узел, который является конечным узлом и может быть удален напрямую;
- Удаленный узел является корневым узлом, есть левый узел или правый узел, а удаленный корневой узел заменяется левым узлом или правым узлом;
- Удаленный узел не является корневым узлом, только левым узлом, замените удаленный узел левым узлом;
- Удаленный узел не является корневым узлом, только правым узлом, замените удаленный узел правильным узлом;
- У удаленного узла есть левый и правый дочерние узлы, замените значение удаленного узла на непосредственный узел-преемник удаленного узла, затем удалите непосредственный узел-преемник, ситуация преобразуется в 2, 4 или 5.
Реализуем алгоритм удаления бинарного дерева по шести случаям удаления бинарного дерева:
public void removeBinaryTreeNode(int value) {
// 根节点
TreeNode tree = root;
if (tree == null) {
return;
}
TreeNode currentNode = findBinaryTreeNode(value);
if (currentNode == null) {
return;
}
if (currentNode.left == null && currentNode.right == null) {
//情况一 删除根节点，并且没有左右子节点
if (currentNode.parent == null) {
root = null;
} else {
//情况二 删除叶子节点
if (currentNode.parent.left == currentNode) {
currentNode.parent.left = null;
} else {
currentNode.parent.right = null;
}
currentNode.parent = null;
}
} else if (currentNode.left == null || currentNode.right == null) {
TreeNode replaceNode = currentNode.left == null ? currentNode.right : currentNode.left;
replaceNode.parent = currentNode.parent;
//情况三 删除根节点 并且只有一个子节点
if (currentNode.parent == null) {
root = replaceNode;
//情况四 不是根节点 只有左节点
} else if (currentNode == currentNode.parent.left) {
currentNode.parent.left = replaceNode;
//情况五 不是根节点 只有右节点
} else {
currentNode.parent.right = replaceNode;
}
currentNode.parent = currentNode.left = currentNode.right = null;
} else {
//情况六 同时有左右节点
//successorNode 需要删除节点的后继节点
TreeNode successorNode = currentNode.right;
TreeNode parentNode;
//查找后继节点
do {
parentNode = successorNode;
successorNode = successorNode.left;
} while (successorNode != null);
successorNode = parentNode;
//覆盖需要删除的节点的值为后继节点的值
currentNode.value = successorNode.value;
//后继节点的左节点一定为空，如果不为空则说明当前节点不是后继节点
if (successorNode.right != null) {
//关联后继节点的右节点和后继节点的父节点
TreeNode replaceNode = successorNode.right;
replaceNode.parent = successorNode.parent;
if (successorNode.parent.left == successorNode) {
successorNode.parent.left = replaceNode;
}
if (successorNode.parent.right == successorNode) {
successorNode.parent.right = replaceNode;
}
}
//删除后继节点
successorNode.parent = successorNode.left = successorNode.right = null;
}
}
//查找当前值所对应的树节点
public TreeNode findBinaryTreeNode(int value) {
// 根节点
TreeNode tree = root;
if (tree == null) {
return null;
}
// 用来存储新节点的父节点
TreeNode parentNode;
do {
// 循环迭代从小到大查找直到叶子为空
parentNode = tree;
if (value < tree.value) {
tree = tree.left;
} else if (value > tree.value) {
tree = tree.right;
} else {
return parentNode;
}
} while (tree != null);
return null;
}
Используя логику удаления узлов в бинарном дереве выше, давайте проанализируем реализацию удаления узлов в исходном коде TreeMap
public V remove(Object key) {
//查找到key所代表的节点p
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//如果被删除的节点左右孩子都不为空，则查找到P的直接后继节点，用后继节点的键和值覆盖P的键和值，然后删除后继节点即可（实际上是情况六）
//这一步非常巧妙，将要删除的节点转换为要删除节点的直接后继节点，情况六转换为情况二，四，五
if (p.left != null && p.right != null) {
//查找到P的直接后继节点
Entry<K,V> s = successor(p);
//后继节点覆盖键和值到P
p.key = s.key;
p.value = s.value;
//将要删除的节点变为P的后继节点，删除后继节点即可
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
//查找用来替换的节点
//经过上面的步骤，如果P存在左节点，则不存在右节点，直接用左节点替换即可。因为如果左右节点都存在，则会查找到后继（后继节点的左节点一定为空）。
//如果P左节点不存在，存在右节点，则直接用右节点来替换即可。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//通过上面的步骤说明左右节点只可能同时存在一个，replacement为左右子节点当中的任何一个
if (replacement != null) {
// Link replacement to parent
//p节点将要删除，将用来替换的节点的父节点指向p的父节点
replacement.parent = p.parent;
//p的父节点为空，则说明删除的是根节点（情况三）
if (p.parent == null)
root = replacement;
//replacement替换为左节点（情况四）
else if (p == p.parent.left)
p.parent.left = replacement;
//replacement替换为右节点（情况五）
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
//删除P节点
p.left = p.right = p.parent = null;
// Fix replacement
//重点：修复红黑树（后面会说）
if (p.color == BLACK)
fixAfterDeletion(replacement);
//如果替换的节点为空，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);
//删除叶子节点和父节点的关联
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;
}
}
}
//查找t节点的直接后继节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Суммировать
В этой статье мы реализовали логику работы обхода бинарного дерева, добавления узлов и удаления узлов, а затем подробно объяснили логику удаления и добавления узлов в TreeMap