Главная » Java, Структуры данных и алгоритмы » Бинарные деревья

0

Одним из видов деревьев, представляющих особый интерес, является бинарное дерево. Как установлено в п. 6.1.1, правильным бинарным деревом является упорядоченное дерево, в котором каждый составной узел имеет два дочерних элемента. Более того, там же специально оговорено, что бинарные деревья считаются правильными, если только’обратное не будет отмечено специально. Заметим, что это условие никоим образом не нарушает целостности понятия, следовательно, любое неправильное бинарное дерево может быть легко преобразовано в правильное, в чем можно убедиться, выполнив упражнение М-6.3. И даже, отказавшись от этого условия, можно считать неправильное бинарное дерево правильным, рассматривая недостающие простые узлы как «нулевые узлы» или установив заглушки, выступающие в роли узлов.

имеют много применений. К примеру, дерево арифметического выражения (пример 6.5) является бинарным, так как каждый из используемых для определения дерева операторов является бинарным. Дерево решений (пример 6.4) также бинарное, поскольку результатом решения выступают «да» или «нет». Далее приводятся несколько характерных для бинарных деревьев[14] областей применения.

Абстрактный тип данных «бинарное дерево»

Как абстрактный тип данных, бинарное дерево представляет собой специальный вид дерева, поддерживающий три дополнительных метода обращения:

•          leftChild(v): возвращает левьщ дочерний элемент узла v; ошибка возникает, если v — простой узел.

Input: позиция, Output: позиция.

•          rightChild(v): возвращает правый дочерний элемент узла v; ошибка возникает, если v — простой узел.

Input: позиция, Output: позиция.

•          sibling(v): возвращает соседний узел (брата) узла v; ошибка возникает, если v — корень.

Input: позиция, Output: позиция.

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

Java-интерфейс бинарного дерева

Модель бинарного дерева представлена в виде абстрактного типа данных с Java-интерфейсами InspectableBinaryTree и BinaryTree (фрагмент кода 6.15). Взаимоотношения между этими и связанными с ними интерфейсами показаны на рис. 6.11. Кстати, поскольку бинарные деревья являются упбрядоченными, то итератор, возвращаемый методом children(v) (наследуемый от интерфейса InspectableTree), обращается сначала к левому дочернему элементу узла v, а затем — к правому.

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

children(v) выполняется за 0(1) времени, так как каждый узел содержит либо имеет два дочерних элемента либо ни одного. • Методы leftChild(v), rightChild(v) и sibling(v) выполняются за 0(1) времени каждый.

public interface InspectableBinary Tree extends Inspectable Tree { // методы доступа

Г* возвращают левый дочерний элемент узла */ public Position leftChild(Position v); Г* возвращают правый дочерний элемент узла */ public Position ringChild(Position v); Г* возвращают соседний узел 7 public Position sibling(Position v);

}

public interface Binary. Tree

extends InspectableBinaryTree, PositionalContainer {

}

Фрагмент кода 6.15. Интерфейс InspectableBinaryTree, расширяющий интерфейс InspectableTree (фрагмент кода 6.1), и интерфейс BinaryTree, расширяющий интерфейсы InspectableBinaryTree (фрагмент кода 6.15) и PositionContainer (фрагмент кода 6.1)

Рис. 6.11. Иерархия наследования абстрактных типов данных, представляющих последовательности и деревья

Свойства бинарного дерева

имеют несколько интересных свойств, касающихся отношений между их высотой и количеством узлов. Определим все узлы дерева Т\ расположенные на одной глубине d, как уровень d дерева 71 В бинарном дереве нулевой уровень содержит один узел (корень), первый уровень содержит, максимум два узла (дочерних элемента корня), второй уровень — максимум четыре узла и так далее (см. р^с. 6.12). В принципе, уровень d содержит максимум 2d узлов.

Рис. 6.12. Максимальное количество узлов на каждом уровне бинарного дерева

