1. Теоретические положения

1.1. Деревья. Основные понятия

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

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

2. Пусть n – узел, а T₁, T₂, ..., T_k – деревья с корнями n₁, n₂, ..., n_k соответственно. Можно построить новое дерево, сделав n родителем узлов n₁, n₂, ..., n_k. В этом дереве n будет корнем, а T₁, T₂, ..., T_k – поддеревьями этого корня. Узлы n₁, n₂, ..., n_k называются дочерними узлами узла n. Узлы, находящиеся на одном уровне (в частности, узлы n₁, n₂, ..., n_k), называют соседними (в некоторых источниках – братьями или сестрами).

Пустую структуру или дерево без узлов называют также нулевым (пустым) деревом. Путем из узла n₁ в узел n_k называется последовательность узлов n₁, n₂, ..., n_k, где для всех i, i = 1, 2, ..., k, узел n_i является родителем узла n_i+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь. Путем нулевой длины будет путь из любого узла к самому себе. Если существует путь из узла а в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла a. Число непосредственных потомков (дочерних узлов) внутренней вершины называют ее степенью. Степень дерева определяется максимальной из степеней всех узлов. Предок или потомок узла, не являющийся таковым самого себя, называется истинным предком или истинным потомком соответственно. Только корень дерева не имеет истинного предка. Если узел не имеет истинных потомков, он называется терминальной вершиной или листом, в противном случае – нетерминальной вершиной или внутренним узлом. Поддерево какого-либо дерева можно определить как узел – корень поддерева – вместе со всеми его потомками. Высотой узла называется длина самого длинного пути из этого узла до какого-либо листа. Высота дерева совпадает с высотой корня. Глубина узла x определяется как длина пути от корня до узла x. Ее часто называют просто длиной пути к x. В таком случае корень имеет длину пути 0, его дочерние узлы – длину пути 1 и т.д. Длина пути всего дерева определяется как сумма длин путей всех его узлов. Она называется длиной внутреннего пути. Часто каждому узлу дерева сопоставляется метка, ключ или иначе – значение, которое хранится в узле [1]. Дочерние узлы могут упорядочиваться справа налево. Если порядок дочерних узлов игнорируется, дерево называется неупорядоченным, в противном случае – упорядоченным. Особое значение имеют упорядоченные деревья второй степени. Они называются двоичными или бинарными. Двоичное дерево определяется как конечное множество узлов, пустое, либо состоящее из корня с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревьями этого корня. Деревья степени больше двух называются сильноветвящимися деревьями.

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

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

• Если дерево Т состоит из одного узла, то в список обхода записывается этот узел.

• Далее, пусть Т – дерево с корнем n и поддеревьями Т₁, Т₂, ..., Т_k (см. рис. 1). Для различных способов обхода выполняется следующее:

Рис. 1. Дерево Т

1. При прохождении в прямом порядке узлов дерева Т сначала посещается корень n, затем – в прямом порядке – узлы поддерева Т₁, далее аналогично все узлы поддерева Т₂. Последними в прямом порядке посещаются узлы поддерева Т_k.

2. При симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева Т₁, далее корень n, затем последовательно в симметричном порядке все узлы поддеревьев Т₂, ..., Т_k.

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

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

1. Root(). Возвращает узел, являющийся корнем дерева.

2. GetLabel(n). Возвращает ключ узла n.

3. SetLabel(n, m). Устанавливает ключ m узла n.

4. Search(m). Осуществляет поиск в дереве узла с ключом m. Возвращает искомый узел или нулевой узел, если поиск окончился неудачей.

5. Add(m, n). Добавляет узел с ключом m в дерево как дочернюю вершину узла n, если в результате выполнения операции степень дерева не изменится и непосредственно перед ее выполнением функция Search(m) возвратила нулевой узел.

6. Delete(m). Удаляет узел с ключом m.

7. Parent(n). Возвращает родителя узла n. Если n является корнем, возвращается нулевой узел.

8. LeftMostChild(n). Возвращает самый левый дочерний узел узла n. Если n является листом, возвращается нулевой узел.

9. RightSibling(n). Возвращает правого соседа узла n и нулевой узел, если такового не существует. Для этого находится родитель p узла n и все дочерние узлы p, затем среди этих потомков находится узел, расположенный непосредственно справа от узла n.

10. MakeNull(). Делает дерево пустым.

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