Представление деревьев в виде бинарных деревьев.
Основными различиями между деревьями и бинарными деревьями являются:
дерево никогда не бывает пусто, т.е. дерево имеет по меньшей мере один узел, и каждый узел дерева может иметь 0,1,2,3,… сыновей.
Бинарное дерево может быть пусто, и каждый из его узлов может иметь 0,1 или 2 сына; делается различие между «правым » и «левым» сыном даже в том случае, когда узел имеет лишь одного сына.
Любое дерево может быть единственным образом представлено в виде бинарного дерева.
Порядок преобразования будет состоять из двух этапов:
На первом для каждой вершины уничтожаются все исходящие из нее ребра, кроме самого левого, вместо них рисуются ребра, соединяющие вершину с другой вершиной, расположенной справа от нее на том же уровне. После этого для каждой вершины осуществляется выбор левого и правого сыновей по правилу:
Левый сын – это вершина, расположенная непосредственно ниже данной, а правый сын – вершина, расположенная непосредственно справа от данной на одной на одном уровне.
Лес – это упорядоченное множество, состоящее из некоторого, быть может, равного нулю, числа деревьев.
Поддеревья, исходящие из любого узла дерева, образуют лес.
Всякий лес может естественным образом представить в виде бинарного дерева. Рассмотрим следующий лес из двух деревьев:
Затем, повернув на 45°, получаем бинарное дерево
Выполненное преобразование называется естественным соответствием между лесами и бинарными деревьями. В частности, оно дает соответствие между деревьями и такими бинарными деревьями, которые имеют корень, но не имеют правого поддерева. Можно также несколько видоизменить способ соответствия, приняв, что голова списка бинарного дерева соответствует корню дерева; при этом получаем взаимно однозначное соответствие между деревьями и бинарными деревьями.
Пусть F=(T1,T2,T3. Tn) –лес деревьев. Бинарное дерево В(F), соответствующееF, можно строго определить следующим образом:
если n=0, тоB(F) пусто
если n>0, то корнем B(F) является корень Т1; левым поддеревом дереваB(F) являетсяB(T11,T12,T13,…,T1m), гдеT11,T12,T13,…,T1m – поддеревья корняT1; правым же поддеревом дереваB(F) являетсяB(T2,T3,…,Tn).
Иногда для удобства будем рисовать диаграмму бинарного дерева, не поворачивая ее на 45°. Прошитое бинарное дерево будет иметь вид
Правые связи-нити идут от самого правого сына к отцу семьи. Для левых же связей-нитей естественной интерпретацией их хода нет, ввиду отсутствия симметрии между левым и правым.
Исходя из указанного естественного соответствия идеи прохождения можно применить к лесам. Известные три порядка прохождения принимают вид:
прямой порядок 1) попасть в корень первого дерева; 2) пройти поддеревья первого дерева(в прямом порядке); 3) пройти оставшиеся деревья (в прямом порядке) симметричный порядок 1)пройти поддеревья первого дерева (в симметричном порядке); 2) попасть в корень первого дерева; 3) пройти оставшиеся деревья (в симметричном порядке);
концевой порядок 1)пройти поддеревья первого дерева (в концевом порядке); 2) пройти оставшиеся деревья (в концевом порядке); 3) попасть в корень первого дерева.
Чтобы понять значение этих трех методов прохождения, рассмотрим следующую запись дерева с помощью вложенных скобок: (А(В,С(К),)D(E(H),F(J),G)).
Эта запись соответствует рассмотренному лесу: представляем дерево, записывая сначала информацию, заложенную в его корне, а затем представляем его поддеревья. Т.о. представлением непустого леса служит заключенный в скобки список представлений его деревьев, разделяемых запятыми. Если лес проходится в прямом порядке, то попадаем в последовательность ABCKDEHFJG. Прямой порядок есть естественный способ пересечения узлов дерева: сначала мы записываем корень, а затем потомков.
Симметричный порядок для узлов леса таков BKCAHEJFGD.
Интересно заметить, что прямой порядок есть освященное веками понятие, которое можно выразительно назвать династическим порядком. После смерти короля, герцога, графа и т.д. его титул переходит к его первому сыну, а затем к потомкам первого сына, и если же таковые умирают, то титул таким же образом переходит к другим сыновьям этой семьи. (В Англии титул может переходить и к дочерям, но их ставят после всех сыновей)
РЕАЛИЗАЦИЯ БИНАРНОГО ДЕРЕВА
При реализации дерева с помощью динамических переменных каждый элемент дерева, помимо информационной части, содержит два указателя: на левое и правое поддеревья этого элемента. Переменная ссылочного типа fRoot указывает на корневой узел дерева. Если какой-либо узел дерева не имеет левого или правого поддерева, то соответствующий указатель этого узла содержит значение ш1.
Описание класса t Binary Tree: type
tValue = Char; //тип элемента дерева — символьный pltem = A tltem; //тип указателя на элемент дерева tltem = record //узел дерева
Value: tValue; //содержательная часть узла дерева
Left, Right: pltem; //указатели на левое и правое поддеревья узла end; //tltem
tBinaryTree=class //класс — бинарное дерево
fRoot: pltem; //поле — указатель на корень
fSize: Word; //поле — число узлов дерева
property Root: pltem read fRoot write fRoot; //указатель на корень property Size: Word read fSize write fSize; //число узлов дерева
//Построение дерева из п узлов из файла f procedure Build(n: Word;var f: Text);
// Обход дерева сверху вниз с выводом результатов в файл f procedure UpDownRevision(var f: Text);
// Обход дерева слева направо с выводом результатов в файл f procedure LeftRightRevision(var f: Text);
// Обход дерева снизу вверх с выводом результатов в файл f procedure DownUpRevision(var f: Text);
//Включение поддерева SubTree в левую ветвь узла Addr procedure AddLeft(Addr: pltem; SubTree: tBinaryTree);
//Включение поддерева SubTree в правую ветвь узла Addr procedure AddRight(Addr: pltem; SubTree: tBinaryTree);
//Исключение поддерева из левой ветви узла с адресом Addr function DeleteLeft(Addr: pltem): tBinaryTree;
//Исключение поддерева из правой ветви узла с адресом Addr function DeleteRight(Addr: pltem): tBinaryTree;
function Addr(v: tValue): pltem;
Value(Addr: pltem): tValue; LeftSon(Addr: pltem): pltem; RightSon(Addr: pltem): pltem; Father(Addr: pltem): pltem; Brother(Addr: pltem): pltem; lsLeft(Addr: pltem): Boolean; lsRight(Addr: pltem): Boolean;
// адрес узла со значением V // значение узла Аддг //левый сын узла Айдг // правый сын Адйг // отец Аййг // брат Аббг
//Аддг — левый сын узла? //Аддг- правый сын узла?
procedure WriteTo(var f: Text); // вывод дерева в файл f
// Возвращение числа узлов поддерева с корнем Addr function NodesQuantity(var Addr:Pltem): Word;
function Empty: Boolean; //возвращение True, если дерево пусто procedure Clear; //удаление всех узлов дерева
constructor Create; //конструктор дерева
destructor Destroy; override; //деструктор дерева end; //tBinaryTree
H Бинарные деревья поиска в черновиках Recovery Mode
Эта статья посвящена бинарным деревьям поиска. Недавно делал статью про сжатие данных методом Хаффмана. Там я не очень обращал внимание на бинарные деревья, ибо методы поиска, вставки, удаления не были актуальны. Теперь решил написать статью именно про деревья. Пожалуй, начнем.
Дерево — структура данных, состоящая из узлов, соединенных ребрами. Можно сказать, что дерево — частный случай графа. Вот пример дерева:
Это не бинарное дерево поиска! Все под кат!
Терминология
Корень
Корень дерева — это самый верхний его узел. В примере — это узел A. В дереве от корня к любому другому узлу может вести только один путь!
Родители/потомки
Все узлы, кроме корневого, имеют ровно одно ребро, ведущее вверх к другому узлу. Узел, расположенный выше текущего, называется родителем этого узла. Узел, расположенный ниже текущего, и соединенный с ним называется потомком этого узла. Давайте на примере. Возьмем узел B, тогда его родителем будет узел A, а потомками — узлы D, E и F.
Узел, у которого нет потомков, будет называться листом дерева. В примере листьями будут являться узлы D, E, F, G, I, J, K.
Это основная терминология. Другие понятия будут разобраны далее. Итак, бинарное дерево — дерево, в котором каждый узел будет иметь не более двух потомков. Как вы догадались, дерево из примера не будет являться бинарным, ибо узлы B и H имеют более двух потомков. Вот пример бинарного дерева:
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.
Представление дерева
По мере продвижения я буду приводить некоторые(возможно, неполные) куски кода, для того, чтобы улучшить ваше понимание. Полный код будет в конце статьи.
Дерево состоит из узлов. Структура узла:
Каждый узел имеет двух потомков(вполне возможно, потомки leftChild и/или rightChild будут содержать значение null). Вы, наверное, поняли, что в данном случае число data — ключ узла.
Ключ и информация в узле могут не совпадать! Например, вы могли сделать так:
Здесь myData хранит информацию узла дерева. Важно понимать, что узел дерева может хранить любую информацию.
С узлом разобрались, теперь поговорим о проблемах насущных о деревьях. Здесь и далее под словом «дерево» буду подразумевать понятие бинарного дерева поиска. Структура бинарного дерева:
Как поле класса нам понадобится только корень дерева, ибо от корня с помощью методов getLeftChild() и getRightChild() можно добраться до любого узла дерева.
Алгоритмы в дереве
Поиск
Допустим, у вас есть построенное дерево. Как найти элемент с ключом key? Нужно последовательно двигаться от корня вниз по дереву и сравнивать значение key с ключом очередного узла: если key меньше, чем ключ очередного узла, то перейти к левому потомку узла, если больше — к правому, если ключи равны — искомый узел найден! Соответствующий код:
Если current становится равным null, значит, перебор достиг конца дерева(на концептуальном уровне вы находитесь в несуществующем месте дерева — потомке листа).
Рассмотрим эффективность алгоритма поиска на сбалансированном дереве(дереве, в котором узлы распределены более-менее равномерно). Тогда эффективность поиска будет O(log(n)), причем логарифм по основанию 2. Смотрите: если в сбалансированном дереве n элементов, то это значит, что будет log(n) по основанию 2 уровней дерева. А в поиске, за один шаг цикла, вы спускаетесь на один уровень.
Вставка
Если вы уловили суть поиска, то понять вставку не составит вам труда. Надо просто спуститься до листа дерева(по правилам спуска, описанным в поиске) и стать его потомком — левым, или правым, в зависимости от ключа. Реализация:
В данном случае надо, помимо текущего узла, хранить информацию о родителе текущего узла. Когда current станет равным null, в переменной parent будет лежать нужный нам лист.
Эффективность вставки, очевидно, будет такой же как и у поиска — O(log(n)).
Удаление
Удаление — самая сложная операция, которую надо будет провести с деревом. Понятно, что сначала надо будет найти элемент, который мы собираемся удалять. Но что потом? Если просто присвоить его ссылке значение null, то мы потерям информацию о поддереве, корнем которого является этот узел. Методы удаления дерева разделяют на три случая.
Первый случай. Удаляемый узел не имеет потомков
Если удаляемый узел не имеет потомков, то это значит, что он является листом. Следовательно, можно просто полям leftChild или rightChild его родителя присвоить значение null. В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, переменная isLeftChild будет принимать значение true или false соответственно.
Второй случай. Удаляемый узел имеет одного потомка
Этот случай тоже не очень сложный. Вернемся к нашему примеру. Допустим, надо удалить элемент с ключом 14. Согласитесь, что так как он — правый потомок узла с ключом 10, то любой его потомок(в данном случае правый) будет иметь ключ, больший 10, поэтому можно легко его «вырезать» из дерева, а родителя соединить напрямую с потомком удаляемого узла, т.е. узел с ключом 10 соединить с узлом 13. Аналогичной была бы ситуация, если бы надо было удалить узел, который является левым потомком своего родителя. Подумайте об этом сами — точная аналогия.
Третий случай. Узел имеет двух потомков
Наиболее сложный случай. Разберем на новом примере.
Поиск преемника
Допустим, надо удалить узел с ключом 25. Кого поставим на его место? Кто-то из его последователей(потомков или потомков потомков) должен стать преемником(тот, кто займет место удаляемого узла).
Как понять, кто должен стать преемником? Интуитивно понятно, что это узел в дереве, ключ которого — следующий по величине от удаляемого узла. Алгоритм заключается в следующем. Надо перейти к его правому потомку(всегда к правому, ибо уже говорилось, что ключ преемника больше ключа удаляемого узла), а затем пройтись по цепочке левых потомков этого правого потомка. В примере мы должны перейти к узлу с ключом 35, а затем пройтись до листа вниз по цепочке его левых потомков — в данном случае, эта цепочка состоит только из узла с ключом 30. Строго говоря, мы ищем наименьший узел в наборе узлов, больших искомого узла.
Теперь можем закончить метод delete:
Полный код метода delete:
Сложность может быть аппроксимирована к O(log(n)).
Поиск максимума/минимума в дереве
Очевидно, как найти минимальное/максимальное значение в дереве — надо последовательно переходить по цепочке левых/правых элементов дерева соответственно; когда доберетесь до листа, он и будет минимальным/максимальным элементом.
Симметричный обход
Обход — посещение каждого узла дерева с целью сделать с ним какую-то функцию.
Алгоритм рекурсивного симметричного обхода:
- Сделать действие с левым потомком
- Сделать действие с собой
- Сделать действие с правым потомком
Заключение
Наконец-то! Если я что-то недообъяснил или есть какие-либо замечания, то жду в комментариях. Как обещал, привожу полный код.
Программирование. Деревья Pascal-Паскаль
Деревья представляют собой иерархическую структуру некой совокупности элементов. Деревья – это одна из наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами, их используют при анализе электрических цепей, математических формул, для организации информации в системах управления базами данных и для представления синтаксических структур в компиляторах.
Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений («родительских»), образующих иерархическую структуру узлов. Вообще говоря, древовидная структура задает для элементов дерева (узлов) отношение «ветвления», которое во многом напоминает строение обычного дерева.
Формально дерево ( tree ) определяется как конечное множество T одного или более узлов со следующими свойствами:
- Существует один выделенный узел, а именно – корень ( root ) данного дерева;
- Остальные узлы (за исключением корня) распределены среди m ?0 непересекающихся множеств T 1 , T 2 , …. T m , и каждое из этих множеств, в свою очередь, является деревом; деревья T 1 , T 2 , . T m называются поддеревьями данного корня.
Как видите, это определение является рекурсивным: дерево определено на основе понятия дерево. Рекурсивный характер деревьев можно наблюдать и в природе, например, почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья) и т.д. Можно привести еще одно формальное определение дерева:
- Один узел является деревом. Этот же узел также является корнем этого дерева.
- Пусть n – это узел, а T 1 , T 2 , . T m – деревья с корнями n 1 , n 2 , … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1 , n 2 , … n m . В этом дереве n будет корнем, а T 1 , T 2 , . T m – поддеревьями этого корня. Узлы n 1 , n 2 , … n m называются сыновьями узла n .
Из приведенных выше определений следует, что каждый узел дерева является корнем некоторого поддерева данного дерева. Количество поддеревьев узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом или листом. Неконцевой узел называется узлом ветвления. Каждый узел имеет уровень, который определяется следующим образом: уровень корня дерева равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева, содержащего данный узел.
Рассмотрим эти понятия на примере дерева с семью узлами (см. рисунок). Узлы часто изображаются буквами, они так же, как и элементы списков могут быть элементами любого типа.
Узел A является корнем, который имеет два поддерева < B >и < C , D , E , F , G >. Корнем дерева < C , D , E , F , G >является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева < D >, < E >и < F , G >, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .
Путем из узла n 1 в узел n k называется последовательность узлов n 1 , n 2 , … n k , где для всех i , 1? i ? k , узел n i является родителем узла n i +1 . Длиной пути называется число, на единицу меньшее числа узлов, составляющего этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. Например, на рисунке путем длины 2 будет путь от узла A к узлу F или от узла C к узлу G .
Если существует путь из узла a в узел b , то в этом случае узел a называется предком узла b , а узел b – потомком узла a . Отметим, что любой узел одновременно является предком и потомком самого себя. Например, на рисунке предками узла G будут сам узел G и узлы F , C и A . Потомками узла C будут являться сам узел C и узлы D , T , F , G . В дереве только корень не имеет предков, а листья не имеют потомков.
Предок узла, имеющий уровень на единицу меньше уровня самого узла, называется родителем. Потомки узла, уровень которых на единицу больше относительно самого узла, называются сыновьями или детьми. Узлы, являющиеся сыновьями одного родителя, принято называть братьями.
Высотой узла дерева называется длина самого длинного пути от этого узла до какого-либо листа. Глубина узла определяется как длина пути от корня до этого узла.
Лес – это множество (обычно упорядоченное), содержащее несколько непересекающихся деревьев. Узлы дерева при условии исключения корня образуют лес.
Порядок узлов
Если в определении дерева имеет значение порядок поддеревьев T 1 , T 2 , . T m , то дерево является упорядоченным.
Сыновья узла обычно упорядочиваются слева направо. Поэтому деревья, приведенные на рисунке, являются различными.
Если порядок сыновей игнорируется, то такое дерево называется неупорядоченным. Далее будем неявно предполагать, что все рассматриваемые деревья являются упорядоченными, если явно не указано обратное.
Обходы дерева
Существует несколько способов обхода всех узлов дерева. Три наиболее часто используемых способа обхода называются прямой, обратный и симметричный обходы. Все три способа можно рекурсивно определить следующим образом:
- Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
- Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
- Пусть дерево T имеет корень n и поддеревья T 1 , T 2 , . T m , как показано на рисунке
Тогда для различных способов обхода имеем следующее:
- Прямой обход . Сначала посещается корень n , затем в прямом порядке узлы поддерева T 1 , далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m .
- Обратный обход . Сначала посещаются в обратном порядке все узлы поддерева T 1 , затем в обратном порядке узлы поддеревьев T 2 … T m , последним посещается корень n .
- Симметричный обход . Сначала в симметричном порядке посещаются все узлы поддерева T 1 , затем корень n , после чего в симметричном порядке все узлы поддеревьев T 2 … T m .
Рассмотрим пример всех способов обхода дерева, изображенного на рисунке:
Порядок узлов данного дерева в случае прямого обхода будет следующим:
1 2 3 5 8 9 6 10 4 7.
Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1.
При симметричном обходе мы получим следующую последовательность узлов:
2 1 8 5 9 3 10 6 7 4.
Помеченные деревья и деревья выражений
Часто бывает полезным сопоставить каждому узлу дерева метку или значение. Дерево, у которого узлам сопоставлены метки, называется помеченным деревом. Метка узла – это значение, которое «хранится» в узле. Полезна следующая аналогия: дерево – список, узел – позиция, метка – элемент.
Рассмотрим пример дерева с метками, представляющее арифметическое выражение ( a + b )*( a + c ), где n 1 , n 2 , …, n 7 – имена узлов, а метки проставлены рядом с соответствующими узлами. Правила соответствия меток деревьев элементам выражений следующие:
- Метка каждого листа соответствует операнду и содержит его значение;
- Метка каждого внутреннего (родительского) узла соответствует оператору.
Часто при обходе деревьев составляется список не имен узлов, а их меток. В случае дерева выражений при прямом обходе получим известную префиксную форму записи выражения, где оператор предшествует обоим операндам. В нашем примере мы получим префиксное выражение вида: *+ ab + ac .
Обратный обход меток дерева дает постфиксное представление выражения (польскую запись). Обратный обход нашего дерева даст нам следующую запись выражения: ab + ac +*.
Следует учесть, что префиксная и постфиксная запись выражения не требует скобок.
При симметричном обходе мы получим обычную инфиксную запись выражения: a + b * a + c . Правда для инфиксной записи выражений характерно заключение в скобки: ( a + b )*( a + c ).
Реализация деревьев
Пусть дерево T имеет узлы 1, 2, …., n . Возможно, самым простым представлением дерева T будет линейный массив A , где каждый элемент A [ i ] содержит номер родительского узла (является курсором на родителя). Поскольку корень дерева не имеет родителя, то его курсор будет равен 0.
Для приведенного на рисунке дерева построим линейный массив по следующему правилу: A [ i ]= j , если узел j является родителем узла i , A [ i ]=0, если узел i является корнем. Тогда массив будет выглядеть следующим образом:
Другой важный и полезный способ представления деревьев состоит в формировании для каждого узла списка его сыновей. Рассмотрим этот способ для приведенного выше примера.
Двоичные деревья
Двоичное или бинарное дерево – это наиболее важный тип деревьев. Каждый узел бинарного дерева имеет не более двух поддеревьев, причем в случае только одного поддерева следует различать левое или правое. Строго говоря, бинарное дерево – это конечное множество узлов, которое является либо пустым, либо состоит из корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня. Тот факт, что каждый сын любого узла определен как левый или как правый сын, существенно отличает двоичное дерево от обычного упорядоченного ориентированного дерева.
Если мы примем соглашение, что на схемах двоичных деревьев левый сын всегда соединяется с родителем линей, направленной влево и вниз от родителя, а правый сын – линией, направленной вправо и вниз, тогда деревья, изображенные на рисунке а) и б) ниже, – это различные деревья, хотя они оба похожи на обычное дерево (рис. в)).
Двоичные деревья нельзя непосредственно сопоставить с обычным деревом.
Обход двоичных деревьев в прямом и обратном порядке в точности соответствует таким же обходам обычных деревьев. При симметричном обходе двоичного дерева с корнем n левым поддеревом T 1 и правым поддеревом T 2 сначала проходится поддерево T 1 , затем корень n и далее поддерево T 2 .
Представление двоичных деревьев
Бинарное дерево можно представить в виде динамической структуры данных, состоящей из узлов, каждый из которых содержит кроме данных не более двух ссылок на правое и левое бинарное дерево. На каждый узел имеется одна ссылка. Начальный узел называется корнем.
По аналогии с элементами списков, узлы дерева удобно представить в виде записей, хранящих информацию и два указателя:
Пример фрагмента программы дерева
Изобразим схематично пример дерева, организованного в виде динамической структуры данных:
Дерево поиска
Обратите внимание на рисунок, приведенный выше. Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.
С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.
Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:
- Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
— если ключи совпадают, поиск завершен;
— если ключ в корне больше искомого, выполнить поиск в левом поддереве;
— если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
- Если дерево пусто, то искомый элемент не найден.
Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность: 1 6 8 10 20 21 25 30.
Можно организовать «зеркально симметричный» обход, начиная с правого поддерева, тогда получим упорядоченную по убыванию последовательность: 30 25 20 10 8 6 1.
Таким образом, деревья поиска можно применять для сортировки значений.
Операции с двоичными деревьями
Для работы с двоичными деревьями важно уметь выполнять следующие операции:
- Поиск по дереву;
- Обход дерева;
- Включение узла в дерево;
- Удаление узла из дерева.
1. Алгоритм поиска по дереву мы рассмотрели выше. Функция поиска :
Пример функции поиска
2. Мы рассмотрели несколько способов обхода дерева. Наибольший интерес для двоичного дерева поиска представляет симметричный обход, т.к. он дает нам упорядоченную последовательность ключей. Логично реализовать обход дерева в виде рекурсивной процедуры.
Пример обхода дерева с помощью рекурсии
3. Вставка узла в двоичное дерево поиска не представляет сложности. Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.
Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.
Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя.
Сложнее всего случай, когда у удаляемого узла есть оба потомка.
Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу. Рассмотрите этот случай на рисунке, должно стать понятней.
В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.
Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.
Рассмотрим реализацию алгоритма удаления.
Пример программы удаления узла из дерева
В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( <6>) .
В операторах <7>— <9>определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева (<7>).
Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева (<8>).
В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву (<9>).
В этой функции первым делом проверяется особый случай, описанный выше (<1>). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл (<2>), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).
В операторе <3>к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла (<5>), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый (<4>), поскольку этот узел перейдет на новое место.
Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень (<10>), иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла (<11>).
После того как узел удален из дерева, освобождается занимаемая им память (<12>).