Бинарные деревья
Бинарное дерево - это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на бинарные поддеревья, т.е. у каждого узла (предка) может быть не более двух потомков - левый и правый. На каждый узел бинарного дерева имеется ровно одна ссылка.
Начальный же узел, как уже известно, называется корнем дерева.
Бинарные деревья
Бинарное дерево - это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на бинарные поддеревья, т.е. у каждого узла (предка) может быть не более двух потомков - левый и правый. На каждый узел бинарного дерева имеется ровно одна ссылка.
Начальный же узел, как уже известно, называется корнем дерева.
На рисунке приведен пример бинарного дерева (корень обычно изображается сверху, хотя изображение можно и перевернуть).
Такая структура данных организуется следующим образом:
или, соблюдая более привычную форму:
Если дерево организовано так, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно называется деревом поиска. Одинаковые ключи здесь не допускаются.
Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации.
В дереве поиска можно найти элемент по ключу, двигаясь от корня, и, переходя на левое или правое поддерево, в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна логарифму количества узлов - log2N. Время поиска по сравнению с линейной структурой сокращается с N до log2N.
Для так называемого сбалансированного дерева, в котором количество узлов справа и слева отличается не более чем на единицу, высота дерева как раз и равна двоичному логарифму количества узлов. Линейный список можно представить как вырожденное бинарное дерево, в котором каждый узел имеет не более одной ссылки. Для списка среднее время поиска равно ровно половине длины этого списка.
Дерево по своей организации является рекурсивной структурой данных, поскольку каждое его поддерево также является деревом. Действия с такими структурами изящнее всего описываются с помощью рекурсивных алгоритмов. Например, функцию обхода всех узлов дерева можно в общем виде описать так:
type way_around (дерево) {
way_around (левое поддерево);
посещение корня;
way_around (правое поддерево);
}
Можно обходить дерево и в другом порядке, например, сначала корень, потом поддеревья, но приведенная функция позволяет получить на выходе отсортированную последовательность ключей, поскольку сначала посещаются вершины с меньшими ключами, расположенные в левом поддереве, а потом вершины правого поддерева с большими ключами.
На приведенном ниже рисунке это Путь «1».
Результат обхода дерева, изображенного на рисунке:
Путь «1»: 1→ 6→ 8→ 10→ 20→ 21→ 25→ 30
Если в функции обхода первое обращение идет к правому поддереву, результат обхода будет таким:
Путь «2»: 30→ 25→ 21→ 20→ 10→ 8→ 6→ 1
Таким образом, деревья поиска можно применять для сортировки значений (при обходе дерева узлы не удаляются).
Рассмотрим основные алгоритмы работы с бинарным деревом
Необходимо уметь:
- построить (создать) дерево;
- вставить новый элемент;
- обойти все элементы дерева, например, для просмотра или чтобы произвести некоторую операцию;
- выполнить поиск элемента с указанным значением в узле;
- удалить заданный элемент.
Обычно бинарное дерево строится сразу упорядоченным, т.е. узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына - большее.
1. Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (Y) со значением нового элемента (New). Если New<Y, то идем по левой ветви, в противном случае - по правой ветви. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.
2. При удалении узла из дерева возможны три ситуации:
1. Удаляемый узел является листом - просто удаляем ссылку на него;
Удаление листа с ключом key:
2. Из удаляемого узла выходит только одна ветвь;
Удаление узла имеющего одного потомка:
3. Удаление узла, имеющего двух потомков, значительно сложнее. Если key – исключаемый узел, то его следует заменить узлом w, который содержит либо наибольший ключ в левом поддереве, либо наименьший ключ в правом поддереве. Такой узел w является либо листом, либо самым правым узлом поддерева key, у которого имеется только левый потомок:
Таким образом, если из удаляемого узла выходит две ветви (в данном случае на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева).
3. Задача обхода дерева.
Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.
1) Обход слева направо: Left-Root-Right (сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево).
2) Обход сверху вниз: Root-Left-Right (посещаем корень до поддеревьев).
3) Обход снизу вверх: Left-Right-Root (посещаем корень после поддеревьев).
Варианты заданий
Программа должна сформировать дерево из целых чисел,
- выполнить просмотр,
- добавление,
- удаление по ключу
- осуществлять сортировку или по возрастанию или по убыванию
- осуществлять обходы Left-Root-Right; Root-Left-Right; Left-Right-Root;
- и освобождение памяти при выходе из программы.
Контрольные вопросы
- Как сформировать дерево из целых чисел,
- Как осуществить добавление,
- Как осуществить удаление по ключу
- Как осуществлять сортировку или по возрастанию или по убыванию
- Как осуществлять обходы Left-Root-Right; Root-Left-Right; Left-Right-Root;