Деревья, двоичные деревья


    5й выпуск медленно, но двигающегося вперед видеопроекта Computer Science Student. На этот раз — небольшая «лекция» о такой структуре данных, как деревья.
    Видео доступно в HD-качестве, но, как всегда, придется идти на vimeo.com.



    P.S. На сайте теперь появилось лого, предоставленное хорошим человеком BION'ом, появилось четыре возможности подписаться на youtube-канал, в том числе — через iTunes.

    P.P.S. Ссылка на обоину :) Уже успели!..
    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 29

      +2
      Часто такое приходиться делать при выводе древовидных комментариев или каких либо категорий и под категорий постов на сайтах…
        0
        хм, и не подумал о таком применении, хотя очень логично :)
          0
          я на всех сайтах так структуру храню.
          оч. удобно )
          +2
          Спасибо! Как раз недавно проходил эту тему в университете и не до конца понял.
            0
            рад что оказалось полезным!
              0
              а где можно посмотреть 1-4 ??? — мне так понравилось!!! :)
                0
                что такое 1-4?
            0
            google binary trees.
            да и вообще чего тут сложного?
            а вот скрестить это с nested sets уже интереснее ;)
              +1
              ничего сложного :)
              скрещивать незнаю, пока в планах осветить другие часто-используемые типы деревьев и некоторые другие структуры для эффективного хранения данных
                +2
                Без простого не сделать сложного:)
                0
                Понятие «обход дерева» вы угадали :)
                Ну и, наверное, на каждой «программерской» специальности в универе есть задача по описанию определенного вида дерева в виде связанного списка :)
                  0
                  :)
                  О да, мы имплементировали на яве простые деревья, двоичные, binary search trees и AVL-trees, и даже на финальном экзамене нужно было написать java-интерфейс для одной из таких структур
                  0
                  мне понравилось. хоть и слишком просто. даже для тех кто не проходил в институте)
                  у меня немного другое предложение. лучше программу всю составить. с необходимыми ссылками на источники информации. вот это было бы очень полезно.
                    0
                    Вы имеете ввиду прямо си- или ява-кодом? можно :)
                      0
                      Нет :) Не всмысле софта. Программа обучения. Тоесть вобщем выписать всю программу как содержание книжки.
                    +1
                    Спасбио за лекцию. Было интересно как звучит по этому поводу теория… наверно многим программистам приходилось работать с деревьями на интуитивном уровне…

                    Подскажите плиз:
                    Есть ли какая-то теория по поводу сравнения двух узлов дерева.
                    Есть два узла и нужно определить какие положения они занимают в дереве относительно друг друга.
                    p1, p2. В варианте до которого додумал могут быть следующие ответы
                    p2==p1 — ответ 0,
                    p2 является одним из родителей p1 — ответ 1,
                    p2 не является одним из родителем то есть находится на каком-то отвороте с родителей p1 — ответ 2.
                    Таким образом compare(p1,p2) получим ответы -2,-1,0,1,2 и можно делать выводы и принимать решения.
                    Не хватает теории… может есть способ более детального описания положения точек друг относительно друга? Или как это относительное положение можно вообще описать
                      +1
                      Смотря что вы считаете родителями и детьми. Например я могу начать обходить дерево с одного из этих узлов, а могу начать откуда-то со стороны. Поэтому для вашей задачи нужно использовать направленный граф, чтобы показывать кто кого породил. Однако и в таком случае может получиться так, что два узла не являются родительскими по отношению друг к другу, простой пример: p1 -> pX < — p2.
                        0
                        Так понял вы говорить про какой-то более общий случай.
                        В случае, вроде файловой системы, у узла один родитель, и два узла быть родителями друг друга в принципе не могут… По моему, дерево уже подразумевает что родитель у узла только один, и как следствие у дерева один корень.
                        Вообще я теорию не знаю, потому и спрашиваю, как можно описать положение двух узлов относительно друг друга… пошёл смотреть, что такое направленный граф
                          +1
                          Вы про фс не упоминали, так что уж извините. Направленный граф это когда вы между двумя узлами ставите не линию, а стрелочку, обозначая кто из них родитель.
                            0
                            понятно… спасиб
                          0
                          Вбиваю в google «направленый граф» первая в списке ссылка с описанием
                          «Направленный граф то же что Ориентированный граф.»
                          ништяк)
                          В файловой системе узлы друг относительно друга описываются относительными ссылками, Тоже вариант иди наверх, наверх, потом сюда туда и я тут.
                          0
                          Ну, если взять легкий вариант с бинарным деревом, где, как кто-то ниже уже указал, у узла не может быть двух родителей «первого уровня».
                          обычно такие деревья делаются через двойные связные списки, то есть простой проверкой p1.parent==p2 или p2.leftChild==p1 можно определить эту свзяь

                          если же интересует является ли узел p1 хоть каким-нибудь родителем узла p2 (то есть, если двигаться от узла p1 только вниз, можно ли добраться до узла p2), то алгоритм тоже получается простой (while iterator.next!=p2 бла бла), но в плане эффективности будет уже намного медленнее первого (O(logn))
                          +2
                          Уважаемый freetonik.
                          Нескромный вопрос — а вот презентации powerpoint-овские по которой рассказываете можете выложить?
                            0
                            Конечно :)
                            https://dl.getdropbox.com/u/72746/css/comp%202402/trees/Trees.ppt
                            +1
                            «Свойства двоичных деревьев» при данном определении не работают: или в определении потомков должно быть либо нуль либо два; или в свойствах — количества узлов соотносятся как неравенства.
                              0
                              Вы правы, ошибочка вышла, поправлю
                              0
                              Спасибо за информацию, но мне кажется много лишних слов в видео.
                                0
                                согласен, не особо. досматривать не стал.
                                  0
                                  Я чего-то недопонял или на 12-ом слайде ошибка?

                                  Судя по алгоритму, узел посещается после посещения его левого и до посещения правого поддерева. В слайде же написано, что «узел посещается после посещения его левого и правого поддерева»…

                                  Это описание прямо столку сбило )

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое