Древовидной структурой данных называется конечное множество элементов-узлов, между которыми существуют отношения – связь исходного и порожденного.

Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t – это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.

Если узел у находится непосредственно под узлом х, то узел у называется непосредственным потомком узла х, а х – непосредственным предком узла у, т. е., если узел х находится на i-ом уровне, то соответственно узел у находится на (i + 1) – ом уровне.

Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева – его корень.

Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.

Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.

Если пройти от корня дерева к некоторому конкретному узлу, то количество ветвей дерева, которое при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.

Частным случаем древовидных структур являются бинарные деревья. Это деревья, в которых каждый потомок имеет не более двух потомков, называемых левым и правым поддеревьями. Таким образом, бинарное дерево – это древовидная структура, степень которой равна двум.

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

Дерево, степень которого больше двух, называется сильноветвящимся.

Приведем алгоритм построения упорядоченного дерева.

1. Если дерево пусто, то данные переносятся в корень дерева. Если же дерево не пусто, то осуществляется спуск по одной из его ветвей таким образом, чтобы упорядоченность дерева не нарушалась. В результате новый узел становится очередным листом дерева.

2. Чтобы добавить узел в уже существующее дерево, можно воспользоваться вышеприведенным алгоритмом.

3. При удалении узла из дерева следует быть внимательным. Если удаляемый узел является листом, или же имеет только одного потомка, то операция проста. Если же удаляемый узел имеет двух потомков, то необходимо будет найти узел среди его потомков, который можно будет поставить на его место. Это нужно в силу требования упорядоченности дерева.

Можно поступить таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.

При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.

Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссьшкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:

TYPE TreeLink = ^Tree;

Inf: <тип данных>;

Left, Right: TreeLink;

1. Построить дерево из n узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).

Рекурсивный алгоритм построения:

1) первый узел берется в качестве корня дерева.

2) тем же способом строится левое поддерево из nl узлов.

3) тем же способом строится правое поддерево из nr узлов;

nr = n – nl – 1. В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:

Function Tree(n: Byte) : TreeLink;

Var t: TreeLink; nl,nr,x: Byte;

If n = 0 then Tree:= nil

nr = n – nl – 1;

writeln("Введите номер вершины ");

t^.left:= Tree(nl);

t^.right:= Tree(nr);

2. В бинарном упорядоченном дереве найти узел с заданным значением ключевого поля. Если такого элемента в дереве нет, то добавить его в дерево.

Procedure Search(x: Byte; var t: TreeLink);

Else if x < t^.inf then

Search(x, t^.left)

Else if x > t^.inf then

Search(x, t^.right)

{обработка найденного элемента}

3. Написать процедуры обхода дерева в прямом, симметричном и обратном порядке соответственно.

3.1. Procedure Preorder(t: TreeLink);

If t <> nil then

Writeln(t^.inf);

Preorder(t^.left);

Preorder(t^.right);

3.2. Procedure Inorder(t: TreeLink);

If t <> nil then

Inorder(t^.left);

Writeln(t^.inf);

Inorder(t^.right);

3.3. Procedure Postorder(t: TreeLink);

If t <> nil then

Postorder(t^.left);

Postorder(t^.right);

Writeln(t^.inf);

4. В бинарном упорядоченном дереве удалить узел с заданным значением ключевого поля.

Опишем рекурсивную процедуру, которая будет учитывать наличие требуемого элемента в дереве и количество потомков этого узла. Если удаляемый узел имеет двух потомков, то он будет заменен самым большим значением ключа в его левом поддереве, и только после этого он будет окончательно удален.

Procedure Delete1(x: Byte; var t: TreeLink);

Var p: TreeLink;

Procedure Delete2(var q: TreeLink);

If q^.right <> nil then Delete2(q^.right)

p^.inf:= q^.inf;

Writeln("искомого элемента нет")

Else if x < t^.inf then

Delete1(x, t^.left)

Else if x > t^.inf then

Delete1(x, t^.right)

If p^.left = nil then

If p^.right = nil then

