← назад к разделу

У нас накопился неприятный компромисс. Упорядоченный массив быстро ищет (двоичный поиск, O(log N)), но медленно вставляет. Связанный список быстро вставляет, но медленно ищет. А хочется и то и другое сразу. Двоичное дерево поиска даёт именно это: быстрый поиск, вставку и удаление — все за O(log N), если дерево сбалансировано.

Термины

Дерево — это узлы, соединённые рёбрами, и говорят о нём словами семьи и растения. Вход в дерево один, верхний узел, это корень (root). От него связи идут вниз: узел выше родитель, узлы под ним потомки, узел без потомков лист (leaf), край дерева. Узел вместе со всем, что под ним, поддерево, и с ним работает почти каждый алгоритм: задачу для дерева решают как задачу для его поддеревьев. Глубину узла считают уровнем: у корня 0, у его детей 1 и так далее.

«Двоичное» означает, что у каждого узла не больше двух потомков — левый и правый.

Правило дерева поиска

Дерево становится деревом поиска благодаря одному правилу: у любого узла все ключи в левом поддереве меньше его собственного, а в правом — больше. Это правило соблюдается на каждом узле, а не только у корня.

Именно оно делает поиск быстрым. Ищем ключ: сравниваем с корнем; меньше — идём влево, больше — вправо, и так спускаемся, отсекая на каждом шаге половину дерева. Это тот же двоичный поиск, но по структуре из узлов, а не по массиву.

12 37 88 25 50 75 62 ищем 62: 62 > 50 → вправо, 62 < 75 → влево

На каждом узле одно сравнение отсекает половину дерева. Три шага до цели — O(log N) на сбалансированном дереве.

Вставка и обход

Вставка идёт по тому же спуску: находим, где ключа не хватает (пустое место слева или справа внизу), и подвешиваем туда новый узел. Тоже O(log N) в сбалансированном дереве.

Обход (traversal) — способ посетить все узлы. Самый полезный — симметричный (in-order): сначала левое поддерево, потом сам узел, потом правое. Магия в том, что симметричный обход дерева поиска выдаёт ключи строго по возрастанию — дерево «само отсортировано».

Обходов на самом деле три, и различаются они только тем, когда посещают сам узел относительно поддеревьев. Прямой (pre-order): узел, потом левое, потом правое; так копируют дерево и сериализуют его в строку, и это ровно тот порядок, в котором обход графа в глубину посещает вершины, о чём статья про графы. Обратный (post-order): сначала оба поддерева, узел последним; так удаляют дерево (потомки раньше родителя) и вычисляют выражение по дереву операций, где значение узла известно только после значений детей. Симметричный, как сказано, даёт сортировку. Код у всех трёх одинаковый до порядка трёх строк: рекурсивный вызов влево, обработка узла, рекурсивный вызов вправо.

Удаление — самая хитрая операция

Удаление разбивается на три случая по числу потомков у удаляемого узла:

  1. нет потомков (лист) — просто отцепляем узел от родителя;
  2. один потомок — «перекидываем» ребёнка на место удаляемого, как в связанном списке;
  3. два потомка — сложный случай: узел просто так не выдернуть. Находят преемника — наименьший ключ в правом поддереве (следующий по величине элемент) — и ставят его на место удаляемого. Правило дерева при этом сохраняется.

В коде три случая сворачиваются в один рекурсивный спуск: ищем ключ, а найдя, либо возвращаем единственного потомка (это закрывает и лист, у которого оба потомка пусты), либо переписываем в узел ключ преемника и удаляем преемника из правого поддерева, где у него точно нет левого потомка.

static Node delete(Node node, int key) {
    if (node == null) return null;
    if (key < node.key) node.left = delete(node.left, key);
    else if (key > node.key) node.right = delete(node.right, key);
    else {
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        Node successor = node.right;
        while (successor.left != null) successor = successor.left;
        node.key = successor.key;
        node.right = delete(node.right, successor.key);
    }
    return node;
}