Как можно заметить, максимальное количество узлов на каждом уровне бинарного дерева экспоненциально возрастает по мере продвижения вниз по дереву. Из этого наблюдения следует заключение относительно свойств взаимозависимости высоты бинарного дерева Т и количества узлов. Подробное обоснование этих свойств оставлено для упражнеия М-6.13.

Утверждение 6.3. Допустим, Т является бинарным (правильным) деревом с количеством узлов п и высотой Л. Тогда Тимеет следующие свойства:

2)    количество составных узлов дерева Гравно минимум h и максимум 2Л – 1;

3)    общее количество узлов дерева Т равно минимум 2Л +1 и максимум 2/l+l – 1;

4)     высота дерева Травна минимум log(п + 1) – 1 и максимум (п – 1)/2, то есть log(п + 1) – 1 < h < (п- 1)/2.

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

Утверждение 6.4. В бинарном (правильном) дереве Г количество простых узлов на единицу больше количества составных узлов.

Доказательство. Разобьем узлы бинарного дерева на две «стопы» — стопу с составными узлами и стопу с простыми узлами, как если бы разделить коробку конфет между двумя детьми. Если само дерево Г имеет только один узел v, то он будет простым, и утверждение остается в силе.

Если же это не так, удалим из Т произвольный простой узел w и его родителя v, который является составным узлом. Теперь представим, что w укладывается в стопу простых узлов, a v — в стопу составных. Если родителем v является узел и, то заново связываем и с бывшим братом (соседним узлом) w — узлом z, как это показано на рис. 6.13. Такая операция под названием removeAboveExternal(w) удаляет один составной и один простой узлы, а дерево при этом остается правильным бинарным деревом.

Рис. 6.13. Операция remove Above External (w), удаляющая простой узел и его родителя и иллюстрирующая обоснование утверждения 6.11

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

Обратите внимание, что это утверждение не будет истинным в принципе, если дерево не бинарное, как это можно увидеть из упражнения 3-6.6.

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

Проход бинарного дерева

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

Прямой проход бинарного дерёва

Поскольку любое бинарное дерево может рассматриваться как обычное, прямой проход обычного дерева (фрагмент кода 6.9) применим и к любому бинарному дереву. В этом случае алгоритм прохождения может быть упрощен, как это показано во фрагменте кода 6.16.

Алгоритм binaryPreorder( Т, v):

выполнить обращение "vizit" к узлу v if v составной узел then

