Pull to refresh

Comments 53

Всё хорошо, только не понятно, зачем key/value пару называть a/b, а не key/value? :)
Да, так лучше будет. У меня иногда бывают заскоки с naming'ом )
А почему бы тогда left и right не назвать lesser и greater, чтобы подчеркнуть где, что лежит?
Названия left и right относятся к структуре дерева. В простейшей реализации lesser и greater могут быть удобнее, но в реализациях сбалансированных деревьев, где будут производиться различные структурные трансформации с деревом left и right имхо удобнее.
В принципе, так принято. Что-то вроде негласного правила =) К тому же, в некоторых реализациях бинарных деревьев значения могут быть неуникальными или lesser и greater не будет отражать суть и релевантность (к примеру, если ключами дерева будут hash значения).
Если б нам так лекции читали…
Все очень понятно написано, главное что даже не обязательно смотреть на код, чтобы все понять. А в 2 часа ночи это ой как актуально.
В 2 часа ночи актуально спать, а не смотреть на код :)
Спасибо!
Интересная и на мой взгляд, весьма полезная статья.
Жду продолжения.
Черт подери, вашему стиллю нужно поучиться — мало кто может так просто рассказывать о сложных вещах.
Хренасебе… вы программируете на Хаскелл?
Примеры на хаскеле не понятны человеку, даже поверхностно не знакомому с хаскелем.

Ждём статьи черно-красную сортировку, всякие разные оптимизации и прочие вкусности.
«Примеры на хаскеле не понятны человеку, даже поверхностно не знакомому с хаскелем.»

Где-то лишнее «не»?
Скорее, тут нужна транспозиция: «Примеры на хаскеле не понятны человеку, не знакомому с хаскелем даже поверхностно». :)
Нисколько не умиляя автора статьи, просто вспомнил, где читал похожий материал!
А вообще лично мне пригодились вложенные деревья, когда делал действительно большой проект, как тут было не вспомнить дискретный анализ, и как я хохотал, когда учился, задаваясь вопросом, — «а нафиг оно мне нужно ?», а когда стало нужно, сел и начал учить! Ну, что-то я отвлекся, а вообще по практическому применению данной статьи, кому интересно загляните сюда, просто красивые картинки…
Примере на Хаскеле просто выносят мозг :)

Первая мысль «сложно и криво», но понятно, что это просто другое и поэтому непривычно. Здорово.

Спасибо за статью, обязательно продолжайте.
Описано хорошо, думаю начинающим программистам будет полезно.

Меня поразило насколько Haskell лаконичнее Java. Размер исходников уменьшается в разы. Интересно, как там с читаемостью больших исходников? Я с Haskell не знаком.
Скорее haskell не вынуждает отделять все подряд пробелами и концами строк. Если (забавы ради) измерять символами, то на глаз лаконичнее кажется java.=)
как это символами — и на глаз?
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
Я лишь имел ввиду специфический си-подобный стиль форматирования кода в java. И что в haskell стиль совсем другой.
С тем, что рекурсивные структуры функциональные языки компактно реализуют — не спорю. Про все математические абстракции остается лишь поверить вам: такого большого опыта функционального программирования у меня нет.
как это символами — и на глаз?
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
Два вопроса:

1. Чем деревья лучше хеш-массивов?

2. Как происходит оптимизация хранения данных в дереве?
Чем деревья лучше хеш-массивов?


