Наклоняющееся влево красно-черное дерево.
| Наклоняющееся влево красно-черное дерево. | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 | ||||||||||||||||||||||||
| Тип | дерево | |||||||||||||||||||||||
| Изобретенный | 2008 | |||||||||||||||||||||||
| Изобретён | Роберт Седжвик | |||||||||||||||||||||||
| ||||||||||||||||||||||||
Наклоняющееся влево красно-черное дерево ( LLRB ) — это тип самобалансирующегося двоичного дерева поиска , представленный Робертом Седжвиком . Это вариант красно-черного дерева , гарантирующий ту же асимптотическую сложность операций, но более простой в реализации. [ 1 ]
Характеристики
[ редактировать ]Наклоненное влево красно-черное дерево удовлетворяет всем свойствам красно-черного дерева:
- Каждый узел либо красный, либо черный.
- Узел NIL считается черным.
- Красный узел не имеет красного дочернего узла.
- Каждый путь от данного узла к любому из его потомков NIL-узлов проходит через одинаковое количество черных узлов.
- Корень черный (по соглашению).
Кроме того, свойство с левым уклоном гласит, что:
- Если у узла есть только один красный дочерний элемент, это должен быть левый дочерний узел.
Свойство наклона влево уменьшает количество случаев, которые необходимо учитывать при реализации операций с деревом поиска.
Отношение к 2–3 и 2–3–4 деревьям
[ редактировать ]
Деревья LLRB — это изоморфные 2–3–4 деревья . В отличие от обычных красно-черных деревьев, 3-узлы всегда наклонены влево, что делает эту связь соответствием 1 к 1 . Это означает, что каждому дереву LLRB соответствует уникальное дерево 2–3–4, и наоборот.
Если мы наложим дополнительное требование, что узел не может иметь двух красных детей, деревья LLRB станут изоморфными 2–3 деревьям , поскольку 4-узлы теперь запрещены. Седжвик отмечает, что реализации деревьев LLRB 2–3 и деревьев LLRB 2–3–4 различаются только положением одной строки кода. [ 1 ]
Анализ
[ редактировать ]Все предложенные алгоритмы красно-черного дерева характеризуются наихудшим временем поиска, ограниченным небольшим постоянным кратным log N в дереве из N ключей, а поведение, наблюдаемое на практике, обычно на то же кратное число быстрее, чем граница наихудшего случая, близкая к оптимальному log N исследованных узлов, которые наблюдались бы в идеально сбалансированном дереве.
в левом красно-черном дереве 2–3 , построенном из N В частности, эксперименты Седжвика показывают, что случайных ключей:
- Случайный успешный поиск исследует log 2 N − 0,5 узлов.
- Средняя высота дерева составляет около 2 с.ш. см
- Средний размер левого поддерева демонстрирует логарифмическое колебательное поведение.
Библиография
[ редактировать ]- Роберта Седжвика Java- реализация LLRB из его статьи 2008 года.
- Роберт Седжвик. 20 апреля 2008 г. Анимация операций LLRB.
- Структуры открытых данных. Раздел 9.2.2. Наклоняющиеся влево красно-черные деревья , Пэт Морин
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Седжвик, Роберт (2008). «Наклоняющиеся влево красно-черные деревья» (PDF) . Наклоняющиеся влево красно-черные деревья . Департамент компьютерных наук Принстонского университета.
Внешние ссылки
[ редактировать ]- Роберт Седжвик. Наклоненные влево красно-черные деревья . Прямая ссылка на PDF .
- Роберт Седжвик. Слайд «Наклоненные влево красно-черные деревья» , октябрь 2008 г.
- Линус Эк, Ола Хольмстрем и Стеван Анджелкович. 19 мая 2009 г. Формализация деревьев Арне Андерссона и левых красно-черных деревьев в Агде.
- Жюльен Остер. 22 марта 2011 г. Реализация Agda удаления в левых красно-черных деревьях.
- Кадзу Ямамото. 19.10.2011. Чисто функциональные красно-черные деревья, наклоненные влево
- Наклоненные влево красно-черные деревья считаются вредными
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |