Красно-чёрные деревья

живой пример

import java.util.Comparator;
import java.util.TreeMap;

public class SortedInsert {
    static int compares = 0;

    public static void main(String[] args) {
        Comparator<Integer> counting = (a, b) -> { compares++; return Integer.compare(a, b); };
        TreeMap<Integer, String> tree = new TreeMap<>(counting);
        for (int key = 1; key <= 1000; key++) tree.put(key, "заказ " + key);
        compares = 0;
        tree.get(1000);
        System.out.println("сравнений при поиске последнего из " + tree.size() + " ключей: " + compares);
    }
}

Семнадцать сравнений вместо тысячи: путь до самого дальнего ключа уложился примерно в два логарифма. Обычное дерево поиска на таком входе выродилось бы в список и прошло бы все 1000 узлов.

Дерева в стандартной библиотеке Go нет, поэтому считаем на его ближайшем аналоге: отсортированном срезе с двоичным поиском. Сбалансированное дерево тратит на тот же поиск примерно вдвое больше сравнений, но это всё равно логарифм.

живой пример

package main

import (
	"cmp"
	"fmt"
	"slices"
)

var compares = 0

func counting(a, b int) int {
	compares++
	return cmp.Compare(a, b)
}

func main() {
	keys := make([]int, 0, 1000)
	for key := 1; key <= 1000; key++ {
		keys = append(keys, key)
	}
	compares = 0
	slices.BinarySearchFunc(keys, 1000, counting)
	fmt.Println("сравнений при поиске последнего из", len(keys), "ключей:", compares)
}

Одиннадцать сравнений вместо тысячи: двоичный поиск делает логарифм шагов и одну проверку на равенство, красно-чёрное дерево на том же входе уложилось бы примерно в семнадцать, два логарифма. Обычное дерево поиска на таком входе выродилось бы в список и прошло бы все 1000 узлов.

Дерева в стандартной библиотеке JavaScript нет, поэтому считаем на его ближайшем аналоге: отсортированном массиве с двоичным поиском. Сбалансированное дерево тратит на тот же поиск примерно вдвое больше сравнений, но это всё равно логарифм.

живой пример

let compares = 0;