Абстрактное бинарное дерево

Лекция Деревья

Деревья (trees) используются для представления отношения. Все деревья являются иерархическими по своей сути. Интуитивное значение этого термина состоит в том, что между узлами дерева существует отношение "родительский-дочерний". Если ребро со­единяет узел n и узел т, причем узел п находится выше узла т, то узел n счи­тается родителем (parent) узла т, а узел т - его дочерним узлом (child) . В де­реве, изображенном на рис. 10.1, узлы В и С являются дочерними по отношению к узлу А. Дочерние узлы, имеющие одного и того же родителя, - например, уз­лы В и С - называются братьями (siblings) . Каждый узел дерева имеет по крайней мере одного родителя, причем в дереве существует только один узел, не имеющий предков. Такой узел называется корнем дерева (root) . На рис. 10.1 корнем является узел А. Узел, у которого нет дочерних узлов, называется лис­том дерева (leaf). Листьями дерева, изображенного на рис. 10.1, являются узлы С, D, Е и F.

Рис. 10.1. Дерево общего в

Отношения между родительским и дочерним узлом с абстрактной точки зре­ния является отношением между предком (ancestor) и потомком (descendant). На рис. 10.1 узел А является предком узла Д следовательно, узел D является по­томком узла А. Не все узлы могут быть связаны отношениями "предок-потомок": узлы В и С, например, не связаны родственными отношениями. Однако корень любого дерева является предком каждого его узла. Поддеревом (subtree) называется любой узел дерева со всеми его потомками. Поддеревом узла п является поддерево, корнем которого является узел n. Например, на рис. 10.2 показано поддерево дерева, изображенного на рис. 10.1. Корнем этого поддерева является узел В, а само поддерево является поддеревом узла А.

С формальной точки зрения, дерево общего вида (general tree) T представляет собой множество, состоящее из одного или нескольких узлов, принадлежащих непересекающимся подмножествам, указанным ниже.

Отдельный узел r, корень.

Множество поддеревьев корня r.

Бинарное дерево (binary tree) - это множество узлов Т, таких что

Множество Т пусто, или

Множество Т распадается на три непересекающихся подмножества:

Отдельный корень r, корень;

Два возможно пустых поддерева бинарного дерева, которые называются левым и правым поддеревьями (leaf and right subtrees) корня r, соответственно.

В качестве иллюстрации использования бинарных деревьев для представле­ния данных в иерархическом виде рассмотрим рис. 10.4. На этом рисунке би­нарные деревья представляют алгебраические выражения, содержащие бинарные операторы +, -, * и /. Для представления выражения а-b оператор помещается в корневой узел, а операнды а и b- в его левый и правый дочерние узлы, соответственно (рис. 10.4). На рис. 10.4, б представлено выражение a-b/с, где поддерево представляет подвыражение b/с. Аналогичная ситуация показана на рис. 10.4, в, где изображено выражение (а-b)*с. В узлах этих деревьев хранятся операнды выражений, а в остальных узлах - операторы. Скобки в этих деревьях не представлены. Бинарное дерево создает иерархию операций, т.е. дерево однозначно определяет порядок вычисления выражения.

Рис. 10.4. Бинарные деревья, представляющие алгебраические выражения

Бинарное дерево поиска - это бинарное дерево, некоторым образом упорядоченное в соответ­ствии со значениями, содержащимися в его узлах. Каждый узел п бинарного де­рева поиска обладает следующими тремя свойствами:

Значение узла п больше всех значений, содержащихся в левом поддереве TL.

Значение узла п меньше всех значений, содержащихся в правом поддереве ТR.

Деревья TL и ТR являются деревьями бинарного поиска.

На рис. 10.5 показан пример бинарного дерева поиска. Как следует из его назва­ния, это дерево обеспечивает возможности поиска конкретного элемента. Позд­нее мы рассмотрим эту структуру данных более подробно.

Высота деревьев. Деревья могут иметь разную форму. Например, хотя деревья, изображенные на рис. 10.6, состоят из одинаковых узлов, они имеют совершенно разную структуру. Каждое из этих деревьев содержит семь узлов, но некоторые деревья "выше" других. Высота (height) дерева - это количество узлов, располо­женных на самом длинном пути от корня к листу. Например, высота деревьев, по­казанных на рис. 10.6, равна 3, 5 и 7, соответственно. Интуитивное представление о высоте деревьев может привести к заключению, что их высота равна 2, 4 и 6, соответственно. Действительно, многие авторы используют именно интуитивное оп­ределение высоты дерева (подсчитывая количество ребер на самом длинном пути от корня до дерева. - Прим. ред.). Однако принятое нами определение позволяет более четко формулировать многие алгоритмы и свойства деревьев.

Полное, совершенное и сбалансированное дерево. В полном бинарном дереве(full binary tree), имеющем высоту h, все узлы, расположенные на уровнях, меньших уровня h, имеют по два дочерних узла. На рис. 10.7 представлено пол­ное бинарное дерево, имеющее высоту, равную 3. Каждый узел полного бинарно­го дерева имеет левое и правое поддерево, имеющие одинаковую высоту . Среди всех бинарных деревьев, высота которых равна h, полное бинарное дерево имеет максимально возможное количество листьев, и все они расположены на уровне h. Проще говоря, в полном бинарном дереве нет пропущенных узлов.

Доказывая свойства полных бинарных деревьев, подсчитывая количество их узлов, удобно пользоваться рекурсивным определением.

Если дерево Т пусто, то оно является полным бинарным деревом, имеющим

высоту, равную 0.

Если дерево T не пусто, и его высота равна h > 0, то дерево T является полным бинарным деревом, если поддеревья его корня являются полными бинарными деревьями, имеющими высоту h-1.

Это определение хорошо отражает рекурсивную природу бинарного дерева.

Совершенное бинарное дерево (complete binary tree), имеющее высоту h, - это бинарное дерево, которое является полным вплоть до уровня h-1, а уровень h заполнен слева направо так, как показано на рис. 10.8.

Рис. 10.8. Совершенное бинарное дерево

Очевидно, что полное бинарное дерево является совершенным.

Бинарное дерево называется сбалансированным по высоте (height balanced), или просто сбалансированным (balanced), если высота правого поддерева любого его узла отличается от высоты левого поддерева не больше, чем на 1. Бинарные деревья, изображенные на рис. 10.8 и 10.6, а, яв­ляются сбалансированными, а деревья, представленные на рис. 10.6, б и 10.6, в - нет. Совершенное бинарное дерево является сбалансированным. Итак, повторим кратко введенные понятия.

Абстрактное бинарное дерево

B бинарном дереве существует несколько способов обхода. Стандартными являются три порядка обхода дерева: прямой, симметричный и обратный. Все они описываются в следующем разделе. Над абстрактным бинарным деревом выполняются следующие операции.

Двоичное дерево – вид связного ациклического (не имеющего циклов) графа, характерный тем, что у каждого из его узлов имеется не более двух потомков (связанных узлов, находящихся иерархически ниже).

Определения следующего абзаца не относятся непосредственно к двоичным деревьям, а скорее к вообще, поэтому тем, у кого не возникает проблем с понятиями можно перейти к следующему абзацу.

В двоичном дереве есть только один узел, у которого нет предка, он называется корнем . Конечные узлы – листья . Если у корня отсутствует предок, то у листьев – потомки. Все вершины помимо корня и листьев называются узлами ветвления . Длина пути от корня до узла определяет уровень этого самого узла. Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него. Например, узлы F и L (рис. ниже) расположены на первом уровне, а U и B – на третьем.

Связный граф является деревом тогда и только тогда, когда P - A =1 , где P – количество вершин в графе, а A – количество ребер, поскольку в любом дереве с n вершинами, должно быть n -1 ребро. Это справедливо и для бинарного дерева, так как оно входит в класс деревьев. А увидеть отличительные признаки бинарного дерева , можно просто зная его определение. Достаточно взглянуть на рисунок 1, чтобы понять является ли изображенный на нем граф бинарным деревом.

