Структуры данных: бинарные деревья. Часть 1

    Интро



    Этой статьей я начинаю цикл статей об известных и не очень структурах данных а так же их применении на практике.

    В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

    Начать я решил с бинарных деревьев поиска, так как это достаточно базовая, но в то же время интересная штука, у которой к тому же существует большое количество модификаций и вариаций, а так же применений на практике.

    Зачем это нужно?



    Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов (например, set и map в с++ или TreeSet и TreeMap в java). Более сложные применения включают в себя ropes (про них я расскажу в одной из следующих статей), различные алгоритмы вычислительной геометрии, в основном в алгоритмах на основе «сканирующей прямой».

    В этой статье деревья будут рассмотрены на примере реализации ассоциативного массива. Ассоциативный массив — обобщенный массив, в котором индексы (их обычно называют ключами) могут быть произвольными.

    Ну-с, приступим



    Двоичное дерево состоит из вершин и связей между ними. Конкретнее, у дерева есть выделенная вершина-корень и у каждой вершины может быть левый и правый сыновья. На словах звучит несколько сложно, но если взглянуть на картинку все становится понятным:

    Пример бинарного дерева

    У этого дерева корнем будет вершина A. Видно, что у вершины D отсутствует левый сын, у вершины B — правый, а у вершин G, H, F и I — оба. Вершины без сыновей принято называть листьями.

    Каждой вершине X можно сопоставить свое дерево, состоящее из вершины, ее сыновей, сыновей ее сыновей, и т.д. Такое дерево называют поддеревом с корнем X. Левым и правым поддеревьями X называют поддеревья с корнями соответственно в левом и правом сыновьях X. Заметим, что такие поддеревья могут оказаться пустыми, если у X нет соответствующего сына.

    Данные в дереве хранятся в его вершинах. В программах вершины дерева обычно представляют структурой, хранящей данные и две ссылки на левого и правого сына. Отсутствующие вершины обозначают null или специальным конструктором Leaf:

    data Ord key => BSTree key value = Leaf | Branch key value (BSTree key value) (BSTree key value)
                                       deriving (Show)
    

    static class Node<T1, T2> {
            T1 key;
            T2 value;
             Node<T1, T2> left, right;
           
            Node(T1 key, T2 value) {
                    this.key = key;
                    this.value = value;
            }
    }
    


    Как видно из примеров, мы требуем от ключей, чтобы их можно было сравнивать между собой (Ord a в haskell и T1 implements Comparable<T1> в java). Все это не спроста — для того, чтобы дерево было полезным данные должны храниться в нем по каким-то правилам.

    Какие же это правила? Все просто: если в вершине X хранится ключ x, то в левом (правом) поддереве должны храниться только ключи меньшие (соответственно большие) чем x. Проиллюстрируем:

    Пример BST с данными

    Что же нам дает такое упорядочевание? То, что мы легко можем отыскать требуемый ключ x в дереве! Просто сравним x со значением в корне. Если они равны, то мы нашли требуемое. Если же x меньше (больше), то он может оказаться только в левом (соответственно правом) поддереве. Пусть например мы ищем в дереве число 17:

    Поиск в дереве числа 17

    Функция, получающая значение по ключу:

    get :: Ord key => BSTree key value -> key -> Maybe value
    get Leaf _ = Nothing
    get (Branch key value left right) k
        | k < key  = get left k
        | k > key  = get right k
        | k == key = Just value
    

    public T2 get(T1 k) {
            Node<T1, T2> x = root;
            while (x != null) {
                    int cmp = k.compareTo(x.key);
                    if (cmp == 0) {
                            return x.value;
                    }
                    if (cmp < 0) {
                            x = x.left;
                    } else {
                            x = x.right;
                    }
            }
            return null;
    }
    


    Добавление в дерево



    Теперь попробуем сделать операцию добавления новой пары ключ/значение (a,b). Для этого будем спускаться по дереву как в функции get, пока не найдем вершину с таким же ключем, либо не дойдем до отсутсвующего сына. Если мы нашли вершину с таким же ключем, то просто меняем соответствующее значение. В противно случае легко понять что именно в это место следует вставить новую вершину, чтобы не нарушить порядок. Рассмотрим вставку ключа 42 в дерево на прошлом рисунке:

    Добавление вершины в дерево

    Код:

    add :: Ord key => BSTree key value -> key -> value -> BSTree key value
    add Leaf k v = Branch k v Leaf Leaf
    add (Branch key value left right) k v
        | k < key  = Branch key value (add left k v) right
        | k > key  = Branch key value left (add right k v)
        | k == key = Branch key value left right
    

    public void add(T1 k, T2 v) {
            Node<T1, T2> x = root, y = null;
            while (x != null) {
                    int cmp = k.compareTo(x.key);
                    if (cmp == 0) {
                            x.value = v;
                            return;
                    } else {
                            y = x;
                            if (cmp < 0) {
                                    x = x.left;
                            } else {
                                    x = x.right;
                            }
                    }
            }
            Node<T1, T2> newNode = new Node<T1, T2>(k, v);
            if (y == null) {
                    root = newNode;
            } else {
                    if (k.compareTo(y.key) < 0) {
                            y.left = newNode;
                    } else {
                            y.right = newNode;
                    }
            }
    }
    


    Лирическое отступление о плюсах и минусах функционального подхода



    Если внимательно рассмотреть примеры на обоих языках, можно увидеть некоторое различие в поведении функциональной и императивной реализаций: если на java мы просто модифицируем данные и ссылки в имеющихся вершинах, то версия на haskell создает новые вершины вдоль всего пути, пройденного рекурсией. Это связано с тем, что в чисто функциональных языках нельзя делать разрушающие присваивания. Ясно, что это ухудшает производительность и увеличивает потребляемую память. С другой стороны, у такого подхода есть и положительные стороны: отсутствие побочных эффектов сильно облегчает понимание того, как функционирует программа. Более подробно об этом можно прочитать в практически любом учебнике или вводной статье про функциональное программирование.

    В этой же статье я хочу обратить внимание на другое следствие функционального подхода: даже после добавления в дерево нового элемента старая версия останется доступной! За счет этого эффекта работают ropes, в том числе и в реализации на императивных языках, позволяя реализовывать строки с асимптотически более быстрыми операциями, чем при традиционном подходе. Про ropes я расскажу в одной из следующих статей.

    Вернемся к нашим баранам



    Теперь мы подобрались к самой сложной операции в этой статье — удалению ключа x из дерева. Для начала мы, как и раньше, найдем нашу вершину в дереве. Теперь возникает два случая. Случай 1 (удаляем число 5):

    Удаление вершины: случай 1. до

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

    Удаление вершины: случай 1. после

    Если же правый сын есть, налицо случай 2 (удаляем снова вершину 5, но из немного другого дерева):

    Удаление вершины: случай 2. до

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

    Удаление вершины: случай 2. после

    Реализация удаления:

    remove :: Ord key => BSTree key value -> key -> BSTree key value
    remove Leaf _ = Leaf
    remove (Branch key value left right) k
        | k < key  = Branch key value (remove left k) right
        | k > key  = Branch key value left (remove right k)
        | k == key = if isLeaf right
                     then left
                     else Branch leftmostA leftmostB left right'
                         where
                           isLeaf Leaf = True
                           isLeaf _    = False
                           ((leftmostA, leftmostB), right') = deleteLeftmost right
                           deleteLeftmost (Branch key value Leaf right) = ((key, value), right)
                           deleteLeftmost (Branch key value left right) = (pair, Branch key value left' right)
                               where (pair, left') = deleteLeftmost left
    

    public void remove(T1 k) {
            Node<T1, T2> x = root, y = null;
            while (x != null) {
                    int cmp = k.compareTo(x.key);
                    if (cmp == 0) {
                            break;
                    } else {
                            y = x;
                            if (cmp < 0) {
                                    x = x.left;
                            } else {
                                    x = x.right;
                            }
                    }
            }
            if (x == null) {
                    return;
            }
            if (x.right == null) {
                    if (y == null) {
                            root = x.left;
                    } else {
                            if (x == y.left) {
                                    y.left = x.left;
                            } else {
                                    y.right = x.left;
                            }
                    }
            } else {
                    Node<T1, T2> leftMost = x.right;
                    y = null;
                    while (leftMost.left != null) {
                            y = leftMost;
                            leftMost = leftMost.left;
                    }
                    if (y != null) {
                            y.left = leftMost.right;
                    } else {
                            x.right = leftMost.right;
                    }
                    x.key = leftMost.key;
                    x.value = leftMost.value;
            }
    }
    


    На десерт, пара функций, которые я использовал для тестирования:

    fromList :: Ord key => [(key, value)] -> BSTree key value
    fromList = foldr (\(key, value) tree -> add tree key value) Leaf
     
    toList :: Ord key => BSTree key value -> [(key, value)]
    toList tree = toList' tree []
        where
          toList' Leaf list = list
          toList' (Branch key value left right) list = toList' left ((key, value):(toList' left list))
    


    Чем же все это полезно?



    У читателя возможно возникает вопрос, зачем нужны такие сложности, если можно просто хранить список пар [(ключ, значение)]. Ответ прост — операции с деревом работают быстрее. При реализации списком все функции требуют O(n) действий, где n — размер структуры. (Запись O(f(n)) грубо говоря означает «пропорционально f(n)», более корректное описание и подробности можно почитать тут). Операции с деревом же работают за O(h), где h — максимальная глубина дерева (глубина — расстояние от корня до вершины). В оптимальном случае, когда глубина всех листьев одинакова, в дереве будет n=2^h вершин. Значит, сложность операций в деревьях, близких к оптимуму будет O(log(n)). К сожалению, в худшем случае дерево может выродится и сложность операций будет как у списка, например в таком дереве (получится, если вставлять числа 1..n по порядку):

    Вырожденное дерево

    К счастью, существуют способы реализовать дерево так, чтобы оптимальная глубина дерева сохранялась при любой последовательности операций. Такие деревья называют сбалансированными. К ним например относятся красно-черные деревья, AVL-деревья, splay-деревья, и т.д.

    Анонс следующих серий



    В следующей статье я сделаю небольшой обзор различных сбалансированных деревьев, их плюсы и минусы. В следующих статьях я расскажу о каком-нибудь (возможно нескольких) более подробно и с реализацией. После этого я расскажу о реализации ropes и других возможных расширениях и применениях сбалансированных деревьев.

    Оставайтесь на связи!

    Полезные ссылки



    Исходники примеров целиком:

    на haskell

    на java

    Статья на википедии

    Интерактивный визуализатор операций с BST

    Также очень советую почитать книгу Кормен Т., Лейзерсон Ч., Ривест Р.: «Алгоритмы: построение и анализ», которая является прекрасным учебником по алгоритмам и структурам данных

    UPD: картинки восстановлены, спасибо Xfrid!

    Share post

    Comments 52

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

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

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

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

                                  Спасибо за статью, обязательно продолжайте.
                                    +2
                                    Хотел бы добавить ещё одну книжку к списку литературы Вирт, алгоритмы и структуры данных она хоть и старая, но фундаментальные вещи не меняются =)
                                      0
                                      Описано хорошо, думаю начинающим программистам будет полезно.

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

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

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


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

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

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

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

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

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

                                                        например

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

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

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

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

                                                                ?
                                                                  0
                                                                  Картинки к посту сгинули… :(
                                                                    0
                                                                    Нашел версию с рабочими картинками на archive.org. Он вроде заблокирован, но это не такая проблема.

                                                                  Only users with full accounts can post comments. Log in, please.