Лекция 14

Деревья.

Дерево — это абстрактная структура данных, иерархия которой похожа на дерево. Состоит из связанных узлов, один из которых является «корнем». Каждый узел может иметь одного предка и/или одного или нескольких потомков. (Дерево является связным графом без циклов.)

Корень дерева — это самый верхний узел.

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

Лист — узел, не имеющий дочерних элементов (потомков).

Внутренний узел — узел дерева, имеющий потомков.

Глубина дерева — самый длинный путь от корня дерева до его листа.

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

Обход узлов дерева

16 → 11 →10 → 1, 2; 5 → 4; 9 → 6, 8

Обход дерева «в глубину»: обход всех потомков каждого узла. Удобно реализовывать рекурсивно:

Процедура Обход дерева в глубину

Обход поддерева в глубину <вх: дерево.root>

Конец процедуры

Процедура Обход поддерева в глубину <вх: node: узел дерева>

Обработать узел<вх: node>

Цикл для каждого узла child из node.childs выполнять

Обход поддерева в глубину <вх: child>

Конец цикла

Конец процедуры

16 → 11 → 9 → 10 → 5 → 6 → 8 → 1 → 2 → 4

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

Процедура Обход дерева в ширину

Очередь_узлов.сделать пустой

Очередь_узлов.добавить<вх: дерево.root>

Цикл пока Очередь_узлов.непуста выполнять

Очередь_узлов.взять элемент из очереди в <вых: node>

Обработать узел<вх: node>

Цикл для каждого узла child из node.childs выполнять

Очередь_узлов.добавить элемент в конец очереди <вх: child>

Конец цикла

Конец процедуры

Двоичная куча

Двоичная куча (пирамида, сортирующее дерево) — это двоичное дерево, удовлетворяющее следующим условиям:

1) Значение в каждом узле дерева не меньше, чем значение в любом из потомков этого узла;

2) Каждый лист имеет глубину d или d-1, где d – глубина дерева;

3) Самый глубокий слой заполняется без пропусков.

Значения, содержащиеся в узлах двоичной кучи, удобно хранить в массиве послойно, начиная сверху дерева. Корень дерева хранится в Array[0], его левый потомок в Array[1], правый в Array[2] и т. д. Потомки элемента Array[i] находятся в Array[2*i+1] и Array[2*i+2].

При нумерации с нуля слоев дерева сверху вниз и узлов слоя слева направо, i-й узел в j-м слое хранится в элементе вектора с индексом i+2^j-1 (при индексации элементов вектора, начиная с 0).

Пример 1. Следующий массив хранит содержимое приведенной на рисунке двоичной кучи:

Вопрос. Как по индексу в массиве вычислить для элемента номер уровня в дереве и его номер в уровне?

N → L, n

3(10) → 2,

L = [log₂(N + 1)], n = N – (2^L - 1)

Индекс 9 (элемент 4) → L=3, n = 2

Вопрос. Как по номеру уровня в дереве и его номеру в уровне вычислить индекс в массиве ?

L, n → N = 2^L – 1 + n

Элемент 4: L=3, n=2 => N = 9

Вопрос. Как массив превратить в двоичную кучу?

0	1	2	3	4	5	6	7	8	9	10	11
4	10	-7	3	12	16	-10	4	5	1	-2	0

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

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

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

Следующая процедура (heapify) реализует описанный алгоритм:

Процедура heapify<вх: ar: массив, N: целое число>

! Дано: массив ar, N – размер массива

! Надо: массив ar содержит двоичную кучу размера N

! Алгоритм: превращаем «хвост» массива в двоичную кучу,

! последовательно сдвигая начало «хвоста» к началу массива

start := parent(N-1) ! start := индекс самого последнего внутреннего узла

Цикл пока start >= 0 выполнять

siftDown(ar, start, N-1) ! Просеять: если надо, переместить содержимое

! корня вниз, чтобы дерево стало двоичной кучей

start = start – 1 ! Переходим к предыдущему внутреннему узлу

Конец цикла

Конец процедуры

Процедура parent<вх: n: индекс узла в массиве>

! Возвращает индекс родительского узла

ответ := (n – 1) / 2

Конец процедуры

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

В противном случае нам придется переместить V вниз по дереву. Перемещение происходит посредством обмена значениями двух узлов — родительского и дочернего (того из дочерних, в котором бОльшее значение): большее значение идет вверх, меньшее вниз. Процесс напоминает сортировку «пузырьком», только здесь «пузырек» проходит не по всему массиву, а только по одной ветви дерева, что существенно сокращает его путь: c O(N) до O(log N).

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

Процедура siftDown<вх: ar: массив, root: индекс, end: индекс>

! Починить кучу, корень которой находится в элементе с индексом root,

! предполагая, что оба дочерних поддерева являются двоичными кучами

! end – индекс последнего узла дерева

! Пока у корня есть дочерний узел со значением большим, чем значение в корне

Цикл пока ((leftChild(root) <= end) и (ar[root] < ar[leftChild(root))) или

((rightChild(root) <= end) и (ar[root] < ar[rightChild(root)))) выполнять

! Если значение в левом дочернем узле больше, чем в правом

Если (rightChild(root) > end) или (ar[leftChild(root)] > ar[rightChild(root)]) то

swap(root, leftChild(root)) ! Обмениваем значения корня и левого дочернего узла

root := leftChild(root)

Иначе

swap(root, rightChild(root)) ! Обмениваем значения корня и правого дочернего узла

root := rightChild(root)

Конец если

Конец цикла

Конец процедуры

Процедура leftChild<вх: n: индекс узла в массиве>

! Возвращает индекс левого дочернего узла

ответ := n * 2 + 1

Конец процедуры

Процедура rightChild<вх: n: индекс узла в массиве>

! Возвращает индекс правого дочернего узла

ответ := n * 2 + 2

Конец процедуры