Во-первых, он связный и не имеет ни одного цикла (следовательно, имеем дело с деревом), во-вторых из каждого узла исходит не больше двух ребер (если бы граф был неориентированным, то допускалось три исходящих ребра), что указывает на главный признак двоичного дерева. Но существует и немного другой способ проверить является ли дерево бинарным. Составим список, в левом столбце которого будут содержаться номера уровней, а в правом – число вершин, лежащих на каждом из них:

Обозначим уровень символом k , а количество вершин n , тогда для бинарного дерева будет справедливо равенство n ≤ 2 k , т. е. количество вершин на k -ом уровне не может иметь значение большее, чем степень двойки этого уровня. Для доказательства этого достаточно построить полное дерево, все уровни которого содержат максимально возможное для двоичного дерева количество вершин:

Продолжая построение, будем получать на каждом новом уровне число вершин равное k -ой степени двойки, а их общее количество вычисляется по формуле:Для рисунка 2 формула раскрывается так: 2 0 +2 1 +2 2 +2 3 =15.

Операция, при которой вершины дерева поочередно просматриваются и каждая только один раз, называется обходом дерева . Выделяют четыре основных метода обхода:

• обход в ширину;
• прямой обход;
• обратный обход;
• симметричный обход;

Обход в ширину – это поуровневая обработка узлов слева на право. Работа метода заключается в просмотре всех вершин, начиная с некоторой вершины на n-ом уровне.

Возьмем нулевой уровень за начальный (рис. 2), и, начиная с вершины K , будем методом обхода в ширину поочередно двигаться вниз, просматривая вершины в следующем порядке: K A X T N H Q F U P L B J V Y.

Обход в прямом порядке вначале предполагает обработку узлов предков, а потом их потомков, то есть сначала посещается вершина дерева, далее левое и правое поддеревья, именно в описанном порядке. Для нашего дерева последовательность прямого обхода такая: K A T F U N P L X H B J Q V Y.

Обход в обратном порядке противоположен прямому обходу. Первыми осматриваются потомки, а уже затем предки, иначе говоря, первоначально обращение идет к элементам нижних уровней левого поддерева, потом то же самое с элементами правого, и в конце осматривается корень. Обратный обход дерева с рисунка 2: F U T P L N A B J H V Y Q X K.

Обход в симметричном порядке заключается в посещении левого узла, перехода в корень и оттуда в правый узел. Все для того же дерева узлы будут осмотрены в следующем порядке: F T U A P N L K B H J X V Q Y.

На практике используются не просто бинарные деревья, а их частные случаи, например, такие как двоичное дерево поиска, АВЛ-дерево, двоичная куча и другие.

Деревья представляют собой иерархическую структуру некой совокупности элементов. Деревья – это одна из наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами, их используют при анализе электрических цепей, математических формул, для организации информации в системах управления базами данных и для представления синтаксических структур в компиляторах.

Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень ), и отношений («родительских»), образующих иерархическую структуру узлов. Вообще говоря, древовидная структура задает для элементов дерева (узлов) отношение «ветвления», которое во многом напоминает строение обычного дерева.

