Деревья

1 085
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 4,00 из 5)
Загрузка...
  • Название: Деревья (trees);
  • Применение: Способ хранения данных;
  • Время выполнения: Зависит от типа представления;
  • Сложность: Высокая;
  • Входные данные: Динамическая область памяти;
  • Результат: Представление данных в виде нелинейных (иерархических) отношений

Пример из жизни:

Необходимо отсортировать данные или найти элемент среди этих данных, например числа. Безусловно, можно воспользоваться существующими алгоритмами быстрой сортировки или бинарным поиском. Но есть один существенный недостаток, при добавлении новых данных необходимо по-новому сортировать массив и производить поиск элемента. Представьте, а если операции добавления новых элементов производятся очень часто (это рядовой случай добавления новых элементов в БД)? Надо каждый раз повторять операции сортировки или поиска (а может и того и другого вместе)? А что если предусмотреть такой способ хранения данных, при котором сортировка и поиск элемента выполнялись бы за достаточно короткое время.

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

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

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

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

Как показала практика с помощью бинарной или двоичной логики можно строить мощные вычислительные информационные системы и Ваш компьютер тому подтверждение. К чему идет разговор? Может и нам как-то упорядочить данные согласно такому принципу. Ведь посудите сами, всю информацию можно свести к этому. Например, если число больше,  то расположим его в правой части иерархии, если меньше — в левой части и т.д. При таком подходе действительно и поиск будет практически мгновенным, а сортировка уже заложена самой идеей! Круто! Вот мы и не заметили как стали использовать бинарную древовидную структуру. Посмотрим как это работает!

Все равно остается много вопросов! Если удалить число больше корневого, что надо делать в этом случае? перестраивать дерево заново? А если у  одного начальника больше двух подчиненных, что тоже не редкость? Давайте разбираться дальше. Для начала подойдем более формально к вопросу и определим базовые понятия такого типа структур, как деревья.

Определения:

Дерево (tree) — это математический способ представления данных (математическая абстракция) по совместительству абстрактный тип данных, который «нелинейно» связывает между собой объекты (узлы).  Что значит «нелинейные»? Как отмечалось ранее — это наличие определенного приоритета или «условной» иерархии одного элемента над другим, что делает элементы в определенной степени неравнозначными. Также говорят что дерево – это множество элементов, среди которых есть один выделенный который называется корнем, а остальные содержатся в N непересекающихся подмножествах, которые называются поддеревьями.

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

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

Родель (родительский узел) — у которого имеются исходящие узлы.

Потомок (дочерний узел) — у которого имеется хотя бы один родительский узел.

Рассмотрим основные свойства деревьев. Самое показательное и основное свойство это рекурсивная природа деревьев. А это значит что каждый узел можно рассматривать как корень, соотвественно принимая его дочерние узлы за «мини» дерево. Отсюда возникает новое понятие — поддерево.

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

Глубина узла — это длина пути от корня до узла (т.е. количество узлов). В свою очередь, глубина дерева — это длина пути от корня. На рисунке (значение глубины обозначены белыми цифрами) видно, что корень всегда имеет глубину 0 потому что он по определению не может быть дочерним элементом. У следующих узлов глубина = 1, потому что ровно существует одно ребро которое указывает на эти узлы и т.д.

Высота узла — количество ребер, ведущих от листового узла до заданного узла. На рисунке значение высоты различных узлов обозначены черными цифрами. Соотвественно, высота корня равна 3, потому что количество ребер, ведущих к корню от конечного терминального узла равно трем. Наоборот, высота листового узла = 0 т.к. он не содержит дочерних узлов.

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

Степенью узла (вершины) в дереве называется количество дуг или ребер, которое из нее выходит. Степень вершины корня = 2, степень вершины листового узла = 0 и т.д.

Осюда следует важное правило: высота дерева=высоте корня. Распространенной операцией, выполняемой над деревом принято считать обход. Существует три основных типа обхода деревьев, представлены на рисунке.

В зависимости от порядка расположения узлов в деревьях принято выделять разные деревья и производить над ними так называемое упорядочивание (т.е. приведение к какому-то виду).

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