func remove(node *Node, key int) *Node {
	if node == nil {
		return nil
	}
	switch {
	case key < node.key:
		node.left = remove(node.left, key)
	case key > node.key:
		node.right = remove(node.right, key)
	default:
		if node.left == nil {
			return node.right
		}
		if node.right == nil {
			return node.left
		}
		successor := node.right
		for successor.left != nil {
			successor = successor.left
		}
		node.key = successor.key
		node.right = remove(node.right, successor.key)
	}
	return node
}

function remove(node, key) {
  if (node === null) return null;
  if (key < node.key) node.left = remove(node.left, key);
  else if (key > node.key) node.right = remove(node.right, key);
  else {
    if (node.left === null) return node.right;
    if (node.right === null) return node.left;
    let successor = node.right;
    while (successor.left !== null) successor = successor.left;
    node.key = successor.key;
    node.right = remove(node.right, successor.key);
  }
  return node;
}

def remove(node, key: int):
    if node is None:
        return None
    if key < node.key:
        node.left = remove(node.left, key)
    elif key > node.key:
        node.right = remove(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.key = successor.key
        node.right = remove(node.right, successor.key)
    return node

Возврат node из каждого вызова и присваивание node.left = delete(...) это способ «перецепить» поддерево без отдельной ссылки на родителя: узел, который надо убрать, просто не возвращается наверх. Второй вызов delete для преемника всегда упирается в первый или второй случай, потому что у наименьшего узла правого поддерева левого потомка нет по определению.

Проблема вырождения

У дерева поиска есть ахиллесова пята. Если вставлять ключи в уже отсортированном порядке (1, 2, 3, 4…), каждый новый узел цепляется справа от предыдущего, и дерево вытягивается в одну длинную ветку — фактически в связанный список. Поиск в нём деградирует до O(N).

вперемешку 50 25 и 75 12 37 62 88 по порядку 12 25 37 и так до 88

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

живой пример

public class BstDemo {
    static class Node { int key; Node left, right; Node(int key) { this.key = key; } }

    static Node insert(Node node, int key) {
        if (node == null) return new Node(key);
        if (key < node.key) node.left = insert(node.left, key);
        else node.right = insert(node.right, key);
        return node;
    }

    static Node build(int... keys) {
        Node root = null;
        for (int key : keys) root = insert(root, key);
        return root;
    }

    static int depth(Node node) {
        return node == null ? 0 : 1 + Math.max(depth(node.left), depth(node.right));
    }

    static int steps(Node node, int key) {
        int count = 1;
        while (node.key != key) { node = key < node.key ? node.left : node.right; count++; }
        return count;
    }

    public static void main(String[] args) {
        Node mixed = build(50, 25, 75, 12, 37, 62, 88);
        Node sorted = build(12, 25, 37, 50, 62, 75, 88);
        System.out.println("вперемешку: глубина " + depth(mixed) + ", шагов до 88 — " + steps(mixed, 88));
        System.out.println("по порядку: глубина " + depth(sorted) + ", шагов до 88 — " + steps(sorted, 88));
    }
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import "fmt"

type Node struct {
	key         int
	left, right *Node
}

func insert(node *Node, key int) *Node {
	if node == nil {
		return &Node{key: key}
	}
	if key < node.key {
		node.left = insert(node.left, key)
	} else {
		node.right = insert(node.right, key)
	}
	return node
}

func build(keys ...int) *Node {
	var root *Node
	for _, key := range keys {
		root = insert(root, key)
	}
	return root
}

func depth(node *Node) int {
	if node == nil {
		return 0
	}
	return 1 + max(depth(node.left), depth(node.right))
}

func steps(node *Node, key int) int {
	count := 1
	for node.key != key {
		if key < node.key {
			node = node.left
		} else {
			node = node.right
		}
		count++
	}
	return count
}

func main() {
	mixed := build(50, 25, 75, 12, 37, 62, 88)
	ordered := build(12, 25, 37, 50, 62, 75, 88)
	fmt.Printf("вперемешку: глубина %d, шагов до 88 — %d\n", depth(mixed), steps(mixed, 88))
	fmt.Printf("по порядку: глубина %d, шагов до 88 — %d\n", depth(ordered), steps(ordered, 88))
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

function insert(node, key) {
  if (node === null) return new Node(key);
  if (key < node.key) node.left = insert(node.left, key);
  else node.right = insert(node.right, key);
  return node;
}

function build(...keys) {
  let root = null;
  for (const key of keys) root = insert(root, key);
  return root;
}

function depth(node) {
  return node === null ? 0 : 1 + Math.max(depth(node.left), depth(node.right));
}

function steps(node, key) {
  let count = 1;
  while (node.key !== key) {
    node = key < node.key ? node.left : node.right;
    count++;
  }
  return count;
}

const mixed = build(50, 25, 75, 12, 37, 62, 88);
const ordered = build(12, 25, 37, 50, 62, 75, 88);
console.log(`вперемешку: глубина ${depth(mixed)}, шагов до 88 — ${steps(mixed, 88)}`);
console.log(`по порядку: глубина ${depth(ordered)}, шагов до 88 — ${steps(ordered, 88)}`);
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

class Node:
    def __init__(self, key: int) -> None:
        self.key = key
        self.left = None
        self.right = None


def insert(node, key: int):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node


def build(*keys: int):
    root = None
    for key in keys:
        root = insert(root, key)
    return root


def depth(node) -> int:
    return 0 if node is None else 1 + max(depth(node.left), depth(node.right))


def steps(node, key: int) -> int:
    count = 1
    while node.key != key:
        node = node.left if key < node.key else node.right
        count += 1
    return count


mixed = build(50, 25, 75, 12, 37, 62, 88)
ordered = build(12, 25, 37, 50, 62, 75, 88)
print(f"вперемешку: глубина {depth(mixed)}, шагов до 88 — {steps(mixed, 88)}")
print(f"по порядку: глубина {depth(ordered)}, шагов до 88 — {steps(ordered, 88)}")
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

Одни и те же семь ключей: вперемешку — глубина 3 и три шага до цели, по порядку — глубина 7 и семь шагов. На миллионе ключей это 20 шагов против миллиона.

Откуда берутся «20 шагов на миллионе». На каждом уровне сбалансированного дерева узлов вдвое больше, чем на предыдущем: один в корне, два ниже, четыре, восемь, и дерево высоты h вмещает до 2ʰ − 1 узлов. Миллион ключей укладывается в высоту, для которой 2ʰ ≥ миллион, то есть h = 20, тот самый log₂ N из статьи про O-нотацию. Поэтому «дерево на миллион узлов ищет за двадцать сравнений» не оценка, а арифметика, и она же объясняет, почему у выродившегося дерева высота равна числу узлов: там на каждом уровне ровно один узел.

Одну вещь в этом коде стоит заметить отдельно: повторный ключ он не отвергает. Ветка else срабатывает и когда ключ больше, и когда он равен — значит, второй такой же ключ ляжет в дерево вторым узлом, справа. Это решение, а не обязанность дерева: можно вместо вставки перезаписывать значение в найденном узле, и именно так поступают упорядоченные словари в библиотеках. Выбирать приходится осознанно — иначе два одинаковых ключа заведутся в дереве незаметно для вас.

То есть обещание O(log N) держится, только пока дерево остаётся сбалансированным — примерно одинаковой глубины во все стороны. Обычное дерево поиска этого не гарантирует. Решение — самобалансирующиеся деревья, которые перестраиваются при вставке: красно-чёрные деревья и деревья 2-3-4.

Деревья не только для поиска: коды Хаффмана

Двоичные деревья полезны не только как хранилище. Классический пример — коды Хаффмана. Идея: частым символам дать короткие битовые коды, редким — длинные (в обычной кодировке все символы занимают одинаково). Коды строят по дереву: символы — листья, и чем символ чаще, тем ближе к корню его лист и тем короче путь до него. Дерево строят снизу вверх, многократно объединяя два самых редких символа. Такое дерево гарантирует, что ни один код не является началом другого, — поэтому сжатую последовательность можно однозначно раскодировать. Встречается это в бекенде каждый день, только под другими именами: коды Хаффмана это вторая половина deflate, то есть gzip, которым сжат почти каждый HTTP-ответ, ими же сжаты заголовки в HTTP/2 (HPACK), и они внутри колоночных форматов вроде Parquet.

Как это сделано в стандартной библиотеке

Дерево из этой статьи — учебное: в рабочем коде его писать не нужно, в стандартной библиотеке лежит готовое и сразу самобалансирующееся, без ахиллесовой пяты с вырождением. Понимать устройство всё равно приходится — иначе непонятно, за что платят, когда берут упорядоченную карту.

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

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

Порядок и есть то, ради чего берут TreeMap: ключи всегда лежат по возрастанию, и появляются операции, которых у хеш-таблицы нет в принципе:

firstKey и lastKey отдают наименьший и наибольший ключ за O(log n). floorKey и ceilingKey с соседями higherKey и lowerKey находят ближайший ключ не больше или не меньше данного, тот самый «следующий по величине», которого искали преемником при удалении. А headMap, tailMap и subMap отвечают на диапазонный запрос: все записи от одной границы до другой.

Всё это объявлено в интерфейсе NavigableMap, и им же стоит объявлять переменную, когда эти методы нужны; там же descendingMap и descendingKeySet дают обход по убыванию без копирования, и pollFirstEntry с pollLastEntry забирают крайнюю запись за O(log n), что превращает TreeMap в упорядоченную очередь с удалением произвольного ключа, которой не хватает PriorityQueue.

Важно, что subMap и его родня возвращают не копию, а представление того же дерева: запись в него меняет исходную карту, и наоборот.

Главная грабля вот в чём: TreeMap определяет равенство ключей по compareTo (или компаратору), а не по equals. Для дерева два ключа одинаковы тогда, когда сравнение вернуло ноль, — и никак иначе.

живой пример

import java.util.Map;
import java.util.TreeMap;

public class TreeMapKeys {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        map.put("Заказ", 1);
        map.put("заказ", 2);
        System.out.println("размер: " + map.size());
        System.out.println("карта: " + map);
    }
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

Две строки не равны по equals, но компаратор считает их одинаковыми: записи одна, ключ в ней остался от первой вставки, а значение — от второй. Так же склеятся объекты, у которых compareTo учитывает не все поля. Поэтому сравнение для ключей TreeMap делают согласованным с equals. И мелочь: при естественном порядке null в качестве ключа TreeMap не принимает — сравнивать его не с чем.

Дерево из этой статьи — учебное, и здесь Go отличается от Java и большинства языков: дерева поиска в стандартной библиотеке нет ни в каком виде. Есть map, у которого порядка нет вовсе, есть срез с двоичным поиском, а самобалансирующееся дерево берут сторонним пакетом. Понимать устройство всё равно приходится — иначе непонятно, что именно вы теряете, обходясь без него.

Первый инструмент — отсортированный срез. slices.BinarySearch находит ключ или место для него за O(log n), slices.Insert вставляет в это место за O(N): соседей приходится сдвигать, но сдвиг делает copy, одна быстрая операция копирования памяти. До сотен тысяч ключей это обычно быстрее любого дерева, потому что срез лежит в памяти подряд и дружит с кешем. Порядок даётся бесплатно, а вместе с ним и операции, которых у map нет в принципе: наименьший и наибольший ключ это keys[0] и keys[len(keys)-1], ближайший ключ не меньше данного это индекс из BinarySearch, а диапазонный запрос это срез между двумя такими индексами.

живой пример

package main

import (
	"fmt"
	"slices"
)

func main() {
	var keys []int
	for _, k := range []int{50, 25, 75, 12, 37, 62, 88} {
		i, found := slices.BinarySearch(keys, k)
		if !found {
			keys = slices.Insert(keys, i, k)
		}
	}
	fmt.Println("по порядку:", keys)
	i, _ := slices.BinarySearch(keys, 40)
	fmt.Println("ближайший не меньше 40:", keys[i], " ближайший не больше 40:", keys[i-1])
	lo, _ := slices.BinarySearch(keys, 30)
	hi, _ := slices.BinarySearch(keys, 71)
	fmt.Println("все от 30 до 70:", keys[lo:hi])
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

Когда вставок и удалений много и они идут вперемешку с поиском, срез перестаёт справляться, и тогда берут пакет. Самый ходовой — github.com/google/btree, B-дерево в памяти: не двоичное, в каждом узле десятки ключей, зато узлов мало и они дружат с кешем; с версии 1.1 он обобщённый, btree.NewG[T] с функцией «меньше». Есть и классические красно-чёрные деревья в github.com/emirpasic/gods. Сложность у обоих честная: поиск, вставка, удаление, ближайший ключ, обход по диапазону — гарантированные O(log n), отсортированные данные им не страшны.

Главная грабля переезжает вместе с деревом из Java без изменений: дерево определяет равенство ключей через «меньше», а не через ==. В google/btree два ключа одинаковы, когда ни один не меньше другого. Если функция сравнения смотрит только на часть полей, скажем на имя без учёта регистра, записи «Заказ» и «заказ» склеятся: останется ключ от первой вставки со значением от второй. Поэтому функцию «меньше» делают согласованной с тем равенством, которое вы имеете в виду.

И мелочь про map: обход for range по нему идёт в намеренно случайном порядке, каждый запуск в новом. Кому нужны ключи по возрастанию, тот пишет slices.Sorted(maps.Keys(m)), и это O(n·log n) на каждый вызов; если такое делается в каждом запросе, это и есть сигнал, что пора заводить отсортированный срез или дерево.

Дерево из этой статьи — учебное, и здесь JavaScript отличается от Java: дерева поиска в стандартной библиотеке нет. Есть Map и Set, которые помнят порядок вставки, но не сортируют, есть массив с двоичным поиском, а самобалансирующееся дерево берут пакетом. Понимать устройство всё равно приходится — иначе непонятно, что именно вы теряете, обходясь без него.

Первый инструмент — отсортированный массив. Двоичный поиск пишут сами, десять строк, он находит ключ или место для него за O(log n), а splice вставляет в это место за O(N): соседей приходится сдвигать, но движок делает это одной операцией копирования памяти. До сотен тысяч ключей это обычно быстрее любого дерева, потому что массив чисел лежит в памяти плотно. Порядок даётся бесплатно, а вместе с ним и операции, которых у Map нет: наименьший и наибольший ключ это keys[0] и keys.at(-1), ближайший ключ не меньше данного это индекс из поиска, а диапазонный запрос это slice между двумя такими индексами.

живой пример

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

const keys = [];
for (const k of [50, 25, 75, 12, 37, 62, 88]) {
  const i = lowerBound(keys, k);
  if (keys[i] !== k) keys.splice(i, 0, k);
}
console.log("по порядку:", keys);
const i = lowerBound(keys, 40);
console.log("ближайший не меньше 40:", keys[i], " ближайший не больше 40:", keys[i - 1]);
console.log("все от 30 до 70:", keys.slice(lowerBound(keys, 30), lowerBound(keys, 71)));
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

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

Главная грабля переезжает из Java почти без изменений: дерево из пакета определяет равенство ключей через функцию сравнения, а не через ===. Если она сравнивает строки без учёта регистра, записи «Заказ» и «заказ» склеятся: останется ключ от первой вставки со значением от второй. Поэтому функцию сравнения делают согласованной с тем равенством, которое вы имеете в виду.

И мелочь про обычные объекты, которая маскируется под сортировку: Object.keys возвращает целочисленные ключи по возрастанию, а строковые — в порядке добавления. Объект { 2: "б", 1: "а" } отдаст ["1", "2"], и легко решить, что объект что-то сортирует. Не сортирует: добавьте ключ "x", и порядок перестанет быть числовым. Нужен порядок по ключу — держите отсортированный массив или дерево, а Map используйте как хеш-таблицу.

Дерево из этой статьи — учебное, и здесь Python отличается от Java: дерева поиска в стандартной библиотеке нет. Есть dict, который помнит порядок вставки, но не сортирует, есть модуль bisect для отсортированного списка, а самобалансирующееся дерево берут пакетом. Понимать устройство всё равно приходится — иначе непонятно, что именно вы теряете, обходясь без него.

Первый инструмент — отсортированный list с bisect. bisect_left находит ключ или место для него за O(log n), insort вставляет в это место за O(N): соседей приходится сдвигать, но сдвиг делает memmove, одна быстрая операция копирования памяти. До сотен тысяч ключей это обычно быстрее любого дерева на Python. Порядок даётся бесплатно, а вместе с ним и операции, которых у dict нет: наименьший и наибольший ключ это keys[0] и keys[-1], ближайший ключ не меньше данного это индекс из bisect_left, а диапазонный запрос это срез между двумя такими индексами.

живой пример

from bisect import bisect_left, insort

keys: list[int] = []
for k in (50, 25, 75, 12, 37, 62, 88):
    i = bisect_left(keys, k)
    if i == len(keys) or keys[i] != k:
        insort(keys, k)
print("по порядку:", keys)
i = bisect_left(keys, 40)
print("ближайший не меньше 40:", keys[i], " ближайший не больше 40:", keys[i - 1])
print("все от 30 до 70:", keys[bisect_left(keys, 30):bisect_left(keys, 71)])
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

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

Главная грабля переезжает из Java почти без изменений: упорядоченная структура определяет равенство ключей через сравнение, а не через == и хеш, как dict. SortedDict с ключом key=str.lower склеит записи «Заказ» и «заказ»: останется ключ от первой вставки со значением от второй. Поэтому функцию-ключ делают согласованной с тем равенством, которое вы имеете в виду.

И мелочь про dict: с Python 3.7 он помнит порядок вставки, и это часто путают с сортировкой. Кому нужны ключи по возрастанию, тот пишет sorted(d), и это O(n·log n) на каждый вызов; если такое делается в каждом запросе, это и есть сигнал, что пора заводить bisect или SortedDict.

Коротко

  • Двоичное дерево поиска сочетает быстрый поиск упорядоченного массива с быстрой вставкой списка — всё за O(log N) в сбалансированном виде.
  • Правило: у каждого узла левое поддерево меньше, правое больше. Поиск и вставка — спуск с отсечением половины на каждом шаге.
  • Симметричный обход выдаёт ключи по возрастанию. Удаление узла с двумя потомками решается заменой на преемника.
  • Обычное дерево вырождается в список при вставке отсортированных данных (O(N)); гарантию баланса дают самобалансирующиеся деревья.
  • Двоичные деревья применяют и вне поиска — например, для сжатия кодами Хаффмана.
  • Обходов три: прямой (узел, потом поддеревья: копирование, обход в глубину), симметричный (сортировка), обратный (поддеревья, потом узел: удаление, вычисление выражений).
  • Удаление пишут одним рекурсивным спуском: единственного потомка возвращают наверх, при двух потомках в узел переписывают ключ преемника и удаляют преемника из правого поддерева.
  • Дерево высоты h вмещает до 2ʰ − 1 узлов, отсюда 20 шагов на миллионе; коды Хаффмана живут в gzip, HPACK и Parquet.
  • Готовое дерево — TreeMap и TreeSet, красно-чёрное, гарантированные O(log n); NavigableMap даёт floorKey, subMap, descendingMap и pollFirstEntry; равенство ключей по compareTo, а не по equals.
  • Дерева в стандартной библиотеке нет: отсортированный срез со slices.BinarySearch и slices.Insert, под тяжёлую нагрузку google/btree; map обходится в случайном порядке; равенство в дереве через «меньше», а не ==.
  • Дерева в языке нет: отсортированный массив с самодельным двоичным поиском и splice, под тяжёлую нагрузку sorted-btree; Map хранит порядок вставки, а Object.keys сортирует только целочисленные ключи.
  • Дерева в стандартной библиотеке нет: отсортированный list с bisect и insort, под тяжёлую нагрузку sortedcontainers; dict хранит порядок вставки, sorted(d) на каждый запрос — сигнал завести упорядоченную структуру.

Что почитать дальше