1. Деревья. Основные понятия. Корень. Листья. Высота дерева. Примеры
Деревья являются самым распространенным классом графов, применяемых в программировании. Они являются наиболее важными нелинейными структурами данных в комбинаторных алгоритмах.
В теории графов дерево определяется как связный граф без циклов. Мы будем рассматривать корневые деревья, которые относятся к ориентированным графам. В ориентированном графе каждое ребро имеет ориентацию.
Корневое дерево удовлетворяет следующим условиям:
1) имеется в точности один узел (вершина), называемый корнем, в который не входит ни одно ребро;
2) в каждый узел, кроме корня, входит ровно одно ребро;
3) из корня к каждому узлу идет путь (который единствен).
Ориентированный граф, состоящий из нескольких деревьев, называется лесом.
В описании соотношений между узлами используются названия, принятые в генеалогических деревьях. Мы говорим, что в дереве все узлы являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Если в дереве есть ребро, ведущее из узла в узел , то называется отцом узла , а - сыном узла . Если есть путь из в , то называется предком узла , а - потомком узла . Узел без сыновей называется листом. Узел и его потомки вместе образуют поддерево, и называется корнем этого поддерева.
Глубина узла в дереве – это длина пути из корня в . Высота узла в дереве – это длина самого длинного пути из в какой-нибудь лист. Высотой дерева называется высота его корня.
При изображении корневого дерева принято располагать его узлы по уровням. На одном уровне изображаются узлы с одинаковой глубиной. Корень дерева находится на верхнем уровне. На следующем уровне располагаются сыновья корня (их глубина равна 1), далее располагаются сыновья сыновей (их глубина равна 2), и т.д.
Пример корневого дерева приведен на рис. 1. Дерево имеет корень в узле 1; узел 3 имеет глубину 2, так как из корня дерева к узлу 3 ведет путь, состоящий из двух ребер (путь образуют ребра (1,2) и (2,3)); узел 3 имеет высоту 0, так как не имеет ни одного сына. Высота дерева равна 3, поскольку самый длинный путь, ведущий от корня к листу, состоит из трех ребер (например, это путь из узла 1 в узел 5).
Узлы 3, 4 и 5 являются потомками узла 2, а узел 2 – их предком. Кроме того, узлы 3 и 4 – сыновья узла 2, а узел 2 – их отец. Узлы 2, 3, 4, 5 вместе с выходящими из них ребрами образуют поддерево с корнем в узле 2.
Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядочено. При изображении упорядоченного дерева мы будем считать, что множество сыновей каждого узла упорядочено слева направо.
Двоичным (бинарным) деревом называется такое упорядоченное дерево, что
1) каждый сын произвольного узла называется либо левым сыном, либо правым сыном;
2) каждый узел имеет не более одного левого сына и одного правого сына.
Поддерево , корнем которого является левый сын узла (если такое существует), называется левым поддеревом узла . Аналогично поддерево , корнем которого является правый сын узла (если такое существует), называется правым поддеревом узла . Все узлы в расположены левее всех узлов в .
Дерево на рис. 1 является двоичным. Узел 3 это левый сын узла 2, а узел 4 – правый. Поддерево с корнем в узле 2 – левое поддерево узла 1, поддерево с корнем в узле 6 – левое поддерево узла 1.
SHAPE \* MERGEFORMAT
| 1 |
| 2 |
| 6 |
| 3 |
| 4 |
| 5 |
| 7 |
| 8 |
| 9 |
| Рис. 1. Корневое бинарное дерево
|
2. Реализация деревьев
В настоящем разделе мы рассмотрим структуры данных, пригодные для представления корневых деревьев в памяти ЭВМ.
2.1. Реализация деревьев в виде массивов
Наиболее простой способ реализации дерева – это линейный (одномерный) массив. Будем предполагать, что узлы дерева перенумерованы числами . Узлу с номером i ставится в соответствие элемент массива , в котором записывается номер отца. Это возможно сделать, поскольку у любого узла в дереве (кроме корня) один отец. Корень не имеет отца, поэтому соответствующий ему элемент полагается равным нулю.
Построим линейный массив для дерева, изображенного на рис. 2. Будем полагать , если узел является отцом узла .
|
| 1 |
| 8
|
| 10
|
|
|
| 3 |
| 6
|
| 5
|
| 2 |
| 4 |
| 7
|
| 9
|
Тогда массив будет выглядеть следующим образом:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | i |
| 0 | 1 | 1 | 1 | 3 | 3 | 4 | 5 | 5 | 6 | A[i] |
Заметим, что хотя этот способ является простым, с таким представлением дерева в большинстве случаев неудобно работать; здесь легко найти отца для узла, но для нахождения сыновей требуется просмотр всего массива, что существенно увеличивает трудоемкость алгоритмов.
2.2. Реализация деревьев с использованием динамических структур данных
На практике обычно для представления деревьев используются динамические структуры данных. Каждый узел состоит из информационного поля INFO и некоторых полей для указателей. Например, представление дерева, использованное в разделе 2.1, для каждого узла имеет единственное поле FATHER, указывающее на отца данного узла. Графически будем представлять узел в следующем виде:
SHAPE \* MERGEFORMAT
| INFO |
| FATHER |
| Рис. 3. Представление узла дерева с указателем на отца
|
При этом дерево, приведенное на рис. 2, будет выглядеть так, как показано на рис. 4.
SHAPE \* MERGEFORMAT
| 1 |
| 4 |
| 3 |
| 2 |
| 71 |
| 61 |
| 5 |
| 10010 |
| 91 |
| 8 |
| 4 |
| Рис. 4. Представление дерева с помощью узлов с полем INFO и указателем FATHER ( пустой указатель)
|
| λ |
Как было замечено ранее, такое представление полезно, если необходимо подниматься по дереву. Такая операция встречается редко; чаще требуется опуститься по дереву от предков к потомкам.
Один из способов, реализующих связь от отца к сыновьям, состоит в формировании для каждого узла списка его сыновей. Этот способ применяется для ориентированных графов, и в теории графов такое представление известно под названием «списки смежности». Поэтому не будем подробно на нем останавливаться.
Отметим, что узел, имея не более одного отца, может иметь произвольно много сыновей, поэтому списки сыновей для разных узлов имеют разную длину, и такое представление дерева является довольно сложным. Один из путей обхода этой трудности состоит в том, чтобы определить соответствие между деревьями и бинарными деревьями. Бинарные деревья легко представить узлами фиксированного размера. Каждый узел имеет три поля: LEFT – указатель на левого сына, INFO – содержимое узла, и RIGHT - указатель на правого сына. Графически будем представлять узел в виде
SHAPE \* MERGEFORMAT
| LEFT |
| INFO |
| RIGHT |
| Рис. 5. Представление узла бинарного дерева |
Для примера такого представления рассмотрим бинарное дерево на рис. 1. Его представление приведено на рис. 6.
SHAPE \* MERGEFORMAT
| Рис. 6. Представление дерева с помощью узлов с полями LEFT, INFO и RIGHT |
| 4 |
| 3 |
| 2 |
| 61 |
| 1 |
| 9 |
| 71 |
| 51 |
| 81 |
Мы можем представлять деревья как бинарные деревья, представляя каждый узел дерева в виде узла, состоящего из полей LEFT, INFO и RIGHT. При этом поле LEFT предназначается для самого левого сына данного узла, а поле RIGHT – для указания следующего брата данного узла. Таким образом, мы используем поле LEFT некоторого узла для указателя на связанный список сыновей этого узла; этот список связывается с помощью полей RIGHT.
В качестве примера представим в виде бинарного дерева дерево на рис. 2. Это дерево не является бинарным, так как вершина 1 имеет трех сыновей.
На рис. 7 справа горизонтальные линии соответствуют указателям RIGHT, наклонные линии – указателям LEFT. Узлы 2, 3 и 4 в исходном графе являются сыновьями узла 1, поэтому в бинарном дереве самый левый сын - узел 2 – связан с узлом 1 ребром; узлы 2, 3 и 4 образуют линейный список как сыновья одного отца.
Представление с помощью бинарного дерева может быть применено и для леса. Отличие от дерева состоит только в том, что корни деревьев, образующих лес, соединяются в линейный список с использованием указателей RIGHT, точно так же, как сыновья одного отца.
SHAPE \* MERGEFORMAT
| 1 |
| 2 |
| 7 |
| 1 |
| 8
|
| 10
|
|
|
| 3 |
| 6
|
| 5
|
| 2 |
| 4 |
| 7
|
| 9
|
| 32 |
| 4 |
| 5 |
| 6 |
| 8 |
| 95 |
| 105 |
| Рис. 7. Слева дерево, справа его бинарное представление |
3. Обходы дерева
Многие алгоритмы, использующие деревья, часто обходят дерево, исследуя все его узлы, в некотором порядкеПредставляются полезными 4 основных способа обхода, а именно: в глубину, снизу вверх, в горизонтальном порядке и для бинарных деревьев в симметричном порядке. В этом разделе будут рассмотрены первые три способа обхода деревьев. Обход в симметричном порядке будет рассмотрен в следующем разделе.
3.1. Обход дерева в прямом порядке
Пусть - дерево с корнем и сыновьями , . При это дерево состоит из единственного узла .
Обход дерева в прямом порядке, или в глубину, определяется следующей рекурсивной процедурой:
1) посетить корень ,
2) посетить в прямом порядке поддеревья с корнями в указанной последовательности.
Рассмотрим прямой порядок обхода на примере дерева на рис. 8.
SHAPE \* MERGEFORMAT
| a |
| b |
| c |
| d3 |
| e4 |
| h |
| f |
| g |
| s |
| Рис. 8. Пример дерева для иллюстрации обходов
|
Первоначально узлы обозначены буквами латинского алфавита. Будем нумеровать узлы в порядке обхода. Распишем процесс нумерации узлов по шагам.
Шаг 1. Посещаем корень a и присваиваем ему номер 1.
Шаг 2. Начинаем обход первого (левого) поддерева. Посещаем корень b поддерева и присваиваем ему номер 2.
Шаг 3. Начинаем обход первого поддерева для дерева с корнем b. Посещаем корень d поддерева и присваиваем ему номер 3.
Шаг 4. Так как левое поддерево у дерева с корнем d отсутствует, обход поддерева с корнем d закончен. Переходим ко второму поддереву с корнем e и присваиваем узлу e номер 4.
Шаг 5. Начинаем обход первого поддерева дерева с корнем e. Посещаем корень h поддерева и присваиваем ему номер 5.
Шаг 6. Шаг 4. Так как второе поддерево у дерева с корнем e отсутствует, обход поддерева с корнем e закончен. В результате мы обошли второе поддерево с корнем b, обход первого поддерева дерева с корнем a завершен.
Переходим ко второму поддереву дерева с корнем a. Посещаем корень c и присваиваем ему номер 6.
Шаг 7. Начинаем обход первого поддерева для дерева с корнем c. Посещаем корень f поддерева и присваиваем ему номер 7. Обход поддерева с корнем f закончен.
Шаг 8. Начинаем обход второго поддерева для дерева с корнем c. Посещаем корень g поддерева и присваиваем ему номер 8.
Шаг 9. Начинаем обход первого поддерева для дерева с корнем g. Посещаем корень s первого поддерева и присваиваем ему номер 9. так как второго поддерева нет у дерева с корнем g, второе поддерево дерева с корнем c также обойдено. Поскольку поддерево с корнем c является вторым поддеревом всего дерева и других поддеревьев нет, процесс прямого обхода дерева завершен.
На рис. 9 приведен исходный граф с нумерацией вершин, полученной в результате прямого обхода дерева.
Название «в глубину» отражает тот факт, что после посещения некоторого узла мы продолжаем прохождение в глубь дерева всякий раз, когда это возможно. Порядок обхода в глубину особенно полезен в процедурах поиска.
SHAPE \* MERGEFORMAT
| 1 |
| 2 |
| 6 |
| 33 |
| 4e4 |
| 5 |
| 7 |
| 8 |
| 9 |
| Рис. 9. Нумерация узлов при прямом обходе узлов дерева |
3.2. Обход дерева в обратном порядке
Обход дерева в обратном порядке, или снизу вверх, определяется следующей рекурсией:
1) посетить в обратном порядке поддеревья с корнями в указанной последовательности;
2) посетить корень .
Рассмотрим обратный порядок обхода на примере дерева, изображенного на рис. 8. Так же, как и для прямого порядка, будем нумеровать узлы в порядке обхода. Распишем процесс нумерации узлов по шагам.
Шаг 1. Начинаем обход первого (левого) поддерева с корнем b в обратном порядке. Для этого начинаем обход его первого поддерева с корнем d. Поддеревья у дерева с корнем d отсутствуют, поэтому посещаем корень d и присваиваем ему номер 1. Таким образом, обход первого поддерева дерева с корнем b завершен.
Шаг 2. Начинаем обход второго (правого) поддерева с корнем e. Для этого начинаем обход его первого поддерева с корнем h. Поддеревья у дерева с корнем h отсутствуют, поэтому посещаем корень h и присваиваем ему номер 2.
Шаг 3. Других поддеревьев для дерева с корнем e нет. Поэтому посещаем корень e и присваиваем ему номер 3.
Шаг 4. Так как на шаге 3 завершен обход обоих поддеревьев дерева с корнем b, посещаем корень b и присваиваем ему номер 4. Таким образом, обход первого поддерева дерева с корнем a завершен.
Шаг 5. Переходим к обходу второго поддерева для дерева с корнем a. Это поддерево имеет корень c. В свою очередь дерево с корнем c имеет два поддерева с корнями f и g.
Начинаем обход первого поддерева с корнем f. Так как у этого поддерева поддеревьев нет, посещаем корень f и присваиваем ему номер 5.
Шаг 6. Переходим к обходу второго поддерева для дерева с корнем c. Это поддерево имеет корень g . Дерево с корнем g в свою очередь имеет поддерево с корнем s. Так как поддеревьев у дерева с корнем s нет, посещаем корень s и присваиваем ему номер 6.
Шаг 7. Поддеревья узла g обойдены, поэтому посещаем g и присваиваем ему номер 7. В результате мы обошли оба поддерева узла c.
Шаг 8. Посещаем узел c и присваиваем ему номер 8. Мы обошли оба поддерева корня a.
Шаг 9. Посещаем узел a и присваиваем ему номер 9. Обход всего дерева в обратном порядке завершен.
Граф с нумерацией вершин, полученной в результате обратного обхода дерева, приведен на рис. 10.
Название «снизу вверх» связано с тем, что в момент посещения произвольного узла все его потомки оказываются уже пройденными. Порядок обхода снизу вверх полезен, поскольку он позволяет делать рекурсивные вычисления на деревьях.
SHAPE \* MERGEFORMAT
| 9 |
| 4 |
| 8 |
| 13 |
| 3e4 |
| 2 |
| 5 |
| 7 |
| 6 |
| Рис. 10. Нумерация узлов дерева при обратном обходе |
3.3. Обход дерева в горизонтальном порядке
Кратко опишем обход дерева в горизонтальном порядке, или обход в ширину. При таком способе обхода узлы дерева обходятся слева направо, уровень за уровнем от корня вниз. Пример нумерации узлов при горизонтальном обходе дерева приведен на рис. 2 (слева). Такое прохождение дерева полезно в некоторых алгоритмах на графах.
4. Бинарные деревья
4.1. Представления бинарных деревьев
В разделе 2.2 было описано представление бинарных деревьев с использованием указателей LEFT и RIGHT (указателей на левого и правого сына). Здесь мы опишем способы представления бинарных деревьев с использованием массивов.
Предварительно введем понятие полного двоичного дерева.
Двоичное дерево называется полным, если для некоторого целого числа k каждый узел глубины меньшей k имеет как левого, так и правого сына, и каждый узел глубины k является листом. Полное двоичное дерево высоты k имеет ровно узлов.
Полное двоичное дерево высоты k часто представляют одним массивом. В позиции 1 этого массива находится корень. Левый сын узла в позиции i расположен в позиции , а его правый сын – в позиции . Отец узла, находящегося в позиции , расположен в позиции (здесь - ближайшее целое снизу для числа ). Такое представление удобно, так как позволяет легко находить для любого узла дерева его сыновей и отца.
Это представление бинарного дерева можно применять и для неполного дерева, если заполнять нулями ячейки для отсутствующих сыновей. Отметим, что при этом неэкономно используется память.
В качестве примера рассмотрим бинарное дерево, изображенное на рис. 1. Дерево будет представлено описанным способом следующим образом:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | i |
| 1 | 2 | 6 | 3 | 4 | 7 | 8 | 0 | 5 | 0 | 0 | 0 | 0 | 9 | A[i] |
Корень имеет номер 1, и поэтому первый элемент массива A[i] равен 1. Сыновьями корня являются узлы 2 и 6, поэтому левый сын – узел 2 - заносится в ячейку A(2) ((позиция массива при ), а правый сын – узел 6 – в ячейку A(3) (позиция массива при ), и т.д. Узел 8 располагается в ячейке массива с номером 7, и не имеет левого сына, поэтому в ячейке с номером 14 записывается 0; узел 3 – лист, поэтому в ячейках с номерами 6 и 7 записываются нули. Высота дерева , поэтому число элементов массива A равно 15.
Двоичное дерево можно также представить в виде двух массивов: ЛЕВЫЙ_СЫН и ПРАВЫЙ_СЫН. Пусть узлы двоичного дерева перенумерованы числами . В этом случае ЛЕВЫЙ_СЫН[i]=j тогда и только тогда, когда узел с номером j является левым сыном узла с номером i. Если у узла i нет левого сына, то ЛЕВЫЙ_СЫН[i]=0. ПРАВЫЙ_СЫН[i] определяется аналогично.
Бинарное дерево, изображенное на рис. 1, будет представлено так:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | i |
| 2 | 3 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | ЛЕВЫЙ_СЫН |
| 6 | 4 | 0 | 5 | 0 | 8 | 0 | 9 | 0 | ПРАВЫЙ_СЫН |
4.2. Обходы бинарных деревьев
Опишем более подробно варианты обхода бинарных деревьев, так как именно бинарные деревья наиболее широко применяются в практических задачах. Дополнительно к порядкам обхода, применяемым ко всем деревьям, для бинарных деревьев приведем также симметричный порядок обхода.
Для бинарных деревьев процедуры обхода в прямом и в обратном порядке упрощаются. Рекурсивная процедура для обхода в глубину выглядит следующим образом:
1) посетить корень;
2) пройти в глубину левое поддерево;
3) пройти в глубину правое поддерево.
Рекурсивная процедура обхода снизу вверх применительно к бинарным деревьям имеет следующий вид:
1) пройти снизу вверх левое поддерево;
2) пройти снизу вверх правое поддерево;
3) посетить корень.
Симметричный порядок определяется рекурсивно следующим образом:
1) пройти в симметричном порядке левое поддерево;
2) посетить корень;
3) пройти в симметричном порядке правое поддерево.
Распишем по шагам процесс нумерации узлов для дерева, изображенного на рис. 8, при этом будем нумеровать узлы в порядке симметричного обхода.
Шаг 1. Начинаем обход левого поддерева с корнем b в симметричном порядке. Для этого начинаем обход его левого поддерева с корнем d. Поддеревья у дерева с корнем d отсутствуют, поэтому посещаем корень d и присваиваем ему номер 1. Таким образом, обход первого поддерева дерева с корнем b завершен.
Шаг 2. Посещаем корень b и присваиваем ему номер 2.
Шаг 3. Начинаем симметричный обход правого поддерева с корнем e. У дерева с корнем e отсутствует левый сын, поэтому посещаем корень e и присваиваем ему номер 3.
Шаг 4. Начинаем обход правого поддерева с корнем h. Так как у узла h нет левого сына, присваиваем корню h номер 4.
Шаг 5. Так как на шаге 4 завершен обход правого поддерева с корнем b и, следовательно, левое поддерево дерева с корнем a перенумеровано, переходим к корню a и присваиваем ему номер 5.
Шаг 6. Переходим к обходу правого поддерева для дерева с корнем a. Это поддерево имеет корень c. В свою очередь дерево с корнем c имеет два поддерева с корнями f и g. Начинаем обход левого поддерева с корнем f. Так как f - лист, посещаем корень f и присваиваем ему номер 6.
Шаг 7. Переходим к корню c и присваиваем ему номер 7.
Шаг 8. Переходим к обходу правого поддерева для дерева с корнем c. Это поддерево имеет корень g. Дерево с корнем g не имеет левого сына, поэтому посещаем корень g и присваиваем ему номер 8.
Дерево с нумерацией узлов, полученной в результате симметричного обхода, изображено на рис. 11.
SHAPE \* MERGEFORMAT
| 5 |
| 2 |
| 7 |
| 13 |
| 3e4 |
| 4 |
| 6 |
| 8 |
| 9 |
| Рис. 11. Нумерация узлов при симметричном обходе дерева |
Можно обнаружить значительное сходство в рекурсивных процедурах обхода бинарных деревьев в глубину, снизу вверх и в симметричном порядке.
| Обход в глубину | Симметричный порядок | Обход снизу вверх |
| 1. посетить корень | 1. левое поддерево | 1. левое поддерево |
| 2. левое поддерево | 2. посетить корень | 2. правое поддерево |
| 3. правое поддерево | 3. правое поддерево | 3. посетить корень |
Опишем общий нерекурсивный алгоритм, который может быть применен к каждому из этих порядков. В нем используется стек S для хранения пар, состоящих из узла бинарного дерева и целого i, значение которого указывает нам, какую из трех операций соответствующей процедуры прохождения (первую, вторую или третью) надо применять, когда пара достигнет вершины стека. В алгоритме используются следующие операции:
| 1. Посетить корень<… Продолжение » |
|
© a-urusov2011 |