Как правило, этот порядок «подкрепляется» присвоением чисел (по определенному правилу) каждому узлу , ведущему от родителя к потомку. В противном случае (если не существует никакого явно выраженного порядка), дерево считается неупорядоченным. Чаще всего алгоритмы имеют дело с упорядоченными деревьями. Обратите внимание в неупорядоченном дереве узлы могут быть пронумерованы в произвольном порядке.

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

В зависимости от заданных органичений бинарные деревья бывают разных типов:

 Двоичное дерево (Binary Tree)   Строгое двоичное дерево (Strictly Binary Tree)  Полное бинарное дерево (Complete Binary Tree)
Общий случай бинарного дерева, в котором вершина должна иметь не более двух потомков Все узлы кроме листовых имеют ровно два потомка (обязательное условие). Красным добавлены вторые потомки  Все узлы кроме листовых заполнены (обязательное условие) и это заполнение происходит слева (дерево растет слева тоже обязательное условие)

Наиболее общие свойства деревьев:

Итак, перечислим еще раз основные свойства деревьев:

  1. Каждое дерево обладает по крайней мере одним узлом — этот узел называется корневым;
  2. Каждый корень имеет ноль или более потомков;
  3. Каждый дочерний узел имеет так же ноль или больше потомков;

В бинарном дереве добавляются еще два условия:

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

Основные математические свойства:

  1. Максимальное количество узлов на i-уровне = 2;
  2. Максимальное количество узлов в дереве высотой  h = 20+21+22+…+2=2h+1-1;
  3. Высота h = log(n+1)-1

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

Балансировка — операция по уплотнению дерева путем минизации высоты дерева или поддерева. Сбалансированное дерево — это дерево у которого разница в высоте между правым и левым поддеревом не превышает какое-то заданное значение (обычно=1).

Сбалансированные деревья бывают разных типов, которые зависят от реализации балансировки. Давайте кратко рассмотрим основные типы и реализованные в них способы балансировки:

Красно черное дерево (Red-Black-Tree, RB-Tree)   АВЛ дерево (AVL-Tree) Расширяющееся дерево (SPLAY-Tree)
В этой структуре баланс достигается за счет поддержания раскраски вершин в два цвета (красный и черный, как видно из названия), подчиняющейся следующим правилам:

  1. Красная вершина не может быть дочерней по отношению к красной вершины;
  2. Черная глубина любого листа одинакова (черной глубиной называют количество черных вершин на пути из корня);
  3. Корень дерева черный;
  4. Указанные результаты достигаются за счет вращения поддеревьев (левого и правого);
В этой структуре баланс достигается за счет того, что для каждой его вершины высота её двух поддеревьев различается не более чем на 1:

  1. Каждому узлу назначется дополнительная информация в виде разности высот правого и левого поддеревьев;
  2. В случае разницы высот левого и правого поддеревьев = 2 производится балансировка дерева;
  3. Изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет;
  4. Указанный результат получается путем вращения поддерева данной вершины.
В этой структуре баланс достигается за счет каждого обращения, даже поиска, после чего splay-дерево меняет свою структуру:

  1. После обращения к любой вершине, она поднимается в корень.
  2. Подъем реализуется через повороты вершин.
  3. За один поворот, можно поменять местами родителя с дочерним узлом, как показано на рисунке ниже;
  4. Используются специальные техники поворота — zig-zig и zig-zag поворотов.

 

Реализация:

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

Возможна реализация через классы, тогда определяется класс бинарного дерева, в котором как правило указывается три поля: поле данных, указатель на левое поддерево, указатель на правое поддерево. Реализуется конструктор, который принимает новое значение узла.

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

Добавление узла

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

Порядок действий: 1. Проверка есть ли корень. Если нет, то новый узел становится корнем. 2. Если есть, то производится сравнение с корнем если > то идем в правое поддерево < в левое. 3. Повторяем шаг 2 пока не найдем листовой узел. 4. Если листовой узел > добавляемого, то вставляем его в правое сторону, если меньше то в левую сторону. Если узел равен текущему обычно предусматривается правило добавления его в правое (или левое) поддерево

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

Например, если мы удаляем корень — мы не можем удалить все дерево. Из-за этого возникают некоторые трудности. Ниже указаны три случая, которые могут возникнуть при удалении элемента дерева.

 Удаление узла без потомков   Удаление узла с одним потомком  Удаление узла с двумя потомками

При удалении узла у которого нет дочерних элементов — происходит обычное исключение этого элемент из иерархической структуры. В нашем случае происходит удаление левого листового узла

