Pull to refresh

Comments 28

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

Спасибо, особенно за ссылки на дополнительные материалы, и ждём продолжения.
Да, пока я собираюсь подробнее разобрать несколько видов.
Огромное спасибо за обзор и данные по сложности операций во всех деревьях.
Как начинающему, хотелось бы получить совет.
Сейчас занят одним заданием по этой тематике (в общем-то, с образовательными целями).
Пытаюсь реализовать структуру данных с возможностью добавления, удаления и доступа к элементу по индексу за O(log N). Для этой цели выбрал структуру, основанную на красно-черном дереве. Можете дать какие-нибудь рекомендации (например, лучше вообще за основу не красно-черное брать)?
В принципе для этого подойдет любое дерево, у которого операции за O(log(n)) работают. Я собирался про расширения деревьев (в том числе и про порядковую статистику) рассказать после разбора пары реализаций сбалансированных деревьев. Эти расширения работают с любым из них абсолютно одинаково, так что стоит выбрать за основу наиболее интересный вариант)
Это то дерево, про которое я знаю меньше всего из этой статьи )
Но ведь самое интересное: с настраиваемой жесткостью, стало быть «кастомизируемое». Параметрическое задание баланса скорость поиска/скорость изменения весьма интересно :)
Да, весьма)
С другой стороны, splay-дерево тоже очень даже интересно своей магией. Абсолютно шаманская операция splay, и шаманское доказательство, что с ней все работает)
Вот это шаманство и отпугивает. Слишком неочевидно для реализации дерева в первый раз.
возможно)
могу посоветовать только не выбирать первых троих — в их реализации несложно посадить какой-нибудь неочевидный баг и потом долго-долго его дебажить, для первого раза все остальные лучше подходят (правда про scapegoat я ничего не знаю — ни разу не писал)
О черт :)
Если не выбирать первые три, то остается шаманское splay, хитрое параметрическое scapegoat и с виду безобидное декартово. Ну да, декартово, может, стоит попробовать, но по красно-черному мне довольно неплохие статьи встречались (первые 5 ссылок из гугла дают хорошие результаты). Так что не буду менять коня на переправе. (Готовая реализация на случай непоняток тоже уже нашлась :)
Да, красно-черные — самый популярный вариант, и реализации на куче языков есть
Можно и я задам вопрос. Правда что дерево отрезков придумали Мирзоянов и Дуров?
Я ничего про это не слышал. Википедия утверждает, что они придуманы J. L. Bentley в 1977 году. Возможно они их переоткрыли или придумали какое-нибудь их расширение, вроде массовых обновлений
Спасибо! В этот раз меньше деталей, но я так полагаю, что если углубиться, выйдет небольшая книжка :)
Почему-то мне казалось, что Вы собирались рассказать о том, как перебалансировать дерево. Я ошибся?
Формулы лучше записывать с помощью HTML и математических символов (Юникод придумали 18 лет назад) или используя TEX.
F_i ~ phi^n (phi=(sqrt(5)+1)/2 — золотое сечение)
Fi ≈ φn (φ = (√5 + 1)/2 — золотое сечение)
<em>F<sub>i</sub></em> ≈ <em>φ<sup>n</sup></em> (<em>φ</em> = (√5 + 1)/2 — золотое сечение)
( — золотое сечение)
К сожалению, корень над пятёркой не нависает и формулы размещены в тексте не очень красиво из-за хабраограничений на использование HTML и CSS.
Я почему-то не могу добиться чтобы TeXовские формулы не выпадали из текста, все время вверх выскакивают (
А где B-деревья? Самое главное практически — и нет :)
B-деревья не бинарные) Можно считать, что красно-черные — наиболее близкий к бинарным деревьям частный случай B-дерева
Это верно, но уже сколько статей вы написали, а про них всё ни слова :) Это же самый важный вид деревьев на текущий момент.
распечатал статью про Splay деревья. я о них никогда даже не слышал, а штука оказывается интересная. можно было бы по-больше расписать )

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

Кстати, если уж рассматривать именно в плане практического применения, а не реализации — есть возможность сделать подборку открытых библиотек, в которых те или иные деревья реализованы? получилась бы просто отменная подборка по тематике.
Only those users with full accounts are able to leave comments. Log in, please.