Формально дерево (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 .

Представление двоичных деревьев

Бинарное дерево можно представить в виде динамической структуры данных, состоящей из узлов, каждый из которых содержит кроме данных не более двух ссылок на правое и левое бинарное дерево. На каждый узел имеется одна ссылка. Начальный узел называется корнем.

По аналогии с элементами списков, узлы дерева удобно представить в виде записей, хранящих информацию и два указателя:

Пример фрагмента программы дерева

Type
Tree=^s;
S=record
Inf: <тип хранимой информации>;
Left , right: tree ;
End ;

Изобразим схематично пример дерева, организованного в виде динамической структуры данных:

Дерево поиска

Обратите внимание на рисунок, приведенный выше. Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.

С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.

Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:

• Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:

Если ключи совпадают, поиск завершен;

Если ключ в корне больше искомого, выполнить поиск в левом поддереве;

Если ключ в корне меньше искомого, выполнить поиск в правом поддереве.

• Если дерево пусто, то искомый элемент не найден.

Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность: 1 6 8 10 20 21 25 30.

Можно организовать «зеркально симметричный» обход, начиная с правого поддерева, тогда получим упорядоченную по убыванию последовательность: 30 25 20 10 8 6 1.

Таким образом, деревья поиска можно применять для сортировки значений.

Операции с двоичными деревьями

Для работы с двоичными деревьями важно уметь выполнять следующие операции:

• Поиск по дереву;
• Обход дерева;
• Включение узла в дерево;
• Удаление узла из дерева.

1. Алгоритм поиска по дереву мы рассмотрели выше. Функция поиска:

Пример функции поиска

function find(root:tree; key:integer; var p, parent:tree):Boolean;
begin
p:=root;
while p<>nil do begin
if key=p^.inf then begin{ узел с таким ключом есть }
find:=true;
exit;
end;
parent:=p {запомнить указатель на предка}
if keyP:= p ^. left {спуститься влево}
else p:= p ^. right ; {спуститься вправо}
end;
find:=false;
end;

2. Мы рассмотрели несколько способов обхода дерева. Наибольший интерес для двоичного дерева поиска представляет симметричный обход, т.к. он дает нам упорядоченную последовательность ключей. Логично реализовать обход дерева в виде рекурсивной процедуры.

Пример обхода дерева с помощью рекурсии

Procedure obhod(p:tree);
Begin
if p<>nil then
begin
obhod(p^.left);
writeln(p^.inf);
obhod(p^.right);
end;
end;

3. Вставка узла в двоичное дерево поиска не представляет сложности. Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.

Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.

Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя.

Сложнее всего случай, когда у удаляемого узла есть оба потомка.

Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу. Рассмотрите этот случай на рисунке, должно стать понятней.

В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.

Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.

Рассмотрим реализацию алгоритма удаления.

Пример программы удаления узла из дерева

procedure del (var root: tree ; key: integer);
var
p: tree ; {удаляемый узел}
parent: tree ; {предок удаляемого узла}
function spusk(p:tree):tree;
var
y: tree ; {узел, заменяющий удаляемый}
pred:tree; { предок узла “y”}
begin
y:=p^.right;
if y^.left=nil then y^.left:=p^.left {1}
else {2}
begin
repeat
pred:=y; y:=y^.left;
until y^.left=nil;
y^.left:=p^.left; {3}
pred^.left:=y^.right; {4}
y^.right:=p^.right; {5}
end;
spusk:=y;
end;
begin
if not find(root, key, p, parent) then {6}
begin writeln(" такого элемента нет "); exit; end;
if p^.left=nil then y:=p^.right {7}
else
if p^.right=nil then y:=p^.left {8}
else y:=spusk(p); {9}
if p=root then root:=y {10}
else {11}
if keyParent^.left:=y
else parent^.right:=y;
dispose(p); {12}
end.

В функцию 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}).

Двоичные деревья поиска или бинарные деревья(binary tree) — это структура данных, состоящая из:

• одного единственного корневого узла, который не имеет родителей;
• остальных узлов, которые имеют одного единственного родителя и не более двух потомков.

Каждый узел дерева может быть корневым узлом для одного из своих поддеревьев(subtree) . Родительский узел — это узел, который имеет одного или двух потомков. Тот узел, который не имеет потомков, называется листом или листовым узлом . Двоичные деревья поиска названы так не просто потому что каждый узел дерева может иметь два потомка. Ключ левого потомка данного узла должен быть меньше, чем значение, которое хранит этот узел. Ключ правого потомка должен быть больше значения, которое хранится в родительском узле (см.рисунок).

В общем случае структуру для хранения узла можно представить следующим образом(на языке С):

typedef struct _Node int data ; struct Node * parent ; struct Node * left ; struct Node * right ; } Node ;

