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

Материал из Википедии — свободной энциклопедии

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

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

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

Двоичное дерево поиска является одной из возможных реализаций ассоциативного массива.

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

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

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

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

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

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

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

[править] Поиск элемента (FIND)

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

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

Алгоритм:

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

[править] Добавление элемента (INSERT)

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

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

Алгоритм:

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

[править] Удаление узла (REMOVE)

Дано: дерево Т с корнем 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 (который, в принципе, может быть равен null).
      • освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n).

[править] Обход дерева (TRAVERSE)

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

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

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

INFIX_TRAVERSE:

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

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

Алгоритм:

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

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

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

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

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

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

// Скомпилируйте и введите java TreeSort
 
class Tree {
   public Tree left;            // левое и правое поддеревья и ключ
   public Tree right;
   public int key;
 
   public Tree(int k) {        // конструктор с инициализацией ключа
      key = k;
   }
 
/*  insert (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   public void insert( Tree aTree) {
     if ( aTree.key < key )
        if ( left != null ) left.insert( aTree );
        else left = aTree;
     else
        if ( right != null ) right.insert( aTree );
        else right = aTree;
   }
 
/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   public void traverse(TreeVisitor visitor) {
      if ( left != null) 
            left.traverse( visitor );
 
      visitor.visit(this);
 
      if ( right != null ) 
            right.traverse( visitor );
   }
}
 
interface TreeVisitor {
  public void visit(Tree node);
};
 
 
class KeyPrinter  implements TreeVisitor {
  public void visit(Tree node) {
      System.out.println( " " + node.key );
  }
};
 
 
public class TreeSort {
  public static void main(String args[]) {
     Tree myTree;
     myTree = new Tree( 7 );       // создать дерево (с ключом)
     myTree.insert( new Tree( 5 ) );  // присоединять поддеревья
     myTree.insert( new Tree( 9 ) );
     myTree.traverse(new KeyPrinter());
  }
}

[править] См. также

• Ассоциативный массив
• Декартово дерево

Сбалансированные деревья:

• АВЛ-дерево
• Красно-чёрное дерево