Комментарии 28
Статью проглядел по диагонали, но визуализатор просто очаровал.
сейчас граммар-наци набегут.
«высата получается примерно»
Неплохо :)
Неплохо :)
Несколько менее понятная статья, чем предыдущая (ну та вообще была введением), но я так понял, что это обзорная статья различных видов, часть из которых будет рассмотрена более подробнее в «следующих сериях». Хотя и такого небольшого обзора хватило, чтобы лично меня навести на некоторые мысли. Но всё равно жду продолжения.
Спасибо, особенно за ссылки на дополнительные материалы, и ждём продолжения.
Спасибо, особенно за ссылки на дополнительные материалы, и ждём продолжения.
Огромное спасибо за обзор и данные по сложности операций во всех деревьях.
Как начинающему, хотелось бы получить совет.
Сейчас занят одним заданием по этой тематике (в общем-то, с образовательными целями).
Пытаюсь реализовать структуру данных с возможностью добавления, удаления и доступа к элементу по индексу за O(log N). Для этой цели выбрал структуру, основанную на красно-черном дереве. Можете дать какие-нибудь рекомендации (например, лучше вообще за основу не красно-черное брать)?
Как начинающему, хотелось бы получить совет.
Сейчас занят одним заданием по этой тематике (в общем-то, с образовательными целями).
Пытаюсь реализовать структуру данных с возможностью добавления, удаления и доступа к элементу по индексу за O(log N). Для этой цели выбрал структуру, основанную на красно-черном дереве. Можете дать какие-нибудь рекомендации (например, лучше вообще за основу не красно-черное брать)?
В принципе для этого подойдет любое дерево, у которого операции за O(log(n)) работают. Я собирался про расширения деревьев (в том числе и про порядковую статистику) рассказать после разбора пары реализаций сбалансированных деревьев. Эти расширения работают с любым из них абсолютно одинаково, так что стоит выбрать за основу наиболее интересный вариант)
Стало быть, scapegoat? :)
Это то дерево, про которое я знаю меньше всего из этой статьи )
Но ведь самое интересное: с настраиваемой жесткостью, стало быть «кастомизируемое». Параметрическое задание баланса скорость поиска/скорость изменения весьма интересно :)
Да, весьма)
С другой стороны, splay-дерево тоже очень даже интересно своей магией. Абсолютно шаманская операция splay, и шаманское доказательство, что с ней все работает)
С другой стороны, splay-дерево тоже очень даже интересно своей магией. Абсолютно шаманская операция splay, и шаманское доказательство, что с ней все работает)
Вот это шаманство и отпугивает. Слишком неочевидно для реализации дерева в первый раз.
возможно)
могу посоветовать только не выбирать первых троих — в их реализации несложно посадить какой-нибудь неочевидный баг и потом долго-долго его дебажить, для первого раза все остальные лучше подходят (правда про scapegoat я ничего не знаю — ни разу не писал)
могу посоветовать только не выбирать первых троих — в их реализации несложно посадить какой-нибудь неочевидный баг и потом долго-долго его дебажить, для первого раза все остальные лучше подходят (правда про scapegoat я ничего не знаю — ни разу не писал)
О черт :)
Если не выбирать первые три, то остается шаманское splay, хитрое параметрическое scapegoat и с виду безобидное декартово. Ну да, декартово, может, стоит попробовать, но по красно-черному мне довольно неплохие статьи встречались (первые 5 ссылок из гугла дают хорошие результаты). Так что не буду менять коня на переправе. (Готовая реализация на случай непоняток тоже уже нашлась :)
Если не выбирать первые три, то остается шаманское splay, хитрое параметрическое scapegoat и с виду безобидное декартово. Ну да, декартово, может, стоит попробовать, но по красно-черному мне довольно неплохие статьи встречались (первые 5 ссылок из гугла дают хорошие результаты). Так что не буду менять коня на переправе. (Готовая реализация на случай непоняток тоже уже нашлась :)
UPD: просьба интересующимся ответить на опрос: winger.habrahabr.ru/blog/66933/
Спасибо! В этот раз меньше деталей, но я так полагаю, что если углубиться, выйдет небольшая книжка :)
Почему-то мне казалось, что Вы собирались рассказать о том, как перебалансировать дерево. Я ошибся?
Почему-то мне казалось, что Вы собирались рассказать о том, как перебалансировать дерево. Я ошибся?
Формулы лучше записывать с помощью 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.(
— золотое сечение)
А где B-деревья? Самое главное практически — и нет :)
распечатал статью про Splay деревья. я о них никогда даже не слышал, а штука оказывается интересная. можно было бы по-больше расписать )
B, B+ деревьев нет (( Очень хотелось бы увидеть сводную таблицу по деревьям со сложностями основных операций и рекомендациям по тому, в каких областях применять.
Кстати, если уж рассматривать именно в плане практического применения, а не реализации — есть возможность сделать подборку открытых библиотек, в которых те или иные деревья реализованы? получилась бы просто отменная подборка по тематике.
B, B+ деревьев нет (( Очень хотелось бы увидеть сводную таблицу по деревьям со сложностями основных операций и рекомендациям по тому, в каких областях применять.
Кстати, если уж рассматривать именно в плане практического применения, а не реализации — есть возможность сделать подборку открытых библиотек, в которых те или иные деревья реализованы? получилась бы просто отменная подборка по тематике.
Интересно было бы ещё увидеть radix trees на хабре
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев