Красно-черное дерево, наклоненное влево - Left-leaning red–black tree

Красно-черное дерево, наклоненное влево
Тип	дерево
Изобрел	2008
Изобретенный	Роберт Седжвик
Сложность времени в нотация большой O
Алгоритм Средний Худший случай Космос O (п) O (п) Поиск O (журнал п) O (журнал п) Вставлять O (журнал п) O (журнал п) Удалить O (журнал п) O (журнал п)

А левый красно-черный (LLRB) дерево является разновидностью самобалансирующееся двоичное дерево поиска. Это вариант красно-черное дерево и гарантирует ту же асимптотическую сложность для операций, но разработан таким образом, чтобы его было проще реализовать.

Свойства наклоненного влево красно-черного дерева

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

В частности, в левом красно-черном 2–3 дерева построен из N случайные ключи:

• Случайный успешный поиск исследует бревно₂ N − 0.5 узлы.
• Средняя высота дерева около 2 журнала₂ N
• Средний размер левого поддерева демонстрирует логарифмически колеблющееся поведение.

внешняя ссылка

Статьи

• Роберт Седжвик. Красно-черные деревья, склоняющиеся влево. Прямая ссылка на PDF.
• Роберт Седжвик. Красно-черные деревья, склоняющиеся влево (слайды). Две версии:
  • Роберт Седжвик. Падающие влево красно-черные деревья (слайды), с семинара в Дагштуле в феврале 2008 г. Устарело.
  • Роберт Седжвик. Красно-черные деревья, наклоняющиеся влево (слайды), апрель 2008 г .; обновлено
• Линус Эк, Ола Холмстрем и Стеван Анджелкович. 19 мая 2009 г. Формализация деревьев Арне Андерссона и красно-черных деревьев влево в Агде
• Жюльен Остер. 22 марта 2011 г. Реализация Agda удаления в лево наклоненных красно-черных деревьях.
• Кадзу Ямамото. 2011.10.19. Чисто функциональные красно-черные деревья с наклоном влево

Реализации

Автор	Дата	Язык	Вариант	Примечания	Связь
Роберт Седжвик	2008	Ява		Из эта бумага Sedgewick
Дэвид Энсон	2 июня 2009 г.	C #			Поддержание баланса: универсальная реализация красно-черного дерева для .NET.
Казу-Ямамото	2011	Haskell			llrbtree (Data.Set.LLRBTree )
Ли Станца	2010	C ++		Включает обсуждение	Сбалансированные деревья, часть 4: красно-черные деревья, наклоняющиеся влево
Джейсон Эванс	2010	C	2-3		rb.h
Никола Бортиньон	8 декабря 2010 г.	ActionScript 3			Внедрение AS3 и обсуждение
Уильям в 25thandClement.com	2011	C	2-3 вариант с использованием итерации с родительскими указателями		llrb.h: Красно-черное дерево, наклоненное влево
Мацей Пехотка	2009	Вала			Gee.TreeMap
Петар Маймунков	2010	Идти	2-3		GoLLRB
Себастьян Шапюи	2015	C			C - левосторонняя реализация rbtree
Сынён Ким	2015	C	2-3-4 вариант		C реализация
Робин Хеггелунд Хансен	2018	Вяз			Вяз реализация
Р. Пратап Чакраварти	2019	Ржавчина			Реализация на Rust

Другой

• Роберт Седжвик. 20 апреля 2008. Анимация операций LLRB.
• Структуры открытых данных - Раздел 9.2.2 - Красно-черные деревья с наклоном влево, Пэт Морин
• Красно-черные деревья, склоняющиеся влево, считаются вредными