Хеш таблица — абстракция. Её эффективные реализации сделаны на основе деревьев. При не интенсивной работе с небольшими данными хеш таблицы из стандартной библиотеки или встроенной в язык может быть достаточно, но при работе с серьезными данными она может стать узким местом.
Не совсем так. Абстракция обычно называется ассоциативным массивом, а деревья и хеш-таблицы — его реализации.
У деревьев и хеш-таблиц свои плюсы и минусы.
Хеш-таблица работает на больших объемах данных быстрее, иногда даже на порядок. С другой стороны, они гораздо требовательнее к памяти, особенно на маленьких объемах. Кроме того, на основе деревьев можно строить более сложные структуры и они поддерживают быструю реализацию таких операций как поиск минимума/максимума, которые на хеш-таблице реализуются в общем случае только пробегом по всем
данным.
Таким образом, у каждой из этих структур есть своя ниша, в которой их применение наиболее эффективно
Не лучше, они просто разные, по памяти (асимптотике и работе — см. перехеширование), времени (асимптотика деревьев хуже) и упорядоченности (в деревьях данные упорядочены).
>> Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов >> (например, set и map в с++…
это не совсем так. у них внутри RB дерево.
Да, правильно. RB-дерево (или красно-черное дерево) — один из способов балансировки обычного бинарного дерева поиска
да, я понимаю, что это частный случай. просто этот ваш коммент понятней бы смотрелся в тексте вместо. ) поэтому и написал не совсем так.
Спасибо за статью.
Интересно было ещё узнать разницу в скорости работы операций с бинарными деревьями реализованными на Java и Haskell. Что код на Хаскель короче это очевидно, а вот на сколько он медленнее?
Написал небольшой тест, результаты на моей машине такие (n=200000):
haskell ~4.8 секунд
java ~1.4 секунды
то есть haskell медленнее примерно в 3.5 раза. По сравнению с кодом из статьи я внес небольшую оптимизацию в код на haskell, а именно сделал так чтобы дерево вычислялось сторого, а не лениво. Без этого оно работает еще раза в 3 дольше.

архив с исходниками теста

В данном случае такое большое отставание связано как раз с созданием объектов, которое я упомянул в статье. Если смотреть здесь, отставание не так велико
«После этого я расскажу о реализации ropes и других возможных расширениях и применениях сбаланчированных деревьев.»
Честно говоря ничего нового не узнал. А почему статья называется «бинарные деревья», а в содержании только про деревья поиска?.. ведь это небольшая часть бинарных деревьев (ожидал увидеть больше)
fixed
Это лишь первая статья, надеюсь в следующих для вас найдется что-нибудь интересное
Ммм, честно говоря, код не разбирал, ибо лениво, а я не java-программист :)

Но вот в этих рассуждениях меня задел один момент

«Поступим по-другому: найдем в правом поддереве минимум. Ясно, что его можно найти если начать в правом сыне и идти до упора влево. Т.к у найденного минимума нет левого сына, можно вырезать его по аналогии со случаем 1 и вставить его вместо удалеемой вершины. Из-за того что он был минимальным в правом поддереве, свойство упорядоченности не нарушится:»

У минимума может и нет левого сына, но может быть правый. Ваш алгоритм корректно обработает всю ветку? :)
ведь так просто ее не пересадишь, и правую ветку нельзя оставить под родителя вашего минимума.

например

удаляемый узел Х
следующий узел минимума 15
наш минимум 10
правый сын минимума 18

просто забрать 10 нельзя, мы получим в левой ветке под 15тью 18
А если забирать всю ветку, то нужно будет найти куда (влево или вправо) подсадить 15ть
А что если у нас у минимума справа не сын, а целая ветвь? :)
уточнения

1. ведь так просто ее не пересадишь, и правую ветку МИНИМУМА нельзя оставить под родителя вашего минимума.

2. следующий узел РОДИТЕЛЬ минимума = 15
Можно — родитель минимума гарантированно больше всех вершин в правом сыне минимума.
Соответственно, в вашем примере правый сын минимума не может быть 18
Да, действительно, я невнимательно прочитал о добавлении новых элементов.
Я правильно понимаю, что во втором случае при вставке нового элемента можно брать максимум в левом поддереве, а не минимум в правом?
Да, конечно. Эти варианты абсолютно симметричны
я где можно взять рекомендованную книгу на русском Кормен Т., Лейзерсон Ч., Ривест Р.: «Алгоритмы: построение и анализ» (не важно: скачать или купить)

?
Only those users with full accounts are able to leave comments. Log in, please.