Структура, представляющая узел хранит сами данные(поле data ) и три указателя — на родительский узел, левого и правого потомков. У корневого узла дерева поле parent будет равно NULL . Сохранение ссылки на родительский узел на самом деле необязательно. Но в некоторых случаях используется.

Еще раз взгляните на рисунок выше.

Корневой узел содержит в себе значение 27. Значение, которое хранит его левый потомок должно быть меньше, чем значение родительского узла. Мы видим там число 14 (14 < 27). Правый же потомок хранит больше значение(35 > 27) и так далее. Временная сложность процедуры поиска в двоичном дереве поиска оценивается как O(logN) . Допустим, что нам нужно найти вершину с ключом, равным 31.

Для того, чтобы найти этот узел, мы сначала сравниваем его со значением в корне. Корень хранит число 27, которое не является искомым элементом(21 != 27). При этом значение искомого элемента больше(31 > 27), чем значение, хранимое в текущем узле, а это значит, что поиск следует продолжить в правом поддереве. Теперь мы пришли в узел со значением 35. Это также не то, что мы искали, поэтому мы двигаемся дальше, а именно в левое поддерево(так как 31 < 35).

В итоге мы приходим в узел со значением 31, а это именно тот элемент, который мы искали. Возможно вся эта процедура уже вам напомнила обычный двоичный поиск в упорядоченном массиве. Это действительно так. Чем же тогда такое дерево лучше обычного массива? Помимо того же преимущества в скорости поиска, бинарное дерево упрощает процедуру вставки нового элемента в середину последовательности, так как в случае с бинарным деревом нам нужно лишь поменять несколько ссылок.

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

Как решить данную проблему? Для этого используются сбалансированные деревья, вроде красно-черных деревьев, которые предотвращают подобные ситуации в принципе. Но и сложность реализации повышается. Однако порой эта сложность полностью себя оправдывает.

Теперь приведем реализацию бинарного дерева с операциями вставки нового узла и поиска.

Реализация бинарного дерева на языке С.

Еще раз приведем реализацию структуры, представляющей узел дерева:

typedef struct _Node { int data; struct Node *parent; struct Node *left; struct Node *right; } Node;

typedef struct _Node int data ; struct Node * parent ; struct Node * left ; struct Node * right ; } Node ;

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

typedef struct _BinaryTree { Node *root; int size; } BinaryTree;

typedef struct _BinaryTree Node * root ; int size ; } BinaryTree ;

Напишем метод для создания нового дерева, который вернет указатель на созданное дерево.

BinaryTree *createTree() { BinaryTree *tree = (BinaryTree*)malloc(sizeof(BinaryTree)); tree->size = 0; tree->root = NULL; }

BinaryTree * createTree () BinaryTree * tree = (BinaryTree * ) malloc (sizeof (BinaryTree ) ) ; tree -> size = 0 ; tree -> root = NULL ;

Добавление нового узла.

Теперь реализуем метод для добавления нового элемента в дерево. Если дерево еще пусто(root указывает на NULL ), то создаем корень дерева, если нет, то сравниваем значение, которое должен хранить новый элемент со значением текущего узла. Если оно меньше, то двигаемся в левое поддерево, а если больше — в правое, пока не найдем пустой узел, в который можно будет добавить данные:

//добавление нового узла Node *addNode(BinaryTree *tree, int data) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; if(tree->root == NULL) { tree->root = newNode; tree->size++; return newNode; }else { Node *currentNode = tree->root; Node *parent; while(true) { parent = currentNode; if(data < currentNode->data) { //идем в левое поддерево currentNode = currentNode->left; //нашли пустой узел? if(currentNode == NULL) { //добавляем сюда новый узел parent->left = newNode; tree->size++; return newNode; } }else { //идем в правое поддерево currentNode = currentNode->right; //нашли пустой узел? if(currentNode == NULL) { //добавляем сюда новый узел parent->right = newNode; tree->size++; return newNode; } } } } }

