Двоичное дерево (структура данных)

Двоичное дерево — абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data — некоторые данные привязанные к узлу, l, r — ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r — правым.

Содержание

Рекурсивное определение двоичного дерева

Существует следующее рекурсивное определение двоичного дерева (см. EBNF):

tree :: (data tree tree) .
tree :: nil .

Эта определение означает, что двоичное дерево состоит из данных и двух поддеревьев, либо является пустым.

Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:

 (m 
    (e 
        (c 
            (a nil nil)
            nil
        )
        (g 
            nil
            (k nil nil)
        )
     )
     (s
        (p (o nill nil) (s nil nil) )
        (y nil nil)
     )
 )

Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, l, r) есть два ребёнка (левый и правый) l и r и, соответственно, два поддерева (левое и правое) с корнями l и r.


Двоичное дерево лежит в основе многих полезных структур данных, а именно:

Двоичное дерево поиска

Двоичное дерево поиска — это структура данных двоичное дерево, в котором данные , привязанные к каждому узлу представляют собой пару (key, value) (ключ и значение) , причём на ключах определена операция сравнения "меньше", и для всех узлов дерева выполнено свойство, называемое свойством дерева поиска:

у всех узлов левого поддерева произвольного узла n значение ключей меньше, нежели значения ключа узла n,
у всех узлов правого поддерева произвольного узла n значение ключей не меньше, нежели значения ключа узла n.

Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

  • FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
  • ADD(K,V) — добавление в дерево пары (key, value) = (K, V).
  • DEL(K) — удаление узла, в котором хранится пара (key, value) с key = K.

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

  • «Телефонная книжка» — хранилище записей (имя человека, его телефо) с операциями поиска и удаление записей по имени человека, и операцией добавления новой записи
  • Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.
  • Namespace — хранилище имен переменных с их значениями, возникающее в трансляторах языков программирования.

По сути, двоичное дерево поиска — это одни из структур данных, способная хранить таблицу пар (key, value), и поддерживающее три операции FIND, ADD, DEL.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева — INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключём K в дереве Т, и если да, то вернуть ссылку этот узел.

Алгоритм:

  • Если дерево пусто, сообщить, что узел не найден, и остановиться.
  • Иначе сравнить K со значением ключа корневого узла X.
    • Если K=X, выдать ссылку на этот узел и остановиться.
    • Если K>X, рекурсивно искать ключ K в правом поддереве Т.
    • Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента (ADD)

Дано: дерево Т и пара (K,V).

Задача: добавить пару (K, V) в дерево Т.

Алгоритм:

  • Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), nil, nil) и остановиться.
  • Иначе сравнить K с ключём корневого узла X.
    • Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
    • Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.


Удаление узла (DEL)

Дано: дерево Т с корнем n и ключём K.

Задача: удалить из дерева Т узел с ключём K (если такой есть).

Алгоритм:

  • Если дерево T пусто, остановиться
  • Иначе сравнить K со ключём X корневого узла n.
    • Если K>X, рекурсивно удалить K из правого поддерева Т.
    • Если K<X, рекурсивно удалить K из левого поддерева Т.
    • Если K=X, то неоходимо рассмотреть два случая.
      • Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения и освобождаем память, занимаемую узлом m.
      • Если оба ребёнка присутствуют, то
        • найдём узел m, являющийся самым левым узлом правого поддерева;
        • скопируем значения полей (key, value) узла m в соответствующие поля узла n.
        • у родителя узла m заменим ссылку на узел m (он может быть как левым, так и правым ребёнком своего родителя) ссылкой на правого ребёнка узла m (который, в принципе, может быть равен nil).
        • освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n).

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию call_back_function. Эта функция обычно работает только к парой (K,V), хранящеся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным оьразом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

  • INFIX_TRAVERSE ( call_back_function ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
  • PREFIX_TRAVERSE ( call_back_function ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
  • POSTFIX_TRAVERSE ( call_back_function ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).


INFIX_TRAVERSE:

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

  • Если дерево пусто, остановиться.
  • Иначе
    • Рекурсивно обойти правое поддерево Т.
    • Применить функцию f к корневому узлу.
    • Рекурсивно обойти левое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

Сортировка с помощью двоичного дерева поиска

Бинарное дерево поиска можно использовать для сортировки. Для этого берётся пустое дерево, к нему добавляют все элементы массива, а затем, используя алгоритм "Обход дерева", записывают элементы дерева в массив в возрастающем порядке.

Если элементы массива различны и расположены в случайном порядке, а длина массива N, алгоритм требует в среднем O(NlogN) операций. Если они уже отсортированы в возрастающем или убывающем порядке, алгоритм требует O(N2) операций, и это худший возможный случай.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home