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

Двоичное дерево поиска — это структура данных двоичное дерево, в которой данные, привязанные к каждому узлу, представляют собой пару (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. Эта функция обычно работает только c парой (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 (N l o g N)$ операций. Если они уже отсортированы в возрастающем или убывающем порядке, то дерево становится несбалансированным (то есть у него появляется много пустых веток). Тогда алгоритм требует $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();
 }
}

Литература

Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 174-179. ISBN 0-201-74395-7
Томас Х. Кормен и др. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. ISBN 0-07-013151-1
Википедия


Алгоритмы сортировок и их реализации
	Главная