Порядок действий: 1. Поиск удаляемого узла. 2. Проверка наличия потомков. 3. Если потомков нет удаляем узел 

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

Порядок действий: 1. Поиск удаляемого узла. 2. Проверка наличия потомков. 3. Если имеется только один дочерний узел, то перезаписываем значение удаляемого узла на значение удаляемого узла.

При удалении узла с двумя потомками, необходимо определить наибольший узел в левом поддереве или наименьший в правом. Его значение присвоить удаляемому узлу и удалить.

Порядок действий: 1. Поиск удаляемого узла. 2. Проверка наличия потомков. 3. Если имеется два дочерних узла производим поиск самого большого значения в левом (самое меньшее в правом) поддереве. 4. Удаляем найденный узел и перезаписываем значение удаляемого узла.

Поиск: поиск элемента осуществялется по общему правилу бинарных деревьев — больше — «иди навлево», меньше — «иди направо»

 Поиск узла   Поиск минимального узла Поиск максимального узла

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

Порядок действий: 1. Начинаем сравнивать с корня, если > то идем в правое поддерево < в левое. 3. Повторяем шаг 1 пока не достигнем найденного узла. 

Поиск минимального узла производится последовательным переходом во все левые узлы т.е. от корня до левого узла, далее опять до левого и так до конечного левого листового узла.

Порядок действий: 1. От корня ищем в левом поддереве. 2. В левом поддереве ищем левое поддерево. 3. Повторяем 2 шаг до листового узла.

Поиск максимального узла производится последовательным переходом во все правые узлы т.е. от корня до правого узла, далее опять до правого и так до листового узла.

Порядок действий: 1. От корня ищем в правом поддереве. 2. В правом поддереве ищем правое поддерево. 3. Повторяем 2 шаг до правого листового узла.

Сортировка (симметричный обход): 

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

Порядок действий: 1.  Рекурссивный обход сначала всех левых поддеревьем, затем правых. Значения сохраняются в стеке.

Программная разработка:

При реализации узла в программе или скрипте, как правило, используют динамическую область памяти (в виде класса). В нашем случае, будем использовать классы. Создадим класс узла, назовем его Item. Существует, по крайней мере, три свойства этого класса (хранимые данные в узле ($data), принадлежность узла к левой стороне поддерева ($left), принадлежность узла к правому поддереву ($right)). И напишем конструктор, который будет вызываться при создании объекта.

Создадим класс BST, в котором реализуем базовый функционал бинарного дерева поиска. При создании дерева необходимо предусмотреть начальную инициализацию корня ($root) строки 3-5. Создадим метод добавления узла в дерево (addItem). При добавлении нового узла, необходимо проверить наличие корня, если корень не содержить значения, то необходимо создать новый узел и назначить его корнем (строки 8-11). В противном случае вызвать метод рекурсивного добавления узла (addTree). Рассмотри его подробней.

Данный метод принимает узел и значения узла. Обход дерева начинается с корня до конечного листового узла. Таким образом, если добавляемые данные меньше, значения текущего узла, то совершаем обход вправо, если больше- влево. При этом каждый узел обладает соотвествующими свойствами ($node->left или $node->right). Совершаем рекурсию до конечного узла в данном случае строки 5-10 (левое поддерево) и 20-25 (правое поддерево).

Метод удаления производит поиск узла, который необходимо удалить. Таким образом, возможны три варианта: узел найден (6-47), совершается обход вправо (48-51), совершается обход влево (52-55).

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

Поиск значения узла производится на основе базового свойства бинарного дерева. Последовательно сравнивается значение узлов, если значение меньше, то производим поиск в левом поддереве, если больше в правом. Для этого формируем цикл 17-26 и последовательно производим извлечение правого или левого поддерева на 17 строке.

Метод симметричного обхода производит последовательный обход узлов от самого наименьшего до самого наибольшего. Все значения обхода сохраняются в массив значений. Данный способ обход реализован на основе рекурсивного обхода сначала всех левых узлов, затем всех правых.

Время выполнения

  • Поиск — среднем O(log n), худшем — O(n);
  • Вставка — среднем O(log n), худшем — O(n);
  • Удаление — среднем O(log n), худшем — O(n).
Список источников
Поделиться

Отправить ответ

avatar
wpDiscuz