Двоичное дерево (структура данных)
Материал из Википедии — свободной энциклопедии
 |
Эту статью предлагается разделить на "Двоичное дерево" и "Двоичное дерево поиска". Возможно, она слишком велика или её содержимое не имеет логической связности и предлагается его разнести в "Двоичное дерево" и "Двоичное дерево поиска". Пояснение причин и обсуждение — на странице Википедия:К разделению. Дата постановки — 27 марта 2007. |
Двоичное дерево — абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (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 nil nil) (s nil nil) )
(y nil nil)
)
)
|
Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.
|
Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины 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. Эта функция обычно работает только 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(NlogN) операций. Если они уже отсортированы в возрастающем или убывающем порядке, то дерево становится несбалансированным (т.е. у него появляется много пустых веток). Тогда алгоритм требует O(N2) операций, и это худший возможный случай. Чтобы сбалансировать дерево следует использовать алгоритм пирамиды или красно-чëрное дерево.
Пример создания бинарного дерева и сортировки на языке 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();
}
}
