yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

ТЕМА 3

Деревья

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

3.1. Основная терминология

Дерево — это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений ("родительских"), образующих иерархическую структуру узлов. Узлы, так же, как и элементы списков, могут быть элементами любого типа. Мы часто будем изображать узлы буквами, строками или числами. Формально дерево можно рекуррентно определить следующим образом.

1.    Один узел является деревом. Этот же узел также является корнем этого дерева.

2.    Пусть п — это узел, a Tl, Т2, …, Tkдеревья с корнями n1, пг, ..., nk соответственно. Можно построить новое дерево, сделав n родителем узлов n1, n2, .... nk. В этом дереве n будет корнем, а T1, Т2, …, Тkподдеревьями этого корня. Узлы n1, п2, ..., nk называются сыновьями узла п.

Часто в это определение включают понятие нулевого дерева, т.е. "дерева" без узлов, такое дерево мы будем обозначать символом Л.

Пример 3.1. Рассмотрим оглавление книги, схематически представленное на рис. 3.1, а. Это оглавление является деревом, которое в другой форме показано на рис. 3.1, б. Отношение родитель-сын отображается в виде линии. Деревья обычно рисуются сверху вниз, как на рис. 3.1, б, так, что родители располагаются выше "детей".

Корнем этого дерева является узел Книга, который имеет три поддерева соответственно с корнями Гл.1, Гл.2 и Гл. З. Эти отношения показаны линиями, идущими из корня Книга к узлам Гл.1, Гл.2 и Гл. З. Узел Книга является родителем узлов Гл.1, Гл.2 и Гл. З, а эти три узла — сыновьями узла Книга.

Третье поддерево, с корнем Гл. З, состоит из одного узла, остальные два поддерева имеют нетривиальную структуру. Например, поддерево с корнем Гл.2 в свою очередь имеет три поддерева, которые соответствуют разделам книги Р.2.1, Р.2.2 и Р.2.3; последние два поддерева имеют по одному узлу, в то время как первое имеет два поддерева, соответствующие подразделам книги Р.2.1.1 и Р.2.1.2.

Пример 3.1 показывает типичные данные, для которых наилучшим представлением будут деревья. В этом примере родительские отношения устанавливают подчиненность глав и разделов: родительский узел связан с узлами сыновей (и указывает на них), как узел Книга подчиняет себе узлы Гл.1, Гл.2 и Гл. З. В этой книге вы встретите много различных отношений, которые можно представить с помощью родительских отношений и подчиненности в виде деревьев.

Путем из узла nl в узел nk называется последовательность узлов n1, n2, ..., nk, где для всех і, 1 ≤ і ≤ k, узел пi является родителем узла ni+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. На рис. 3.1 путем длины 2 будет, например, путь от узла Гл.2 к узлу Р.2.1.2.

Если существует путь из узла а в b, то в этом случае узел а называется предком узла b, а узел b — потомком узла а. Например, на рис. 3.1 предками узла Р.2.1 будут следующие узлы: сам узел Р.2.1 и узлы Гл.2 и Книга, тогда как потомками этого узла являются опять сам узел Р.2.1 и узлы Р.2.1.1 и Р.2.1.2. Отметим, что любой узел одновременно является и предком, и потомком самого себя.

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

Высотой узла дерева называется длина самого длинного пути из этого узла до какого-либо листа. На рис.3.1 высота узла Гл.1 равна 1, узла Гл.2 — 2, а узла Гл. З — 0. Высота дерева совпадает с высотой корня. Глубина узла определяется как длина пути (он единственный) от корня до этого узла.

Порядок узлов

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

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

Пример 3.2. Рассмотрим дерево на рис. 3.3. Узел 8 расположен справа от узла 2, слева от узлов 9, 6, 10, 4 и 7, и не имеет отношений справа-слева относительно предков 1, 3 и 5.

Существует простое правило, позволяющее определить, какие узлы расположены

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

 

31