//добавление нового узла Node * addNode (BinaryTree * tree , int data ) Node * newNode = (Node * ) malloc (sizeof (Node ) ) ; newNode -> data = data ; newNode -> left = NULL ; newNode -> right = NULL ; if (tree -> root == NULL ) tree -> root = newNode ; tree -> size ++ ; return newNode ; } else Node * currentNode = tree -> root ; Node * parent ; while (true ) parent = currentNode ; if (data < currentNode -> data ) //идем в левое поддерево currentNode = currentNode -> left ; //нашли пустой узел? if (currentNode == NULL ) //добавляем сюда новый узел parent -> left = newNode ; tree -> size ++ ; return newNode ; } else //идем в правое поддерево currentNode = currentNode -> right ; //нашли пустой узел? if (currentNode == NULL ) //добавляем сюда новый узел parent -> right = newNode ; tree -> size ++ ; return newNode ;

Данный метод возвращает указатель на добавленный узел дерева.

Теперь мы можем создать новое дерево и добавить туда несколько элементов.

BinaryTree *tree = createTree(); printf("%s = %i\n", "Count:", tree->size); addNode(tree, 50); addNode(tree, 10); addNode(tree, 75);

BinaryTree * tree = createTree () ; printf ("%s = %i\n" , "Count:" , tree -> size ) ; addNode (tree , 50 ) ; addNode (tree , 10 ) ; addNode (tree , 75 ) ;

Поиск узла с заданным ключом.

Поиск узла в двоичном дереве подразумевает перемещение по дереву и сравнение искомого ключа с ключами, которые хранятся в каждом узле. При каждом сравнении возможны три различные ситуации:

1). Значение ключа совпадает со значением в просматриваемом узле. Значит, элемент найден и мы возвращаем указатель на него.

2). Значение ключа меньше, чем значение, которое хранится в текущем узле. Значит, нужно продолжить поиск в левом поддереве. currentNode = currentNode->left .

3). Значение ключа больше, чем значение, которое хранится в текущем узле. Значит, нужно продолжить поиск в правом поддереве. currentNode = currentNode -> right .

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

//поиск узла Node *search(BinaryTree *tree, int key) { Node *currentNode = tree->root; while(currentNode->data != key) { if(key < currentNode->data) currentNode = currentNode->left; else currentNode = currentNode->right; if(currentNode == NULL) return NULL; } return currentNode; }

//поиск узла Node * search (BinaryTree * tree , int key ) Node * currentNode = tree -> root ; while (currentNode -> data != key ) if (key < currentNode -> data ) currentNode = currentNode -> left ; else currentNode = currentNode -> right ; if (currentNode == NULL ) return NULL ; return currentNode ;

Обход дерева.

Процедурой обхода дерева называется посещение всех узлов дерева по одному разу в определенном порядке. Существует три разных порядка обхода: прямой , центрированный (симметричный) и обратный. Мы рассмотри здесь реализацию наиболее часто используемой процедуры обхода, а именно симметричного порядка обхода. Реализовав данный тип обхода вы с легкостью реализуете два оставшихся. Центрированный порядок обхода подразумевает посещение сначала двух потомков некоторого узла, а затем самого узла. В итоге он обрабатывает узлы дерева в порядке возрастания. Другие два типа обхода используются в разборе алгебраических выражений.

Так как деревья сами по себе обладают рекурсивной структурой, то и обход мы также выполним с применением рекурсии. Итак, наш алгоритм будет состоять из следующих шагов:

1). Обход левого поддерева.

2). Посещение узла(подразумевает какие-то операции над узлом, в нашем случае это просто вывод значения, хранимого в узле на экран).

3). Обход правого поддерева.

Данный алгоритм очень легко реализуется:

//симметричный обход дерева void inorder(BinaryTree *tree, Node *localRoot) { if(localRoot != NULL) { inorder(tree, localRoot->left); printf("%i -> ", localRoot->data); inorder(tree, localRoot->right); } }

//симметричный обход дерева void inorder (BinaryTree * tree , Node * localRoot )