Бинарное дерево

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

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

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

дерево :: (данные ВКЛ ВКЛ) .
дерево :: ПУСТО .

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

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

 (m 
    (e 
        (c 
            (a ПУСТО ПУСТО)
            ПУСТО
        )
        (g 
            ПУСТО
            (k ПУСТО ПУСТО)
        )
     )
     (s
        (p (o ПУСТО ПУСТО) (s ПУСТО ПУСТО) )
        (y ПУСТО ПУСТО)
     )
 )

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

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

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

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

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

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

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

  • ИСКАТЬ(K) — поиск узла, в котором хранится пара (ключ, значение) с ключ = K.
  • ДОБАВИТЬ(K,V) — добавление в дерево пары (ключ, значение) = (K, V).
  • УДАЛИТЬ(K) — удаление узла, в котором хранится пара (ключ, значение) с ключ = K.

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

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

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (ключ, значение) и поддерживающая три операции: ИСКАТЬ, ДОБАВИТЬ, УДАЛИТЬ.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: ИНФИКСНЫЙ_ОБХОД, ПРЕФИКСНЫЙ_ОБХОД, ПОСТФИКСНЫЙ_ОБХОД. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (ИСКАТЬ)Править

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

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

Алгоритм:

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

Добавление элемента (ДОБАВИТЬ)Править

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

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

Алгоритм:

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

Удаление узла (УДАЛИТЬ)Править

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

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

Алгоритм:

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

Обход дерева (ОБХОД)Править

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

Первая операция — ИНФИКСНЫЙ_ОБХОД — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова. Эта функция обычно работает только c парой (K,V), хранящейся в узле. Операция ИНФИКСНЫЙ_ОБХОД реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

  • ИНФИКСНЫЙ_ОБХОД ( функция_обратного_вызова ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
  • ПРЕФИКСНЫЙ_ОБХОД ( функция_обратного_вызова ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
  • ПОСТФИКСНЫЙ_ОБХОД ( функция_обратного_вызова ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).

ИНФИКСНЫЙ_ОБХОД:

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

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

Алгоритм:

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

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции ИНФИКСНЫЙ_ОБХОД будут выведены все пары в порядке возрастания ключей. Если же использовать ПРЕФИКСНЫЙ_ОБХОД, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

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

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

Если элементы массива различны и расположены в случайном порядке, а длина массива N N , алгоритм требует в среднем O ( N l o g N ) O(N log N) операций. Если они уже отсортированы в возрастающем или убывающем порядке, то дерево становится несбалансированным (т.е. у него появляется много пустых веток). Тогда алгоритм требует O ( N 2 ) O(N^2) операций, и это худший возможный случай. Чтобы сбалансировать дерево следует использовать алгоритм пирамиды или красно-чëрное дерево.

Пример создания бинарного дерева и сортировкиПравить

На языке Java:

// Скомпилируйте и введите java TreeSort

class Tree {
   public Tree big;            // правое и левое поддеревья и ключ
   public Tree small;
   public int key;

   public Tree(int k) {        // конструктор с инициализацией ключа
      key = k;
   }

/*  add (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключём корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   public void add( Tree aTree) {
     if ( aTree.key >= key )
        if ( big != null ) big.add( aTree );
        else big = aTree;
     else
        if ( small != null ) small.add( aTree );
        else small = aTree;
   }

/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   public void traverse() {
      if ( small != null) small.traverse();
      System.out.println( " " + key );
      if ( big != null ) big.traverse();
   }
}
public class TreeSort {
  public static void main(String args[]) {
     Tree myTree;
     myTree = new Tree( 7 );       // создать дерево (с ключом)
     myTree.add( new Tree( 5 ) );  // присоединять поддеревья
     myTree.add( new Tree( 9 ) );
     myTree.traverse();
  }
}

См. такжеПравить

ЛитератураПравить