Comments 53
UPD: перенес в алгоритмы
Всё хорошо, только не понятно, зачем key/value пару называть a/b, а не key/value? :)
в хаскелле, я имею в виду
Да, так лучше будет. У меня иногда бывают заскоки с naming'ом )
А почему бы тогда left и right не назвать lesser и greater, чтобы подчеркнуть где, что лежит?
Названия left и right относятся к структуре дерева. В простейшей реализации lesser и greater могут быть удобнее, но в реализациях сбалансированных деревьев, где будут производиться различные структурные трансформации с деревом left и right имхо удобнее.
В принципе, так принято. Что-то вроде негласного правила =) К тому же, в некоторых реализациях бинарных деревьев значения могут быть неуникальными или lesser и greater не будет отражать суть и релевантность (к примеру, если ключами дерева будут hash значения).
Если б нам так лекции читали…
Отличная статья.
Все очень понятно написано, главное что даже не обязательно смотреть на код, чтобы все понять. А в 2 часа ночи это ой как актуально.
Спасибо!
Интересная и на мой взгляд, весьма полезная статья.
Жду продолжения.
Интересная и на мой взгляд, весьма полезная статья.
Жду продолжения.
Очень полезная статья. Спасибо большое!
Черт подери, вашему стиллю нужно поучиться — мало кто может так просто рассказывать о сложных вещах.
Хренасебе… вы программируете на Хаскелл?
Примеры на хаскеле не понятны человеку, даже поверхностно не знакомому с хаскелем.
Ждём статьи черно-красную сортировку, всякие разные оптимизации и прочие вкусности.
Ждём статьи черно-красную сортировку, всякие разные оптимизации и прочие вкусности.
жду «следующих серий».
Нисколько не умиляя автора статьи, просто вспомнил, где читал похожий материал!
А вообще лично мне пригодились вложенные деревья, когда делал действительно большой проект, как тут было не вспомнить дискретный анализ, и как я хохотал, когда учился, задаваясь вопросом, — «а нафиг оно мне нужно ?», а когда стало нужно, сел и начал учить! Ну, что-то я отвлекся, а вообще по практическому применению данной статьи, кому интересно загляните сюда, просто красивые картинки…
А вообще лично мне пригодились вложенные деревья, когда делал действительно большой проект, как тут было не вспомнить дискретный анализ, и как я хохотал, когда учился, задаваясь вопросом, — «а нафиг оно мне нужно ?», а когда стало нужно, сел и начал учить! Ну, что-то я отвлекся, а вообще по практическому применению данной статьи, кому интересно загляните сюда, просто красивые картинки…
Примере на Хаскеле просто выносят мозг :)
Первая мысль «сложно и криво», но понятно, что это просто другое и поэтому непривычно. Здорово.
Спасибо за статью, обязательно продолжайте.
Первая мысль «сложно и криво», но понятно, что это просто другое и поэтому непривычно. Здорово.
Спасибо за статью, обязательно продолжайте.
Хотел бы добавить ещё одну книжку к списку литературы Вирт, алгоритмы и структуры данных она хоть и старая, но фундаментальные вещи не меняются =)
Описано хорошо, думаю начинающим программистам будет полезно.
Меня поразило насколько Haskell лаконичнее Java. Размер исходников уменьшается в разы. Интересно, как там с читаемостью больших исходников? Я с Haskell не знаком.
Меня поразило насколько Haskell лаконичнее Java. Размер исходников уменьшается в разы. Интересно, как там с читаемостью больших исходников? Я с Haskell не знаком.
Скорее haskell не вынуждает отделять все подряд пробелами и концами строк. Если (забавы ради) измерять символами, то на глаз лаконичнее кажется java.=)
как это символами — и на глаз?
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
Я лишь имел ввиду специфический си-подобный стиль форматирования кода в java. И что в haskell стиль совсем другой.
С тем, что рекурсивные структуры функциональные языки компактно реализуют — не спорю. Про все математические абстракции остается лишь поверить вам: такого большого опыта функционального программирования у меня нет.
С тем, что рекурсивные структуры функциональные языки компактно реализуют — не спорю. Про все математические абстракции остается лишь поверить вам: такого большого опыта функционального программирования у меня нет.
как это символами — и на глаз?
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
на самом деле вы не правы, с математическими абстракциями функциональные языки действительно обходятся лаконичнее, чем императивные. во многом это является следствием самой их сущности.
Два вопроса:
1. Чем деревья лучше хеш-массивов?
2. Как происходит оптимизация хранения данных в дереве?
1. Чем деревья лучше хеш-массивов?
2. Как происходит оптимизация хранения данных в дереве?
Чем деревья лучше хеш-массивов?
Хеш таблица — абстракция. Её эффективные реализации сделаны на основе деревьев. При не интенсивной работе с небольшими данными хеш таблицы из стандартной библиотеки или встроенной в язык может быть достаточно, но при работе с серьезными данными она может стать узким местом.
У деревьев и хеш-таблиц свои плюсы и минусы.
Хеш-таблица работает на больших объемах данных быстрее, иногда даже на порядок. С другой стороны, они гораздо требовательнее к памяти, особенно на маленьких объемах. Кроме того, на основе деревьев можно строить более сложные структуры и они поддерживают быструю реализацию таких операций как поиск минимума/максимума, которые на хеш-таблице реализуются в общем случае только пробегом по всем
данным.
Таким образом, у каждой из этих структур есть своя ниша, в которой их применение наиболее эффективно
Хеш-таблица работает на больших объемах данных быстрее, иногда даже на порядок. С другой стороны, они гораздо требовательнее к памяти, особенно на маленьких объемах. Кроме того, на основе деревьев можно строить более сложные структуры и они поддерживают быструю реализацию таких операций как поиск минимума/максимума, которые на хеш-таблице реализуются в общем случае только пробегом по всем
данным.
Таким образом, у каждой из этих структур есть своя ниша, в которой их применение наиболее эффективно
Не лучше, они просто разные, по памяти (асимптотике и работе — см. перехеширование), времени (асимптотика деревьев хуже) и упорядоченности (в деревьях данные упорядочены).
спасибо статья супер
>> Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов >> (например, set и map в с++…
это не совсем так. у них внутри RB дерево.
это не совсем так. у них внутри RB дерево.
Спасибо за статью.
Интересно было ещё узнать разницу в скорости работы операций с бинарными деревьями реализованными на Java и Haskell. Что код на Хаскель короче это очевидно, а вот на сколько он медленнее?
Интересно было ещё узнать разницу в скорости работы операций с бинарными деревьями реализованными на Java и Haskell. Что код на Хаскель короче это очевидно, а вот на сколько он медленнее?
Написал небольшой тест, результаты на моей машине такие (n=200000):
haskell ~4.8 секунд
java ~1.4 секунды
то есть haskell медленнее примерно в 3.5 раза. По сравнению с кодом из статьи я внес небольшую оптимизацию в код на haskell, а именно сделал так чтобы дерево вычислялось сторого, а не лениво. Без этого оно работает еще раза в 3 дольше.
архив с исходниками теста
В данном случае такое большое отставание связано как раз с созданием объектов, которое я упомянул в статье. Если смотреть здесь, отставание не так велико
haskell ~4.8 секунд
java ~1.4 секунды
то есть haskell медленнее примерно в 3.5 раза. По сравнению с кодом из статьи я внес небольшую оптимизацию в код на haskell, а именно сделал так чтобы дерево вычислялось сторого, а не лениво. Без этого оно работает еще раза в 3 дольше.
архив с исходниками теста
В данном случае такое большое отставание связано как раз с созданием объектов, которое я упомянул в статье. Если смотреть здесь, отставание не так велико
«После этого я расскажу о реализации ropes и других возможных расширениях и применениях сбаланчированных деревьев.»
Честно говоря ничего нового не узнал. А почему статья называется «бинарные деревья», а в содержании только про деревья поиска?.. ведь это небольшая часть бинарных деревьев (ожидал увидеть больше)
Честно говоря ничего нового не узнал. А почему статья называется «бинарные деревья», а в содержании только про деревья поиска?.. ведь это небольшая часть бинарных деревьев (ожидал увидеть больше)
Ммм, честно говоря, код не разбирал, ибо лениво, а я не java-программист :)
Но вот в этих рассуждениях меня задел один момент
«Поступим по-другому: найдем в правом поддереве минимум. Ясно, что его можно найти если начать в правом сыне и идти до упора влево. Т.к у найденного минимума нет левого сына, можно вырезать его по аналогии со случаем 1 и вставить его вместо удалеемой вершины. Из-за того что он был минимальным в правом поддереве, свойство упорядоченности не нарушится:»
У минимума может и нет левого сына, но может быть правый. Ваш алгоритм корректно обработает всю ветку? :)
ведь так просто ее не пересадишь, и правую ветку нельзя оставить под родителя вашего минимума.
например
удаляемый узел Х
следующий узел минимума 15
наш минимум 10
правый сын минимума 18
просто забрать 10 нельзя, мы получим в левой ветке под 15тью 18
А если забирать всю ветку, то нужно будет найти куда (влево или вправо) подсадить 15ть
А что если у нас у минимума справа не сын, а целая ветвь? :)
Но вот в этих рассуждениях меня задел один момент
«Поступим по-другому: найдем в правом поддереве минимум. Ясно, что его можно найти если начать в правом сыне и идти до упора влево. Т.к у найденного минимума нет левого сына, можно вырезать его по аналогии со случаем 1 и вставить его вместо удалеемой вершины. Из-за того что он был минимальным в правом поддереве, свойство упорядоченности не нарушится:»
У минимума может и нет левого сына, но может быть правый. Ваш алгоритм корректно обработает всю ветку? :)
ведь так просто ее не пересадишь, и правую ветку нельзя оставить под родителя вашего минимума.
например
удаляемый узел Х
следующий узел минимума 15
наш минимум 10
правый сын минимума 18
просто забрать 10 нельзя, мы получим в левой ветке под 15тью 18
А если забирать всю ветку, то нужно будет найти куда (влево или вправо) подсадить 15ть
А что если у нас у минимума справа не сын, а целая ветвь? :)
уточнения
1. ведь так просто ее не пересадишь, и правую ветку МИНИМУМА нельзя оставить под родителя вашего минимума.
2. следующий узел РОДИТЕЛЬ минимума = 15
1. ведь так просто ее не пересадишь, и правую ветку МИНИМУМА нельзя оставить под родителя вашего минимума.
2. следующий узел РОДИТЕЛЬ минимума = 15
Можно — родитель минимума гарантированно больше всех вершин в правом сыне минимума.
Соответственно, в вашем примере правый сын минимума не может быть 18
Соответственно, в вашем примере правый сын минимума не может быть 18
Я правильно понимаю, что во втором случае при вставке нового элемента можно брать максимум в левом поддереве, а не минимум в правом?
Книга Кормена и др. «Introduction to algorithms», на английском.
я где можно взять рекомендованную книгу на русском Кормен Т., Лейзерсон Ч., Ривест Р.: «Алгоритмы: построение и анализ» (не важно: скачать или купить)
?
?
Картинки к посту сгинули… :(
Нашел версию с рабочими картинками на archive.org. Он вроде заблокирован, но это не такая проблема.
Большое спасибо) скилл «бинарные деревья» +1
Sign up to leave a comment.
Структуры данных: бинарные деревья. Часть 1