binaryPreorder(r, r.leftChild(v)) {рекурсивное прохождение левой ветви} binaryPreorder(7", IrightChild(v)) {рекурсивное прохождение правой ветви}

Фрагмент кода 6.16. Алгоритм binaryPreorder, выполняющий прямой проход одной из ветвей бинарного дерева Т, корнем которой является узел v

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

Обратный проход бинарного дерева

Аналогично обратному проходу обычных деревьев можно выполнять обратный проход бинарного дерева (фрагмент кода 6.17).

Алгоритм binaryPostorder(r, v): if v составной узел then

binaryPostorder (Г, T.leftChild(v)) {рекурсивное прохождение левой ветви} binaryPostorder(r, IrightChild(v)) {рекурсивное прохождение правой ветви} обработка "визита" в узел v

Фрагмент кода 6.17. Алгоритм binaryPostorder, выполняющий обратный проход одной из ветвей бинарного дерева Г, корнем которой является узел v

Обратный проход бинарного дерева может применяться для решения задач определения значения выражения. В этом случае имеется дерево арифметического выражения, то есть бинарное дерево, в котором каждый простой узел содержит ассоциируемое с ним значение, а каждый составной узел — ассоциируемую с ним арифметическую операцию (см. пример 6.5). Необходимо вычислить значение арифметического выражения, представленного деревом.

Алгоритм evaluateExpression, показанный во фрагменте кода 6.18, определяет значение выражения, соответствующего ветви, причем корнем этой ветви служит узел v дерева Т арифметического выражения, с помощью обратного прохода по дереву Т от узла v. В этом случае обращение будет состоять из выполнения одной арифметической операции.

Алгоритм evaluateExpression(7»:

if v составной узел, хранящий оператор о, then х <r- evaluateExpression(r, r.leftChild(\/)) у <- evaluateExpression(r, TrightChild(i/)) return x о у else

return значение, хранимое в v

Фрагмент кода 6.18. Алгоритм evaluateExpression для вычисления значения выражения, представленного ветвью дерева арифметического выражения Г, корнем которого служит узел v                                                                                f

Время выполнения алгоритма обратного прохода для вычисления значения арифметического выражения в дереве с количеством узлов п составляет 0{п). Но, как и в случае с обратным проходом обычного дерева, обратный проход бинарного дерева может применяться и к другим «перевернутым» вычислениям значений (типа вычисления размера, приведенного в примере 6.7). При этом особенностью обратного прохождения по бинарному дереву является возможность упростить процесс, поскольку используются методы leftChild и rightChild, чтобы избежать итерационного цикла при прохождении всех дочерних элементов сложного узла.

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

Симметричный проход бинарного дерева

Дополнительным методом прохождения бинарного дерева является симметричный проход. При таком виде прохода обращение происходит к узлу между двумя рекурсивными прохождениями по его левой и правой ветви. Симметричный проход ветви, корнем которой является узел v бинарного дерева Г, приводится во фрагменте кода 6.19.

Алгоритм inorder(T.v): ‘ if v составной узел then

inorder(T, T.leftChild(v)) {рекурсивное лрохрждение левой ветви} выполнить обращение к узлу.у if v составной узел then

inorder(T, T.rightChild(v)) {рекурсивное прохождение правой ветви}

Фрагмент кода 6.19. Алгоритм inorder симметричного прохода ветви бинарного дерера Г, корнем которого является узел v

Симметричный проход бинарного дерева Т может рассматриваться как последовательное обращение к узлам дерева «слева направо». В самом деле, для каждого узла v при симметричном прохождении обращение к узлу выполняется после того, как пройдены все узлы в левой ветви v, но до того, как будут пройдены все узлы в правой ветви v (рис. 6.14).

Рис. 6.14. Симметричный обход бинарного дерева

Алгоритм симметричного прохода также имеет несколько областей применения. Одна из наиболее важных — хранение упорядоченной последовательности элементов в бинарном дереве. Такая структура называется бинарным поисковым деревом (binary search tree). В частности, охарактеризуем бинарное поисковое дерево как дерево, в котором каждый составной узел v содержит элемент е, так что элементы, хранимые в левой ветви v, меньше или равны е, а элементы, хранимые в правой ветви v, больше или равны е. Более того, допустим, что простые узлы не содержат элементов, следовательно, они фактически являются нулевыми объектами иди ссылками на объект f^lULLJSIODE.

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

Бинарное поисковое дерево Г может использоваться для определения местоположения элемента с конкретным значением х путем прохождения вниз по дереву. При обращении к каждому составному узлу значение текущего узла сравнивается с требуемым элементом х. Если значение «меньше» искомого, поиск продолжается в левой ветви. При равенстве поиск успешно завершается. Если «больше», то поиск перемещается в правую ветвь. И наконец, при достижении простого узла (в котором ничего нет) поиск завершается безрезультатно (см. рис. 6.15).

Рис. 6.15. Бинарное поисковое дерево, хранящее целые числа. Путь, указанный линией с короткими штрихами, указывает на успешное завершение поиска числа 36. Линия с длинным пунктиром отмечает безуспешный поиск числа 70

Время выполнения поиска в бинарном дереве Г пропорционально его высоте. Согласно утверждению 6.3, высота дерева с количеством узлов, равным п, может быть как минимум 0(long п) и как максимум О(п). Так что наиболее эффективен поиск в деревьях с небольшой высотой. В разделе 9.1 описан поиск в бинарном поисковом дереве рис. 6.15 и более детально рассмотрены сами бинарные поисковые деревья.

Симметричный проход применим и к задачам вычисления схемы бинарного дерева. Можно изобразить бинарное дерево Т с помощью алгоритма, который, руководствуясь двумя нижеприведенными правилами, устанавливает для каждого узла v дерева Т координаты х и у (см. рис. 6.16):

•          x(v) равно количеству узлов, пройденных до обращения к v при симметричном проходе дерева Т;

•       y(v) равно глубине узла v в дереве Т.

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

Рис. 6.16. Алгоритм отображения симметричного прохода бинарного дерева

Унифицированная среда прохода дерева

Рассматривая алгоритмы прохода дерева с точки зрения объект- но-ориентированного подхода, можно сделать вывод об их различии по способам реализации итераторов. При прохождении каждое обращение к узлу дерева выполняется в определенном порядке и только единожды. Алгоритмы прохода дерева унифицируются в виде единого обобщенного подхода при отсутствии требования об одноразовом обращении к узлу. Полученный в результате метод прохода будет называться «проходом по Эйлеру» (Euler tour traversal), или эйлеровым проходом.

Эйлеровый проход бинарного дерева Т можно неформально определить как «прогулку» вокруг Г, начинающуюся из корня в сторону левого дочернего элемента, а границы дерева Г рассматриваются при этом как «стены», которые всегда должны оставаться слева (см. рис. 6.17).

Каждый узел v дерева Т при эйлеровом проходе будет встречаться трижды:

•     «слева» (до прохода вдоль левой ветви v);

•     «снизу» (когда окажемся между двумя ветвями v);

•     «справа» (при проходе вдоль правой ветви v).

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

Рис. 6.17. Обход бинарного дерева по правилу Эйлера

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

Прямой проход бинарного дерева совпадает с эйлеровым проходом в том смысле, что обращёййе ЪеугЦ^твляетСя только к левому по ходу узлу. Аналогично симметричный и обратный проходы бинарного дерева эквивалентны эйлеровому проходу в том плане, что обращение к узлу выполняется при подходе к нему снизу или справа соответственно.

Проход по Эйлеру расширяет прямой, обратный и симметричный виды проходов, но может выполнять и другие их виды. Например, необходимо определить количество потомков каждого узла v в бинарном дереве с количеством узлов п. Начнем эйлеровый проход, установив счетчик равным 0, и затем будем увеличивать его значение при каждом обращении к узлу, двигаясь по левой стороне. Определение количества потомков узла v соответствует разности между значениями счетчика при обращении к v слева и справа, добавив 1. Это простое правило позволяет определить количество потомков v, так как каждый узел в ветви, корнем которой является v, находится между обращениями к v слева и справа. Таким

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

Алгоритм eulerTour(7»:

Выполнить обращение к узлу v слева if v составной узел then

рекурсивно обойти левую ветвь узла v с помощью eulerTour(T, r.leftChild(v)) выполнять обращение к v снизу if v составной узел then

рекурсивно обойти правую ветвь узла v с помощью eulerTour(T, T.rightChild(v)) выполнять обращение к v справа

Фрагмент кода 6.20. Алгоритм eulerTour для вычисления эйлерового прохода ветви дерева Г, корнем которого служит узел v

Время выполнения эйлерового прохода легко проанализировать, допустив, что обращение к каждому узлу требует 0(1) времени. А именно, при прохождении затрачивается постоянный отрезок времени для доступа к каждому узлу дерева, поэтому общие затраты времени составят 0(п) для дерева с количеством узлов п.

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

Алгоритм print Expression, показанный фрагментом кода 6.21, выполняет эту задачу с помощью следующих действий:

•      обращение «слева» — если узел составной, напечатать "(";

•          обращение «снизу» — распечатать значение или оператор, хранимый в узле;

•      обращение «справа» — если узел составной, напечатать ")".

Алгоритм printExpression(7» : if TisExternal(i/) then

вывести на экран значение, хранимое в v else

print "(м

printExpression(r,r.leftChild(i/)) print the operator stored at v printExpression(r,r.rigritChild(i/)) , print ")"

Фрагмент кода 6.21. Алгоритм вывода арифметического выражения, ассоциируемого с соответствующей ветвью дерева, корнем которого является узел v дерева Т

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии