Дерево козлов отпущения
-
История и основные характеристики
- Дерево козлов отпущения изобретено Арне Андерссоном в 1989 году и Игалем Гальпериным и Рональдом Л. Ривестом в 1993 году.
- Обеспечивает наихудшее время поиска O(log n) и амортизированное время вставки и удаления O(log n).
- Не требует дополнительных затрат памяти на каждый узел, хранит только два указателя на дочерние узлы.
-
Теория и балансировка
- Дерево козлов отпущения сбалансировано по α-весу, если половина узлов находится слева от корня, а половина справа.
- Дерево слабо сбалансировано по высоте, но не всегда сохраняет α-баланс веса.
- Поддерживает любое значение α, такое что 0,5 < α < 1, что позволяет выбирать оптимальное значение для конкретных приложений.
-
Операции
- Поиск по стандартному дереву бинарного поиска имеет наихудшее время O(log n).
- Вставка требует перебалансировки, если узел нарушает свойство α-height-balance.
- Удаление проще, чем вставка, требует перестройки всего дерева вокруг корня.
-
Эскиз доказательства стоимости
- Вставка требует O(n) времени в наихудшем случае, но амортизированное время O(log n).
- Удаление требует O(n) времени в наихудшем случае, но амортизированное время O(log n).
-
Этимология
- Название «Дерево козлов отпущения» основано на библейском ритуале, где козел отпущения используется для перекладывания вины.