function lowerBound(a, key) {
  let lo = 0;
  let hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    compares++;
    if (a[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const keys = Array.from({ length: 1000 }, (_, i) => i + 1);
compares = 0;
lowerBound(keys, 1000);
console.log(`сравнений при поиске последнего из ${keys.length} ключей: ${compares}`);

Десять сравнений вместо тысячи: двоичный поиск делает ровно логарифм шагов, красно-чёрное дерево на том же входе уложилось бы примерно в семнадцать, два логарифма. Обычное дерево поиска на таком входе выродилось бы в список и прошло бы все 1000 узлов.

Дерева в стандартной библиотеке Python нет, поэтому считаем на его ближайшем аналоге: отсортированном списке с bisect. Сбалансированное дерево тратит на тот же поиск примерно вдвое больше сравнений, но это всё равно логарифм.

живой пример

from bisect import bisect_left

compares = 0


class Key(int):
    def __lt__(self, other) -> bool:
        global compares
        compares += 1
        return int(self) < int(other)


keys = [Key(k) for k in range(1, 1001)]
compares = 0
bisect_left(keys, Key(1000))
print(f"сравнений при поиске последнего из {len(keys)} ключей: {compares}")

Десять сравнений вместо тысячи: двоичный поиск делает ровно логарифм шагов, красно-чёрное дерево на том же входе уложилось бы примерно в семнадцать, два логарифма. Обычное дерево поиска на таком входе выродилось бы в список и прошло бы все 1000 узлов.

На красно-чёрном дереве построены упорядоченные словари и множества стандартных библиотек, и писать его самому не нужно даже для тренировки: в поворотах и перекрасках десяток симметричных случаев, а ошибка не видна, дерево продолжает отвечать правильно и лишь перестаёт быть сбалансированным. Знать устройство нужно, чтобы понимать, за что вы доплачиваете, беря упорядоченную коллекцию вместо хеш-таблицы.

Если реализацию всё-таки пишут, «ошибка не видна» лечится проверкой инвариантов в тестах: обойти дерево и убедиться, что корень чёрный, красные не идут подряд, а число чёрных узлов на всех путях до листьев одинаково; заодно проверить порядок ключей симметричным обходом. Такая проверка пишется в двадцать строк, гоняется после каждой вставки и удаления на случайных ключах и ловит сломанный поворот на первой же тысяче операций, тогда как поиск будет работать правильно ещё долго. Так тестируют и JDK: у TreeMap есть свои проверки инвариантов, и ровно так проверяют любую структуру с внутренними правилами.

Красно-чёрное дерево не единственный способ держать порядок. AVL-дерево балансирует строже (высоты поддеревьев отличаются не больше чем на единицу), поэтому ниже и чуть быстрее на поиске, но платит поворотами почти на каждой записи; его берут там, где читают много, а пишут редко. Список с пропусками (skip list) вообще не дерево: это несколько уровней связанных списков, где верхние пропускают большую часть элементов, и монета решает, на сколько уровней поднять новый элемент; тот же O(log N) в среднем, зато без поворотов, и потому он хорошо живёт в многопоточной среде, на нём построен ConcurrentSkipListMap, упорядоченная замена ConcurrentHashMap. И B-дерево из следующей статьи, тот же баланс для диска.

Эталонная реализация — TreeMap (и TreeSet, который внутри тот же TreeMap: ключи настоящие, а на месте значений у всех записей лежит одна общая заглушка). Это буквально то дерево, что разобрано выше: у каждого узла, кроме ключа, значения и трёх ссылок (левый, правый, родитель), есть поле цвета — один булев флаг. Вставка идёт как в обычном дереве поиска, а потом поднимается к корню, починяя нарушения теми же перекрасками и левыми-правыми поворотами. Наружу цвет не виден: ни настроек, ни методов у балансировки нет — она просто есть.

Сложность отсюда честная, без оговорки «в среднем»: get, put, remove — гарантированные O(log n) при любом порядке вставки. Интереснее цена самой балансировки. Перекрасок при вставке может быть до O(log n) — они поднимаются к корню, — а вот поворотов не больше двух, при удалении — не больше трёх. Поворот дороже перекраски: он переставляет ссылки и трогает сразу несколько узлов. То, что поворотов всегда единицы, и есть причина, по которой в библиотеках прижилось именно красно-чёрное дерево, а не более строго сбалансированное (например, AVL): то было бы чуть ниже и чуть быстрее на поиске, но платило бы поворотами на каждой записи.

За упорядоченность вы платите памятью и константой. Каждая запись TreeMap — отдельный объект с шестью полями, разбросанный по куче, и путь к нему — это несколько прыжков по ссылкам. На точечном доступе по ключу хеш-таблица заметно быстрее. Поэтому TreeMap берут не «на всякий случай», а когда порядок или диапазонные запросы действительно нужны.

Грабля. Загружать в дерево уже отсортированные данные поштучно — самый дорогой способ его построить: каждая вставка сначала ищет место, потом запускает балансировку. Если источник уже упорядочен, дерево можно собрать сразу готовым:

SortedMap<Long, Order> source = ...;
Map<Long, Order> copy = new TreeMap<>(source);

Конструктор от SortedMap обходит источник по порядку и раскладывает узлы сразу правильно, не сравнивая ключи вообще: линейный проход вместо n вставок с перестройками. putAll умеет тот же трюк, но только при трёх условиях разом: приёмник пуст, источник — тоже SortedMap, и порядок сравнения у них один и тот же. Не совпало хоть что-то — и это обычные поштучные вставки со всей балансировкой. Поштучно те же 1000 ключей обходятся примерно в 14 500 сравнений, копия целиком — в ноль. На сотне записей разница незаметна, на миллионе — вполне.

На красно-чёрном дереве или его родне построены упорядоченные словари большинства языков, но в стандартной библиотеке Go его нет: там только map без порядка и срез. Писать дерево самому не нужно даже для тренировки: в поворотах и перекрасках десяток симметричных случаев, а ошибка не видна, дерево продолжает отвечать правильно и лишь перестаёт быть сбалансированным. Знать устройство нужно, чтобы понимать, за что вы доплачиваете, беря упорядоченную структуру вместо map.

Если реализацию всё-таки пишут, «ошибка не видна» лечится проверкой инвариантов в тестах: обойти дерево и убедиться, что корень чёрный, красные не идут подряд, а число чёрных узлов на всех путях до листьев одинаково; заодно проверить порядок ключей симметричным обходом. Такая проверка пишется в двадцать строк, гоняется после каждой вставки и удаления на случайных ключах, лучше всего через testing/quick или фаззинг go test -fuzz, и ловит сломанный поворот на первой же тысяче операций, тогда как поиск будет работать правильно ещё долго. Ровно так проверяют любую структуру с внутренними правилами.

Красно-чёрное дерево не единственный способ держать порядок. AVL-дерево балансирует строже (высоты поддеревьев отличаются не больше чем на единицу), поэтому ниже и чуть быстрее на поиске, но платит поворотами почти на каждой записи; его берут там, где читают много, а пишут редко. Список с пропусками (skip list) вообще не дерево: это несколько уровней связанных списков, где верхние пропускают большую часть элементов, и монета решает, на сколько уровней поднять новый элемент; тот же O(log N) в среднем, зато без поворотов, и потому он хорошо живёт в многопоточной среде: на нём построена таблица в памяти у LevelDB и Pebble, хранилища под CockroachDB. И B-дерево из следующей статьи, тот же баланс для диска и для кеша процессора.

Готовые реализации живут в пакетах. Самый ходовой — github.com/google/btree, и это не красно-чёрное дерево, а B-дерево в памяти: в узле по умолчанию до 63 ключей подряд, узлов мало, и обход дружит с кешем; на нём держат индексы etcd и Kubernetes. Красно-чёрное и AVL есть в github.com/emirpasic/gods, а в golang.org/x/exp долго жил экспериментальный treap. Все дают гарантированные O(log n) при любом порядке вставки, и балансировка наружу не видна: ни настроек, ни методов у неё нет — она просто есть.

Интереснее цена самой балансировки. У красно-чёрного дерева перекрасок при вставке может быть до O(log n) — они поднимаются к корню, — а вот поворотов не больше двух, при удалении — не больше трёх. Поворот дороже перекраски: он переставляет указатели и трогает сразу несколько узлов. У B-дерева перестроек ещё меньше: узел на десятки ключей разбивается редко, а внутри узла элементы просто сдвигаются copy. Это и есть причина, по которой в Go прижилось именно B-дерево: меньше объектов, меньше указателей и меньше работы сборщику мусора.

За упорядоченность вы платите памятью и константой. Каждый узел красно-чёрного дерева — отдельный объект с ключом, значением, тремя указателями и цветом, разбросанный по куче, и путь к нему — несколько прыжков по указателям; миллион записей это миллион объектов, которые сборщик мусора обходит на каждом цикле. На точечном доступе по ключу map заметно быстрее. Поэтому дерево берут не «на всякий случай», а когда порядок или диапазонные запросы действительно нужны.

Грабля. Собирать упорядоченную структуру из уже отсортированных данных поштучно — самый дорогой способ её построить. Для отсортированного среза это slices.Insert в цикле, O(N²) на сдвигах; для дерева каждая вставка сначала ищет место, потом запускает балансировку. Если источник уже упорядочен или его можно отсортировать разом, так и делают:

keys := slices.Collect(maps.Keys(source)) // Go 1.23; раньше — цикл с append
slices.Sort(keys)                          // один проход O(n·log n) вместо n вставок со сдвигами

Отсортированный срез готов к slices.BinarySearch сразу; а если после этого нужны частые вставки вперемешку с поиском, срез один раз переливают в B-дерево пакета в порядке возрастания: вставка следующего по порядку ключа в B-дерево дешёвая, разбиение узла случается раз в десятки вставок. Поштучно те же 1000 ключей в срез стоят полмиллиона сдвинутых элементов, сортировка целиком — около десяти тысяч сравнений. На сотне записей разница незаметна, на миллионе — вполне.

На красно-чёрном дереве или его родне построены упорядоченные словари большинства языков, но в стандартной библиотеке JavaScript его нет: Map и Set помнят порядок вставки, а не порядок ключей. Писать дерево самому не нужно даже для тренировки: в поворотах и перекрасках десяток симметричных случаев, а ошибка не видна, дерево продолжает отвечать правильно и лишь перестаёт быть сбалансированным. Знать устройство нужно, чтобы понимать, за что вы доплачиваете, беря упорядоченную структуру вместо Map.

Если реализацию всё-таки пишут, «ошибка не видна» лечится проверкой инвариантов в тестах: обойти дерево и убедиться, что корень чёрный, красные не идут подряд, а число чёрных узлов на всех путях до листьев одинаково; заодно проверить порядок ключей симметричным обходом. Такая проверка пишется в двадцать строк, гоняется после каждой вставки и удаления на случайных ключах, удобнее всего через fast-check, и ловит сломанный поворот на первой же тысяче операций, тогда как поиск будет работать правильно ещё долго. Ровно так проверяют любую структуру с внутренними правилами.

Красно-чёрное дерево не единственный способ держать порядок. AVL-дерево балансирует строже (высоты поддеревьев отличаются не больше чем на единицу), поэтому ниже и чуть быстрее на поиске, но платит поворотами почти на каждой записи; его берут там, где читают много, а пишут редко. Список с пропусками (skip list) вообще не дерево: это несколько уровней связанных списков, где верхние пропускают большую часть элементов, и монета решает, на сколько уровней поднять новый элемент; тот же O(log N) в среднем, зато без поворотов, и потому он хорошо живёт в многопоточной среде: на нём построены упорядоченные множества Redis, которыми бэкенд на Node пользуется каждый день. И B-дерево из следующей статьи, тот же баланс для диска и для кеша процессора.

Готовые реализации живут в пакетах: sorted-btree даёт B-дерево в памяти с диапазонными запросами, functional-red-black-tree — классическое красно-чёрное, неизменяемое, где каждая вставка возвращает новую версию дерева, деля неизменённые узлы со старой. Оба дают гарантированные O(log n) при любом порядке вставки, и балансировка наружу не видна: ни настроек, ни методов у неё нет — она просто есть. Внутри самого V8 деревья тоже работают, но для своих нужд: так хранятся диапазоны в регулярных выражениях и промежутки жизни регистров в компиляторе.

Интереснее цена самой балансировки. Перекрасок при вставке может быть до O(log n) — они поднимаются к корню, — а вот поворотов не больше двух, при удалении — не больше трёх. Поворот дороже перекраски: он переставляет ссылки и трогает сразу несколько узлов. То, что поворотов всегда единицы, и есть причина, по которой в библиотеках прижилось именно красно-чёрное дерево, а не более строго сбалансированное AVL: то было бы чуть ниже и чуть быстрее на поиске, но платило бы поворотами на каждой записи.

За упорядоченность вы платите памятью и константой. Каждый узел — отдельный объект движка с заголовком и полями, разбросанный по куче, и путь к нему — несколько прыжков по ссылкам; миллион записей это миллион объектов для сборщика мусора. На точечном доступе по ключу Map заметно быстрее. Поэтому дерево берут не «на всякий случай», а когда порядок или диапазонные запросы действительно нужны.

Грабля. Собирать упорядоченную структуру из уже отсортированных данных поштучно — самый дорогой способ её построить. Для отсортированного массива это splice в цикле, O(N²) на сдвигах; для дерева каждая вставка сначала ищет место, потом запускает балансировку. Если источник уже упорядочен или его можно отсортировать разом, так и делают:

const keys = [...source.keys()].sort((a, b) => a - b); // один проход вместо n вставок со сдвигами

Отсортированный массив готов к двоичному поиску сразу; если после этого нужны частые вставки вперемешку с поиском, его переливают в дерево пакета в порядке возрастания. Поштучно те же 1000 ключей через splice стоят полмиллиона сдвинутых элементов, сортировка целиком — около десяти тысяч сравнений. На сотне записей разница незаметна, на миллионе — вполне.

На красно-чёрном дереве или его родне построены упорядоченные словари большинства языков, но в стандартной библиотеке Python его нет: dict помнит порядок вставки, а не порядок ключей. Писать дерево самому не нужно даже для тренировки: в поворотах и перекрасках десяток симметричных случаев, а ошибка не видна, дерево продолжает отвечать правильно и лишь перестаёт быть сбалансированным. Знать устройство нужно, чтобы понимать, за что вы доплачиваете, беря упорядоченную структуру вместо dict.

Если реализацию всё-таки пишут, «ошибка не видна» лечится проверкой инвариантов в тестах: обойти дерево и убедиться, что корень чёрный, красные не идут подряд, а число чёрных узлов на всех путях до листьев одинаково; заодно проверить порядок ключей симметричным обходом. Такая проверка пишется в двадцать строк, гоняется после каждой вставки и удаления на случайных ключах, удобнее всего через hypothesis, и ловит сломанный поворот на первой же тысяче операций, тогда как поиск будет работать правильно ещё долго. Ровно так проверяют любую структуру с внутренними правилами.

Красно-чёрное дерево не единственный способ держать порядок. AVL-дерево балансирует строже (высоты поддеревьев отличаются не больше чем на единицу), поэтому ниже и чуть быстрее на поиске, но платит поворотами почти на каждой записи; его берут там, где читают много, а пишут редко. Список с пропусками (skip list) вообще не дерево: это несколько уровней связанных списков, где верхние пропускают большую часть элементов, и монета решает, на сколько уровней поднять новый элемент; тот же O(log N) в среднем, зато без поворотов, и потому он хорошо живёт в многопоточной среде: на нём построены упорядоченные множества Redis. И B-дерево из следующей статьи, тот же баланс для диска; в Python оно ближе, чем кажется: индексы sqlite3 из стандартной библиотеки это B-деревья.

Готовая реализация упорядоченной коллекции в мире Python одна на всех — пакет sortedcontainers с SortedList, SortedDict и SortedSet. Внутри у него не дерево, а список отсортированных списков по тысяче элементов с индексом над ними: на чистом Python такая конструкция обгоняет любое дерево, потому что сдвиг внутри короткого списка делает быстрая memmove, а объектов-узлов нет вовсе. Сложность близка к O(log n) при любом порядке вставки, а балансировка, здесь это разбиение переполненного подсписка, наружу не видна: ни настроек, ни методов у неё нет — она просто есть.

Интереснее цена самой балансировки в классическом дереве. Перекрасок при вставке может быть до O(log n) — они поднимаются к корню, — а вот поворотов не больше двух, при удалении — не больше трёх. Поворот дороже перекраски: он переставляет ссылки и трогает сразу несколько узлов. То, что поворотов всегда единицы, и есть причина, по которой в библиотеках других языков прижилось именно красно-чёрное дерево, а не более строго сбалансированное AVL; в Python же выиграл sortedcontainers именно потому, что обошёлся без узлов и поворотов вообще.

За упорядоченность вы платите памятью и константой. Каждый узел самодельного дерева — отдельный объект Python с полями и ссылками, разбросанный по куче, и путь к нему — несколько прыжков через интерпретатор; миллион записей это миллион объектов для сборщика мусора. На точечном доступе по ключу dict заметно быстрее. Поэтому упорядоченную структуру берут не «на всякий случай», а когда порядок или диапазонные запросы действительно нужны.

Грабля. Собирать упорядоченную структуру из уже отсортированных данных поштучно — самый дорогой способ её построить. Для отсортированного списка это insort в цикле, O(N²) на сдвигах; для дерева каждая вставка сначала ищет место, потом запускает балансировку. Если источник уже упорядочен или его можно отсортировать разом, так и делают:

keys = sorted(source)          # один проход O(n·log n) вместо n вставок со сдвигами
ordered = SortedList(source)   # конструктор sortedcontainers делает то же самое внутри

Отсортированный список готов к bisect сразу, а конструктор SortedList сортирует источник один раз и режет его на подсписки, не сравнивая ключи поштучно. Поштучно те же 1000 ключей через insort стоят полмиллиона сдвинутых элементов, сортировка целиком — около десяти тысяч сравнений. На сотне записей разница незаметна, на миллионе — вполне.

• Готовое дерево — TreeMap и TreeSet: узел с цветом, поворотов при вставке не больше двух; упорядоченная замена ConcurrentHashMap — ConcurrentSkipListMap; отсортированный источник копируют конструктором от SortedMap, а не put в цикле.

• В стандартной библиотеке дерева нет: отсортированный срез со slices.BinarySearch, под нагрузку google/btree (B-дерево в памяти, меньше объектов для сборщика мусора); отсортированный источник собирают одним slices.Sort, а не slices.Insert в цикле.

• В языке дерева нет: отсортированный массив с двоичным поиском, под нагрузку sorted-btree или functional-red-black-tree; отсортированный источник собирают одним sort, а не splice в цикле.

• В стандартной библиотеке дерева нет: bisect над отсортированным list, под нагрузку sortedcontainers (список списков без узлов и поворотов); отсортированный источник собирают одним sorted или конструктором SortedList, а не insort в цикле.