Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев

[valergrad]

Статью проглядел по диагонали, но визуализатор просто очаровал.

[winger]

Если что, это не я его писал)
Нашел ссылку на него в википедии

[Shiz]

сейчас граммар-наци набегут.

[Devgru]

«высата получается примерно»
Неплохо :)

[winger]

fixed)

[amlet]

Несколько менее понятная статья, чем предыдущая (ну та вообще была введением), но я так понял, что это обзорная статья различных видов, часть из которых будет рассмотрена более подробнее в «следующих сериях». Хотя и такого небольшого обзора хватило, чтобы лично меня навести на некоторые мысли. Но всё равно жду продолжения.

Спасибо, особенно за ссылки на дополнительные материалы, и ждём продолжения.

[winger]

Да, пока я собираюсь подробнее разобрать несколько видов.

[CONSTantius]

Огромное спасибо за обзор и данные по сложности операций во всех деревьях.
Как начинающему, хотелось бы получить совет.
Сейчас занят одним заданием по этой тематике (в общем-то, с образовательными целями).
Пытаюсь реализовать структуру данных с возможностью добавления, удаления и доступа к элементу по индексу за O(log N). Для этой цели выбрал структуру, основанную на красно-черном дереве. Можете дать какие-нибудь рекомендации (например, лучше вообще за основу не красно-черное брать)?

[winger]

В принципе для этого подойдет любое дерево, у которого операции за O(log(n)) работают. Я собирался про расширения деревьев (в том числе и про порядковую статистику) рассказать после разбора пары реализаций сбалансированных деревьев. Эти расширения работают с любым из них абсолютно одинаково, так что стоит выбрать за основу наиболее интересный вариант)

[CONSTantius]

Стало быть, scapegoat? :)

[winger]

Это то дерево, про которое я знаю меньше всего из этой статьи )

[CONSTantius]

Но ведь самое интересное: с настраиваемой жесткостью, стало быть «кастомизируемое». Параметрическое задание баланса скорость поиска/скорость изменения весьма интересно :)

[winger]

Да, весьма)
С другой стороны, splay-дерево тоже очень даже интересно своей магией. Абсолютно шаманская операция splay, и шаманское доказательство, что с ней все работает)

[CONSTantius]

Вот это шаманство и отпугивает. Слишком неочевидно для реализации дерева в первый раз.

[winger]

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

[CONSTantius]

О черт :)
Если не выбирать первые три, то остается шаманское splay, хитрое параметрическое scapegoat и с виду безобидное декартово. Ну да, декартово, может, стоит попробовать, но по красно-черному мне довольно неплохие статьи встречались (первые 5 ссылок из гугла дают хорошие результаты). Так что не буду менять коня на переправе. (Готовая реализация на случай непоняток тоже уже нашлась :)

[winger]

Да, красно-черные — самый популярный вариант, и реализации на куче языков есть

[winger]

UPD: просьба интересующимся ответить на опрос: winger.habrahabr.ru/blog/66933/

[valergrad]

Можно и я задам вопрос. Правда что дерево отрезков придумали Мирзоянов и Дуров?

[winger]

Я ничего про это не слышал. Википедия утверждает, что они придуманы J. L. Bentley в 1977 году. Возможно они их переоткрыли или придумали какое-нибудь их расширение, вроде массовых обновлений

[ZakharS]

Спасибо! В этот раз меньше деталей, но я так полагаю, что если углубиться, выйдет небольшая книжка :)
Почему-то мне казалось, что Вы собирались рассказать о том, как перебалансировать дерево. Я ошибся?

[cblp]

Формулы лучше записывать с помощью HTML и математических символов (Юникод придумали 18 лет назад) или используя T_EX.

F_i ~ phi^n (phi=(sqrt(5)+1)/2 — золотое сечение)

F_i ≈ φⁿ (φ = (√5 + 1)/2 — золотое сечение)

<em>F_i</em> ≈ <em>φⁿ</em> (<em>φ</em> = (√5 + 1)/2 — золотое сечение)

( — золотое сечение)

К сожалению, корень над пятёркой не нависает и формулы размещены в тексте не очень красиво из-за хабраограничений на использование HTML и CSS.

[winger]

Я почему-то не могу добиться чтобы TeXовские формулы не выпадали из текста, все время вверх выскакивают (

[proxor]

А где B-деревья? Самое главное практически — и нет :)

[winger]

B-деревья не бинарные) Можно считать, что красно-черные — наиболее близкий к бинарным деревьям частный случай B-дерева

[proxor]

Это верно, но уже сколько статей вы написали, а про них всё ни слова :) Это же самый важный вид деревьев на текущий момент.

[StepLg]

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

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

Кстати, если уж рассматривать именно в плане практического применения, а не реализации — есть возможность сделать подборку открытых библиотек, в которых те или иные деревья реализованы? получилась бы просто отменная подборка по тематике.

[SaveTheRbtz]

Интересно было бы ещё увидеть radix trees на хабре