Ниже — сжатое, но ёмкое описание устройства и алгоритмов для двух классических самобалансирующихся двоичных деревьев поиска (BST) — AVL и красно‑чёрных (RB) деревьев, затем сравнение асимптотики, поведения при последовательных/частично отсортированных данных и практические рекомендации, когда что предпочесть.

1) Структура и инварианты

AVL:

Каждый узел хранит ключ, ссылки на детей и дополнительную информацию о «балансе» (чаще balance factor = высота правого под‑дерева − высота левого, или просто высота).Инвариант: для любого узла разность высот его поддеревьев ∈ {−1, 0, +1}.Из-за строгого баланса высота дерева h = O(log n). Более точная оценка: h ≤ 1.44·log2(n + 2) − const.

Красно‑чёрное дерево (RB):

Каждый узел хранит ключ, ссылки и бит цвета (красный/чёрный).Инварианты:
1) корень чёрный;
2) красный узел не имеет красных детей (никаких двух подряд красных);
3) на всех путях от узла до листьев одинаковое число чёрных узлов (чёрная высота).Следствие: высота h ≤ 2·log2(n+1). То есть более «мягкий» баланс, чем у AVL.

2) Основные операции и алгоритмы коррекции

Общий подход: стандартный BST‑поиск для вставки/удаления, затем локальная «фиксация» инварианта с помощью вращений и/или перекраски/обновления баланса, проходя вверх по дереву.

AVL: вставка

Вставляем как в BST, устанавливаем новый лист с balance = 0.Поднимаясь вверх, обновляем факторы баланса; если фактор становится ±2, выполняем одну из 4 конфигураций:LL (одно правое вращение), RR (одно левое), LR (двойное: левое на ребёнке, потом правое), RL (двойное).После одной корректировки на первом встретившемся неравновесном (ниже по пути) узле баланс восстанавливается — больше вращений обычно не нужно (т. е. вставка приводит к O(1) вращениям: 1 или 2).

AVL: удаление

Удаляем как в BST (возможно заменяем узел преемником), затем при подъёме вверх обновляем факторы.Может потребоваться серия корректировок по пути к корню — в худшем случае до O(log n) (много последовательных вращений).

RB: вставка

Вставляем новый узел красным; затем выполняем фикс‑ап (перекраска и/или вращения) по правилу:Если родитель красный — есть нарушение; исправляют комбинацией перекраски и при необходимости одного или двух вращений.Количество вращений ограничено небольшим константным числом (обычно ≤2), но может потребоваться несколько перекрасок по пути к корню.

RB: удаление

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

3) Временная и пространственная сложность

Поиск: O(h) = O(log n) в обоих.Вставка/удаление:
Ассимптотически обе — O(log n) времени.Практические различия:AVL: чаще выполняет больше перестроек при удалении (в худшем — O(log n) вращений); при вставке — обычно 1–2 вращения.RB: вставка требует ≤O(1) вращений (часто только перекраски); удаление может потребовать O(log n) перекрасок и несколько вращений, но в среднем/на практике количество вращений меньше, чем у AVL при интенсивных модификациях.Память: RB требует 1 бит на цвет (реально обычно 1 байт), AVL требуется хранить фактор (можно в 2 бита, но в реализации чаще 1 байт/целое). Дополнительные указатели (родитель/дети) одинаковы.

4) Поведение при последовательных и частично отсортированных данных

Оба дерева гарантируют логарифмическую высоту и не деградируют до списка при вставке уже отсортированных ключей — то есть безопасность против «худшего» порядка входных данных.Однако реакция на последовательные вставки:
AVL: более строгая балансировка, поэтому при последовательных вставках будет выполняться больше вращений (и/или больше корректировок) для поддержания близкой к идеальной сбалансированности; CPU‑затраты на модификации выше.RB: часто выполняет лишь перекраску и реже вращения; вставки последовательных ключей приводят к меньшему количеству тяжёлых операций в среднем. Поэтому при длинных последовательных вставках RB обычно «дешевле» по числу вращений.Частично отсортированные данные (локально упорядоченные):
Если операций поиска много и сравнений дорогие, выгоднее иметь минимальную высоту — AVL даст немного меньшую высоту и чуть меньше сравнений.Если данные приходят с локальной вставочной «локальностью», RB может показать лучшее соотношение затрат на модификацию/балансировку.

5) Практические замечания и рекомендации

Когда выбирать AVL:
Доминируют операции поиска (reads) над модификациями; критичны минимальные задержки поиска.Нужна более плотная высота (меньше сравнений на поиск).В однопоточной/индексной структуре, где операции удаления редки.Когда выбирать RB:
Баланс между insert/erase и find; особенно если много вставок/удалений.Требуется простая реализация с невысокими накладными издержками при модификациях.Широко применим в системных/стандартных библиотеках (std::map, Java TreeMap используют RB) — проверено на практике.Другие соображения:
Если нужен минимальный коэффициент поиска и много памяти доступно — AVL.Для persistents (функциональных) реализаций многие исследователи предпочитают RB (Okasaki) или другие варианты, поскольку алгоритмы проще адаптируются к копированию узлов. Тем не менее, существуют и функциональные AVL‑реализации.Для дисковых/внешних структур (индексы баз данных) обычно используют B‑деревья / B+‑деревья, а не BST.Если важна простота и ожидается случайный порядок ключей — часто выбирают RB за простоту и низкие константы.

6) Короткое практическое резюме

Оба дают гарантии O(log n). AVL — строже сбалансирован → меньше сравнений при поиске, но при модификациях (особенно удалениях) может выполнять больше вращений. RB — «мягче» баланс, чуть выше дерево, но меньше затрат на перестроение при интенсивных вставках/удалениях; обычно предпочитается в библиотечных реализациях карт/сетей. Выбор зависит от профиля нагрузки: read‑heavy → AVL; write‑heavy / общий случай → RB.

Если хотите, могу:

показать пошаговый пример вставки/удаления в каждой структуре (с рисунками/псевдокодом),дать шаблон реализации на C/C++/Java,или сравнить их на конкретном наборе данных (симуляция числа вращений и сравнений).