Бинарные деревья


Содержание

Бинарные деревья

Бинарное дерево Штерна-Броко — Дерево Штерна Броко способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева. В первом варианте построения дерева Штерна Броко дробь является корнем, а все прочие узлы заполняются по… … Википедия

Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия

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

Красно-черное дерево — Красно чёрное дерево Красно чёрное дерево (Red Black Tree, RB Tree) это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска:… … Википедия

Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… … Википедия

Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия

Бинарная диаграмма решений — (БДР) или программа с ветвлением является формой представления булевой функции от переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных ), каждый из которых имеет по два потомка, и двух… … Википедия

Код Хаффмена — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… … Википедия

Кодирование Хаффмана — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… … Википедия

Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ.&#1 … Википедия

Бинарные деревья

Читайте также:

  1. Двоичные (бинарные) деревья
  2. Двоичные упорядоченные деревья
  3. Кодовые деревья
  4. Красно-черные деревья
  5. Оптимальные деревья
  6. Понятие бинарные деревья. Операции над бинарными деревьями
  7. Сбалансированные по высоте деревья
  8. Случайные деревья
  9. Текстовые и бинарные файлы и файловые потоки
  10. Тема 15. Бинарные деревья

Бинарные деревья являются деревьями со степенью не более двух.

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

Рис.3. Бинарное дерево и его организация

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

· информационное поле (ключ вершины);

· служебное поле (их может быть несколько или ни одного);

· указатель на левое поддерево;

· указатель на правое поддерево.

По степени вершин бинарные деревья делятся на (рис. 4):

· строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);

· нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).

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

Рис.4. Виды бинарных деревьев

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

Бинарное дерево может представлять собой пустое множество. Бинарное дерево может выродиться в список (рис. 5).

Рис. 5. Список как частный случай бинарного дерева

Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, ‘*’ (звездочка). При этом сначала описываются левые потомки, затем, правые. Для структуры бинарного дерева, представленного на следующем рисунке 6, входной поток имеет вид: ABD*G***CE**FH**J**.

Рис. 6. Адресация в бинарном дереве

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

Описание бинарного дерева выглядит следующим образом:

адрес левого поддерева;

адрес правого поддерева;

где информационное поле – это поле любого ранее объявленного или стандартного типа;

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

int data;//информационное поле

int count; //служебное поле

point *left;//адрес левого поддерева


point *right;//адрес правого поддерева

Основными операциями, осуществляемыми с бинарными деревьями, являются:

· создание бинарного дерева;

· печать бинарного дерева;

· обход бинарного дерева;

· вставка элемента в бинарное дерево;

· удаление элемента из бинарного дерева;

· проверка пустоты бинарного дерева;

· удаление бинарного дерева.

Для описания алгоритмов этих основных операций используется следующее объявление:

int Data; //поле данных

BinaryTree* Left; //указатель на левый потомок

BinaryTree* Right; /указатель на правый потомок

BinaryTree* BTree = NULL;

Приведем функции перечисленных основных операций при работе с бинарным деревом.

//создание бинарного дерева

void Make_Binary_Tree(BinaryTree** Node, int n)<

BinaryTree** ptr;//вспомогательный указатель

while (*ptr != NULL) <

if ((double) rand()/RAND_MAX Left);

(*ptr) = new BinaryTree();

//печать бинарного дерева

void Print_BinaryTree(BinaryTree* Node, int l)<

//обратный обход бинарного дерева

void PostOrder_BinaryTree(BinaryTree* Node)<

//симметричный обход бинарного дерева

void SymmetricOrder_BinaryTree(BinaryTree* Node)<

//вставка вершины в бинарное дерево

void Insert_Node_BinaryTree(BinaryTree** Node,int Data) <

BinaryTree* New_Node = new BinaryTree;

BinaryTree** ptr = Node;//вспомогательный указатель

while (*ptr != NULL) <

double q = (double) rand()/RAND_MAX;

if ( (double) rand()/RAND_MAX Left = *ptr;

else New_Node->Right = *ptr;

//удаление вершины из бинарного дерева

void Delete_Node_BinaryTree(BinaryTree** Node,int Data)<

if ((*Node)->Data == Data)<

BinaryTree* ptr = (*Node);

else if ((*Node)->Left == NULL) (*Node) = ptr->Right;


else if ((*Node)->Right == NULL) (*Node) = ptr->Left;

Двоичное дерево поиска

Двоичное дерево поиска. Итеративная реализация.

Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.

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

Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.

Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.

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

ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.

Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.

Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.

Разберёмся со вставкой. Возможны следующие ситуации

  • 1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
  • 2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
  • 3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.

Пусть нам необходимо поместить в ДДП следующие значения

10 7 9 12 6 14 11 3 4

Первое значение становится корнем.

Второе значение меньше десяти, так что оно помещается слева.

Часть 7. Бинарные поисковые деревья (BST)

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Этот контент является частью серии: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Эта статья посвящена одной из разновидностей двоичных деревьев: бинарным поисковым деревьям. Как обычно будут рассмотрены теоретические алгоритмы для выполнения различных операций: вставка и удаление узла, поиск максимума/минимума и практические реализации данных алгоритмов на языках Си и Python.

Бинарные поисковые деревья

Бинарные поисковые деревья (англ. binary search tree или сокращенно BST) — это разновидность двоичного дерева, обладающая следующими отличительными свойствами:

  1. для каждого узла X (если X не равен NULL) все узлы в его левом поддереве содержат значения, которые ВСЕГДА меньше значения узла X.
  2. все узлы в правом поддереве узла Х содержат значения, которые соответственно ВСЕГДА больше значения узла X.
  3. каждый узел в таком дереве является родителем для своих поддеревьев.

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

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

Рисунок 1. Два варианта представления бинарного поискового дерева

В листинге 1 приведено объявление структур для узла бинарного дерева и самого дерева на языке Си.

Листинг 1. Определение структур для представления дерева и его узлов

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

Листинг 2. Функция для создания дерева

Вставка узла в бинарное поисковое дерево

Перед вставкой нового элемента в бинарное дерево обязательно нужно проверить, нет ли в нем уже такого элемента. Для этого необходимо начать обход дерева с корневого узла и проверить, не превосходит ли значение корневого узла добавляемого значения. Если корневой узел больше добавляемого элемента, то необходимо переместиться в левое дочернее дерево. В противном случае — в правое. Функция поиска определенного узла в дереве, приведенная в листинге 3, вернет 1 в случае, если искомое значение будет найдено, или , если указанное значение в дереве отсутствует.

Листинг 3. Функция для поиска узла в дереве

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

Листинг 4. Функция для вставки узла в бинарное поисковое дерево


Элемент, добавленный первым, автоматически становится корнем дерева. Функция может вернуть одно из 3-х значений: (при вставке произошла ошибка), 1 (узел успешно вставлен), 2 (такой элемент уже есть в дереве).

Удаление узла из бинарного поискового дерева

Функция удаления узла из бинарного дерева также будет возвращать , если возникла ошибка, или 1 в случае удачного удаления элемента. В данной функции используется уже знакомый алгоритм поиска, который будет искать элемент, помеченный для удаления. После того, как этот элемент будет обнаружен, возможны 3 варианта действий, которые представлены на рисунке 2.

Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева

В первом случае (вариант a) узел z имеет только левый дочерний узел, и при удалении он и будет заменен им. Во втором варианте (рисунок b) узел z заменяется узлом y.

В третьем варианте (рисунок с) корневой узел z заменяется узлом x, что приводит к дополнительным перестроениям в правом поддереве. Узел x становится преемником узла z, так как в левом поддереве узла z все узлы меньше 5, и преемника нужно искать в правом поддереве узла z.

Листинг 5. Функция для удаления узла из бинарного поискового дерева

Проход по дереву

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

Листинг 6. Функции для вывода содержимого дерева

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

Листинг 8. Нерекурсивная реализация обхода дерева

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

Удаление дерева

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

Листинг 9. Функции для удаления дерева

Нахождение минимума и максимума в бинарном поисковом дереве

В листинге 10 приведены две функции для поиска в дереве узлов с минимальным и максимальным значением. Минимальное значение нужно искать в левом поддереве корневого элемента, а максимальное — в правом.

Листинг 10. Функции для поиска минимального и максимальных значений

Определение типа двоичного дерева

Чтобы определить относится ли данное двоичное дерево к поисковым бинарным деревьям, можно использовать функцию из листинга 11.

Листинг 11. Определение типа двоичного дерева

Практическая реализация алгоритмов

В файле sources.zip, прикрепленном к данной статье, находятся две программы, в которых используются описанные выше алгоритмы для обработки бинарного поискового дерева. В файле bst_operations.с находится реализация на языке Си, а файл bst_operations.py содержит реализацию на языке Python.

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

Заключение

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

  1. если вставить в бинарное поисковое дерево числа в диапазоне от 1 до 64 в порядке возрастания таким образом, что сначала вставляются нечетные числа, потом четные, то какова будет высота этого дерева?
  2. если сначала вставить 3 числа: 32, 16, 48, а потом все остальные в прежнем порядке, то какова будет высота этого дерева?

Бинарные деревья

По книге Laszlo
«Вычислительная геометрия и компьютерная графика на С++»


Двоичные деревья

Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непуста, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.

Двоичное дерево на рис. 1а состоит из четырех внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В — непустой (содержит узел D), тогда как правый потомок узла В — пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других — на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 16 внешние узлы не показаны).

Основанная на генеалогии метафора дает удобный способ обозначения узлов внутри двоичного дерева. Узел р является родителем (или предком) узла n, если n — потомок узла р. Два узла являются братьями, если они принадлежат одному и тому же родителю. Для двух заданных узлов n1 и nk таких, что узел nk принадлежит поддереву с корнем в узле n1, говорят, что узел nk является потомком узла n1, а узел n1предком узла nk. Существует уникальный путь от узла n1 вниз к каждому из потомков nk, a именно: последовательность узлов n1 и n2. nk такая, что узел ni является родителем узла ni+1 для i = 1, 2. k-1. Длина пути равна числу ребер (k-1), содержащихся в нем. Например, на рис. 1а уникальный путь от узла А к узлу D состоит из последовательности А, В, D и имеет длину 2.

Глубина узла n определяется рекурсивно:

< 0 если n — корневой узел
глубина (n) = <
< 1 + глубина (родителя (n)) в противном случае

Глубина узла равна длине уникального пути от корня к узлу. На рис. 1а узел А имеет глубину 0, а узел D имеет глубину, равную 2.

Высота узла n также определяется рекурсивно:

< 0 если n — внешний узел
высота (n) = <
< 1 + max( высота(лев(n)), высота(прав(n)) ) в противном случае

где через лев(n) обозначен левый потомок узла n и через прав(n) — правый потомок узла n. Высота узла n равна длине самого длинного пути от узла n вниз до внешнего узла поддерева n. Высота двоичного дерева определяется как высота его корневого узла. Например, двоичное дерево на рис. 1а имеет высоту 3, а узел D имеет высоту 1.


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

Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.

Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:

TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:


Двоичные деревья поиска

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

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

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

Также очень полезны функции для обращения к элементам дерева поиска и воздействия на них. Такие функции обращения могут быть полезны для вывода на печать, редактирования и доступа к элементу или воздействия на него каким-либо иным образом. Функции обращения не принадлежат деревьям поиска, к элементам одного и того же дерева поиска могут быть применены различные функции обращения.


Класс SearchTree (дерево поиска)

Определим шаблон нового класса SearchTree для представления двоичного дерева поиска. Класс содержит элемент данных root, который указывает на корень двоичного дерева поиска (объект класса TreeNode) и элемент данных cmp, который указывает на функцию сравнения.

Для упрощения реализации предположим, что элементами в дереве поиска являются указатели на объект заданного типа, когда шаблон класса SearchTree используется для создания действительного класса. Параметр Т передается в виде типа указателя.

Конструкторы и деструкторы

Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:

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

Деструктор удаляет все дерево путем обращения к деструктору корня:

Поиск

Чтобы найти заданный элемент val, мы начинаем с корня и затем следуем вдоль ломаной линии уникального пути вниз до узла, содержащего val. В каждом узле n вдоль этого пути используем функцию сравнения для данного дерева на предмет сравнения val с элементом n->val, записанном в n. Если val меньше, чем n->val, то поиск продолжается, начиная с левого потомка узла n, если val больше, чем n->val, то поиск продолжается, начиная с правого потомка n, в противном случае возвращается значение n->val (и задача решена). Путь от корневого узла вниз до val называется путем поиска для val.

Этот алгоритм поиска реализуется в компонентной функции find, которая возвращает обнаруженный ею указатель на элемент или NULL, если такой элемент не существует в дереве поиска.

Этот алгоритм поиска можно сравнить с турниром, в котором участвуют некоторые кандидаты. В начале, когда мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.

Для нахождения наименьшего элемента мы начинаем с корня и прослеживаем связи с левым потомком до тех пор, пока не достигнем узла n, левый потомок которого пуст — это означает, что в узле n содержится наименьший элемент. Этот процесс также можно уподобить турниру. Для каждого узла n состав кандидатов определяется потомками узла n. На каждом шаге из состава кандидатов удаляются те элементы, которые больше или равны n->val и левый потомок n будет теперь выступать в качестве нового n. Процесс продолжается до тех пор, пока не будет достигнут некоторый узел n с пустым левым потомком и, полагая, что не осталось кандидатов меньше, чем n->val, и будет возвращено значение n->val.

Компонентная функция findMin возвращает наименьший элемент в данном дереве поиска, в ней происходит обращение к компонентной функции _findMin, которая реализует описанный ранее алгоритм поиска, начиная с узла n :

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

Симметричный обход

Обход двоичного дерева — это процесс, при котором каждый узел посещается точно только один раз. Компонентная функция inorder выполняет специальную форму обхода, известную как симметричный обход. Стратегия заключается сначала в симметричном обходе левого поддерева, затем посещения корня и потом в симметричном обходе правого поддерева. Узел посещается путем применения функции обращения к элементу, записанному в узле.

Компонентная функция inorder служит в качестве ведущей функции. Она обращается к собственной компонентной функции _inorder, которая выполняет симметричный обход от узла n и применяет функцию visit к каждому достигнутому узлу.

При симметричном обходе каждого из двоичных деревьев поиска, показанных на рис. 2, узлы посещаются в возрастающем порядке: 2, 3, 5, 7, 8. Конечно, при симметричном обходе любого двоичного дерева поиска все его элементы посещаются в возрастающем порядке. Чтобы выяснить, почему это так, заметим, что при выполнении симметричного обхода в некотором узле n элементы меньше, чем n->val посещаются до n, поскольку они принадлежат к левому поддереву n, а элементы больше, чем n->val посещаются после n, поскольку они принадлежат правому поддереву n. Следовательно, узел n посещается в правильной последовательности. Поскольку n — произвольный узел, то это же правило соблюдается для каждого узла.

Компонентная функция inorder обеспечивает способ перечисления элементов двоичного дерева поиска в отсортированном порядке. Например, если а является деревом поиска SearchTree для строк, то эти строки можем напечатать в лексикографическом порядке одной командой а.inorder(printstring). Для этого функция обращения printstring может быть определена как:

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

Включение элементов

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

Компонентная функция insert включает элемент val в это двоичное дерево поиска:

Удаление элементов

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

Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рис. 4:

  1. Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
  2. У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
  3. Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.

Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

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


Компонентная функция remove является общедоступной компонентной функцией для удаления узла, содержащего заданный элемент. Она обращается к собственной компонентной функции _remove, которая выполняет фактическую работу:

Параметр n (типа ссылки) служит в качестве псевдонима для поля ссылки, которое содержит ссылку вниз на текущий узел. При достижении узла, подлежащего удалению (old), n обозначает поле ссылки (в предке узла old), содержащее ссылку вниз на old. Следовательно команда n=old->_rchild заменяет ссылку на old ссылкой на правого потомка узла old.

Компонентная функция removeMin удаляет из дерева поиска наименьший элемент и возвращает его:

Древовидная сортировка — способ сортировки массива элементов — реализуется в виде простой программы, использующей деревья поиска. Идея заключается в занесении всех элементов в дерево поиска и затем в интерактивном удалении наименьшего элемента до тех пор, пока не будут удалены все элементы. Программа heapSort(пирамидальная сортировка) сортирует массив s из n элементов, используя функцию сравнения cmp:

Также доступна реализация двоичного дерева на Си с базовыми функциями. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в укзателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.

Поиск по бинарному дереву

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

Например, для набора чисел <7, 3, 5, 2, 8, 1,6, 10, 9, 4, 11>получится бинарное дерево (рис. 6.6). Для того чтобы правильно учесть повторения элементов, можно ввести дополнительное поле, которое будет хранить число вхождений для каждого элемента.

Рис. 6.6. Дерево двоичного поиска

Бинарное дерево, соответствующее бинарному поиску среди п записей, можно построить следующим образом: при п = 0 дерево сводится к узлу 0. В противном случае корневым узлом является [п/2], левое поддерево соответствует бинарному дереву с [п/2]—1 узлами, а правое — дереву с [п/2J узлами и числами в узлах, увеличенными на [п/2] (рис. 6.7).

Рис. 6.7. Бинарное дерево, соответствующее бинарному поиску

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

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

Пусть дано бинарное дерево поиска (рис. 6.8).

Требуется по бинарному дереву отыскать ключ SAG. При просмотре от корня дерева видно, что по первой букве латинского алфавита название SAG больше, чем САР. Следовательно, дальнейший поиск будет осуществляться в правой ветви. Это слово больше, чем PIS, — снова продвижение вправо; оно меньше, чем TAU, — продвижение влево; оно меньше, чем SCO, и отбирается узел 8. Таким образом, название SAG должно находиться в узле 8. При этом узлы дерева имеют структуру, показанную в табл. 6.1.

Структура узлов дерева

Указатель на левое поддерево

Указатель на правое поддерево

Пример. Пусть дано исходное множество ключей

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

Ац эл = [п/2] + 1, где п — число элементов множества.

Вершиной полевой ветке является центральный элемент левого подмножества, а по правой — правого подмножества и т.д. Отыскиваемый ключ К = 24. Исходное множество имеет 19 элементов. N л = [19/2] +1 = 10. Поиск ключа К = 24 по бинарному дереву от корня до листьев показан на рис. 6.9.

Преобразование произвольного дерева в бинарное. Упорядоченные деревья степени 2 называются бинарными деревьями. Бинарное дерево состоит из конечного множества элементов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями корня. Деревья, у которых d > 2, называются d-арными.

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

На рис. 6.10 показаны этапы такого преобразования некоторого Парного дерева в бинарное.

Рис. 6.10. Этапы преобразования J-арного дерева в бинарное

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

Сбалансированное бинарное дерево. Бинарное дерево называется сбалансированным (B-balanced), если высота левого поддерева каждого узла отличается от высоты правого не более чем на единицу (рис. 6.11).

Рис. 6.11. Пример сбалансированного дерева

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

Бинарные деревья поиска

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

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

Бинарным деревом поисканазывается такое бинарное дерево, у которого для каждой вершиныAвсе значения вершин левого поддереваAне превышают значенияA, а все значения вершин правого поддереваAне меньше, чем значениеA.

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

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

Опишем структуры данных для представления таблицы в виде бинарного дерева.

left, right: Tree;

Функция поиска по дереву со вставкой может в рекурсивном варианте выглядеть, как показано ниже.

Var t: Tree;

X: KeyType;

Var found: Boolean

if t = nil then begin

else if t^.key x then

TreeSearch := TreeSearch(t^.left, x, found)

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

Если функция выполнит вставку новой вершины, то исходное дерево изменится, однако оно сохранит свойства дерева поиска.

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

Максимальное число шагов спуска ограничено высотой дерева поиска. Как связана высота hс числом вершин дереваn? Это зависит от распределения вершин в дереве.

Наиболее предпочтительным для поиска видом деревьев являются идеально сбалансированные деревья (ИС-деревья). Это такие бинарные деревья, у которых для каждой вершины количества вершин в ее левом и правом поддеревьях различаются не больше, чем на 1. Легко доказать, что длины всех ветвей ИС-дерева также различаются не более, чем на 1.

Примеры ИС-деревьев поиска с разным числом вершин показаны на рис. 4.1.

Рис. 4.1. Примеры идеально сбалансированных деревьев поиска

Нетрудно доказать, что ИС-дерево высоты hможет иметь от2 h–1 до2 h – 1вершин. Отсюда можно получить и обратную зависимость – оценку высоты для данного числа вершин:h log2n + 1. Получается, что время поиска по ИС-дереву имеет логарифмическую оценку:T(n) = O(log(n)), аналогично бинарному поиску в сортированном массиве.

Проблема заключается в том, что сбалансированность дерева обеспечить трудно. Предположим, что на вход программы, строящей бинарное дерево поиска с помощью функции TreeSearch, поступает монотонно возрастающая последовательность ключей. Нетрудно видеть, что в этом случае каждая новая вершина будет включаться в дерево как правый сын предыдущей вершины, а левых сыновей в этом дереве не будет вовсе. Результатом будет крайне несбалансированноевырожденноедерево, по сути представляющее собой линейный список. Для вырожденного дерева его высота равна числу вершин, а стало быть,T(n) = O(n).

С другой стороны, пусть нам удалось каким-то образом построить ИС-дерево из nвершин. Если затем в это дерево будет добавлено еще хотя бы 1-2 вершины, то его балансировка может быть нарушена и для ее восстановления придется заново строить все дерево, затратив на это время порядкаO(n).

Таким образом, для несбалансированного дерева время порядка O(n)может тратиться на каждый поиск ключа, а для идеально сбалансированного аналогичное время будет затрачиваться на процедуру перебалансировки после добавления вершины.

Разумеется, вырожденное дерево – это заведомо худший случай. В среднем дело обстоит не так плохо. Доказано, что если вершины добавляются в случайном порядке, то математическое ожидание высоты получившегося дерева будет иметь логарифмическую оценку и лишь примерно на 40 % превысит высоту ИС-дерева с тем же количеством вершин.

Ситуация напоминает ту, которая характерна для алгоритма QuickSort: в среднем все очень хорошо, но не исключен и худший случай, когда все становится плохо.

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

Рис. 4.2. Удаление вершин из дерева поиска

На рис. 4.2, апоказано удаление вершиныA, не имеющей сыновей. Здесь проблем не возникает.

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

На рис. 4.2, впоказан самый сложный случай – удаление вершиныC, имеющей двух сыновей. Чтобы при этом не развалить дерево и сохранить его сортированность, поступают следующим образом. Для удаляемой вершины ищется ближайшая к ней слева вершина. Для этого нужно сначала перейти отCк ее левому сыну, а затем спускаться направо, пока не попадем в вершину, не имеющую правого сына. В данном примере это вершинаD. Далее следует поменять местами удаляемую вершинуCи ее левого соседаD(это можно сделать либо путем манипуляций указателями, либо просто обменяв записи таблицы, связанные с вершинами). На новом месте вершинаCимеет не более одного сына (ибо правого сына она не имеет), а потому может быть удалена, как в случаеаилиб. Легко видеть, что сортированность дерева не будет нарушена после этих операций.

Удаление вершин, как и их добавление, может нарушить сбалансированность дерева и в худшем случае привести к его вырожденности.

Можно ли при работе с бинарными деревьями поиска гарантировать оценку T(n) = O(log(n))для поиска и вставки не только в среднем, но и в худшем случае? Ответ положительный. Однако для этого следует выбрать подходящий класс деревьев. Для произвольных бинарных деревьев операция вставки выполняется просто и быстро, но поиск может быть долгим в случае вырождения. ИС-деревья гарантируют быстрый поиск, но много времени уходит на поддержание баланса при вставке и удалении. Желательно найти какой-то «средний» тип деревьев, чтобы они были не намного хуже, чем идеально сбалансированные, но вставка выполнялась значительно быстрее.

Было предложено несколько подобных типов деревьев. Среди них АВЛ-деревья [1, 5], 2-3-деревья [3, 5], красно-черные деревья [4]. Мы рассмотрим только АВЛ-деревья, которые были названы в честь предложивших их советских математиков Г.М.Адельсона-Вельского и Е.М.Ландиса и которые до настоящего времени остаются одним из лучших средств решения задачи поиска со вставкой.

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

Легко видеть, что всякое ИС-дерево поиска является АВЛ-деревом. Обратное, вообще говоря, неверно.

На рис. 4.3показаны примеры самых худших (т.е. наиболее разбалансированных, «перекошенных») АВЛ-деревьев для различных значений высоты. Как видно из рисунка, даже в худшем случае АВЛ-деревья далеки от вырожденности. Это становится все более заметно при увеличении высоты. Можно доказать, что высота АВЛ-дерева превышает высоту ИС-дерева с тем же количеством вершин не более, чем на 45 %. Таким образом, логарифмическая зависимость высоты от числа вершин сохраняется даже в худшем случае.

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

Рис. 4.3. Наихудшие АВЛ-деревья разной высоты

Прежде всего, надо выяснить, каким образом вообще обнаруживается нарушение сбалансированности при вставке. Наиболее удобное решение – хранить в каждой вершине АВЛ-дерева дополнительное поле bal(баланс), которое может принимать одно из трех значений:

t^.bal = –1, если левое поддерево вершиныtвыше, чем правое;

t^.bal = 0, если оба поддерева одинаковы по высоте;

t^.bal = +1, если правое поддеревоtвыше, чем левое.

При выполнении вставки сначала происходит рекурсивный спуск по дереву, затем новая вершина добавляется как лист (и для нее, естественно, устанавливается начальное значение bal= 0), а затем, в процессе возврата вверх, для всех вершин соответствующей ветви дерева выполняется корректировка значений поляbal, если вставка новой вершины вызвала увеличение высоты левого или правого поддерева.

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

Рис. 4.4. Нарушение баланса при вставке в АВЛ-дерево

Буквой Aобозначен левый сын вершиныC. Высота поддереваAмогла увеличиться либо при вставке в левое поддеревоA(случай 1), либо при вставке в правое поддерево (случай 2). Прямоугольники 1, 2, 3, 4 обозначают поддеревья произвольной сложности, а перечеркнутый квадрат – добавленную вершину. Во втором случае показаны два возможных положения добавленной вершины, одно из них – пунктиром. Можно доказать, что в случае 1 высоты поддеревьев 1, 2 и 3 равны одной и той же величинеh, а в случае 2 высоты поддеревьев 1 и 4 на единицу больше, чем 2 и 3.

Для восстановления баланса изображенные части дерева должны быть переставлены так, как показано на рис. 4.5.

Рис. 4.5. Восстановление баланса АВЛ-дерева


Такие преобразования АВЛ-дерева принято называть его поворотами.

Прежде всего заметим, что повороты не нарушают упорядоченность дерева поиска (например, в случае 1 и до поворота, и после него ключи в различных частях дерева упорядочены следующим образом: 1 A  2  C  3). При этом восстанавливается баланс вершин дерева.

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

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

Двоичное дерево.

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

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

В двоичном дереве есть только один узел, у которого нет предка, он называется корнем. Конечные узлы – листья. Если у корня отсутствует предок, то у листьев – потомки. Все вершины помимо корня и листьев называются узлами ветвления. Длина пути от корня до узла определяет уровень этого самого узла. Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него. Например, узлы F и L (рис. ниже) расположены на первом уровне, а U и B – на третьем.

Связный граф является деревом тогда и только тогда, когда PA=1, где P – количество вершин в графе, а A – количество ребер, поскольку в любом дереве с n вершинами, должно быть n-1 ребро. Это справедливо и для бинарного дерева, так как оно входит в класс деревьев. А увидеть отличительные признаки бинарного дерева, можно просто зная его определение. Достаточно взглянуть на рисунок 1, чтобы понять является ли изображенный на нем граф бинарным деревом.

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

Обозначим уровень символом k, а количество вершин n, тогда для бинарного дерева будет справедливо равенство n2 k , т. е. количество вершин на k-ом уровне не может иметь значение большее, чем степень двойки этого уровня. Для доказательства этого достаточно построить полное дерево, все уровни которого содержат максимально возможное для двоичного дерева количество вершин:

Продолжая построение, будем получать на каждом новом уровне число вершин равное k-ой степени двойки, а их общее количество вычисляется по формуле: Для рисунка 2 формула раскрывается так: 2 0 +2 1 +2 2 +2 3 =15.

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

  • обход в ширину;
  • прямой обход;
  • обратный обход;
  • симметричный обход;

Обход в ширину – это поуровневая обработка узлов слева на право. Работа метода заключается в просмотре всех вершин, начиная с некоторой вершины на n-ом уровне.

Возьмем нулевой уровень за начальный (рис. 2), и, начиная с вершины K, будем методом обхода в ширину поочередно двигаться вниз, просматривая вершины в следующем порядке: K A X T N H Q F U P L B J V Y.

Обход в прямом порядке вначале предполагает обработку узлов предков, а потом их потомков, то есть сначала посещается вершина дерева, далее левое и правое поддеревья, именно в описанном порядке. Для нашего дерева последовательность прямого обхода такая: K A T F U N P L X H B J Q V Y.

Обход в обратном порядке противоположен прямому обходу. Первыми осматриваются потомки, а уже затем предки, иначе говоря, первоначально обращение идет к элементам нижних уровней левого поддерева, потом то же самое с элементами правого, и в конце осматривается корень. Обратный обход дерева с рисунка 2: F U T P L N A B J H V Y Q X K.

Обход в симметричном порядке заключается в посещении левого узла, перехода в корень и оттуда в правый узел. Все для того же дерева узлы будут осмотрены в следующем порядке: F T U A P N L K B H J X V Q Y.

На практике используются не просто бинарные деревья, а их частные случаи, например, такие как двоичное дерево поиска, АВЛ-дерево, двоичная куча и другие.

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

суббота, 30 июля 2011 г.

Бинарные деревья

Существуют следующие разновидности бинарных деревьев:

  • полное(расширенное) бинарное дерево — каждый узел, за исключением листьев, имеет по 2 дочерних узла;
  • идеальное бинарное дерево — это полное бинарное дерево, в котором все листья находятся на одной высоте;
  • сбалансированное бинарное дерево — это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n — общее число узлов;
  • вырожденное дерево — дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
  • бинарное поисковое дерево (BST) — бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.

Вычисление путей
Путь — это расстояние от корня дерева до какого либо узла. Если число листьев полного бинарного дерева обозначить как S, а число остальных узлов обозначить как N, то справедлива формула:

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

а сумма внутренних путей будет равна:

и тогда будет справедлива формула:

Пример расширенного дерева

Можно сформулировать следующие задачи:

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

Давид Хаффман (David Huffman) предложил алгоритм для решения этой проблемы, в котором на каждом шаге выбираются и складываются два наименьших листа, как показано в листинге 1, что приводит к дереву, изображенному на рисунке ниже.

Бинарное дерево, построенное по алгоритму Хаффмана

Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:
Дальше, все функции расширяют класс Tree.

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

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

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

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

Сравнение бинарных деревьев
Вынесите её за пределы класса только)

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

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

  1. Дж. Макконнелл — Основы современных алгоритмов.
  2. Структуры данных: бинарные деревья. Часть 1
  3. Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
  4. Может быть полезным Обходы бинарных деревьев


Бинарное дерево — Binary tree

В информатике , бинарное дерево представляет собой дерево структура данных , в которой каждый узел имеет не более двух детей , которые переданы в качестве левого ребенка и правом ребенка . Рекурсивное определение с использованием только теории множеств понятий является то , что (непустое) бинарное дерево является кортеж ( L , S , R ), где L и R являются бинарные деревья или пустое множество , а S представляет собой набор синглтон . Некоторые авторы позволяют бинарное дерево быть пустое множество , а также.

Из теории графов перспективы, бинарные (и K-ичной) деревья , как определено здесь, на самом деле arborescences . Бинарное дерево таким образом , может быть также называется бифурцирующей древовидным -a термина , который появляется в некоторых очень старых книгах по программированию, до того , как современная наука терминология компьютера преобладала. Кроме того , можно интерпретировать , как бинарное дерево неориентированный , а не ориентированного графа , в этом случае бинарное дерево представляет собой приказ , корневое дерево . Некоторые авторы используют коренится бинарное дерево вместо бинарного дерева , чтобы подчеркнуть тот факт , что дерево с корнем, но , как определено выше, бинарное дерево всегда корни. Бинарное дерево представляет собой частный случай упорядоченного K-ичных дерева , где к равно 2.

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

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

  • Во- первых, как средство доступа к узлам на основе некоторого значения или метки , связанной с каждым узлом. Бинарные деревья , помеченные таким образом , используются для реализации бинарных деревьев поиска и бинарных куч , и используются для эффективного поиска и сортировки . Обозначение некорневыми узлов как левого или правого ребенка , даже когда есть только один ребенок представить дело в некоторых из этих приложений, в частности, имеет важное значение в бинарных деревьев поиска. Однако расположение отдельных узлов в дерево не является частью концептуальной информации. Например, в обычном двоичном дереве поиска размещение узлов почти полностью зависит от порядка , в котором они были добавлены, и может быть перестроено (например , путем балансировкой ) без изменения смысла.
  • Во- вторых, как представление данных с соответствующей структурой бифурцирующих. В таких случаях конкретное расположение узлов под и / или слева или справа от других узлов является частью информации (то есть, изменение было бы изменить значение). Типичные примеры встречаются с Хаффманом кодированием и кладограммами . Каждодневный разделение документов на главы, разделы, параграфы, и так далее является аналогичный пример с п-арной , а не бинарных деревьев.

содержание

Определения

Рекурсивные определения

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

  • пустое множество является расширенным бинарным деревом
  • если Т 1 и Т 2 вытянуты бинарных деревьев, то обозначим через T 1 • T 2 расширенное бинарное дерево , полученный добавлением корня г , подключенный влево , чтобы T 1 и вправо до Т 2 путем добавления краев , когда эти суб- деревья не пусты.

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

Используя понятия теории графов

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

Необходимо различие может быть сделано с помощью первого разделения края, то есть, определение двоичного дерева , как триплет (V, E 1 , E 2 ), где (V, E 1 ∪ E 2 ) является корневым деревом (эквивалентно древовидным) и E 1 ∩ E пусто, а также требует , чтобы для всех J ∈ <1, 2>каждый узел имеет не более одного Х J ребенка. Более неформальный способ сделать различие есть, цитируя Энциклопедию математики , что «каждый узел не имеет левого ребенка, правильного ребенка, ни, или оба» и указать , что эти «все разные» бинарных деревьев.

Типы бинарных деревьев

терминология Дерево не очень хорошо стандартизированы и поэтому варьируется в литературе.

  • Коренятся бинарное дерево имеет корневой узел и каждый узел имеет не более двух детей.
  • Полное бинарное дерево (иногда называют правильной или плоскости двоичного дерева) представляет собой дерево , в котором каждый узел имеет 0 или 2 детей. Другим способом определения полного двоичного дерева является рекурсивным определением . Полное бинарное дерево либо:
    • Одна вершина.
    • График формируется путем принимать два (полные) бинарных дерева, добавляя вершину, и добавляя край, направленный от новой вершины к корню каждого двоичного дерева.
  • В полном бинарном дереве каждый уровень, за исключением , возможно , последний , полностью заполнен, и все узлы в последнем уровне , как далеко влево , насколько это возможно. Он может иметь от 1 до 2 ч узлов на последнем уровне ч . Альтернативное определение является идеальным дерево, листья правый (возможно все) были удалены. Некоторые авторы используют термин полный вместо того, чтобы обратиться к совершенному бинарного дерева , как определено выше, в этом случае они называют этот тип дерева почти полное бинарное дерево или почти полное бинарное дерево. Полное бинарное дерево может быть эффективно представлено с использованием массива.
  • Совершенное бинарное дерево бинарное дерево , в котором все внутренние узлы имеют двух детей и все листья имеют одинаковую глубину или же уровень . Примером идеального бинарного дерева является родословная диаграмма человека на заданную глубину, так как каждый человек имеет ровно два биологических родителей (одна мать и один отец).
  • В бесконечном полном бинарном дереве, каждый узел имеет два детей (и , следовательно, множество уровней счетное ). Множество всех узлов счетно бесконечное, но множество всех бесконечных путей от корня несчетно, имеющая мощность континуума . Эти пути соответствуют по порядку , сохраняющей биекции к точкам множества Кантора , или (используя пример дерева Стерн-Броко ) к множеству положительных иррациональных чисел .
  • Сбалансированное бинарное дерево представляет собой бинарное дерево структуры , в которой левый и правый поддеревья каждого узла отличаются по высоте не более чем на 1. Можно также рассматривать бинарные деревья , где нет листьев не намного дальше от корня , чем любой другой лист. (Различные схемы балансировки позволяют различные определения «гораздо дальше».)
  • Вырожденный (или патологический ) дерево , где каждый родительский узел имеет только один дочерний узел , связанные. Это означает , что производительность мудрым, дерево будет вести себя как связанный список структур данных.

Свойства бинарных деревьев

  • Число узлов в полном бинарном дереве, по крайней мере , и в большинстве , где есть высота дерева. Дерево , состоящее только из корневого узла имеет высоту 0. N <\ Displaystyle п>N знак равно 2 час + 1 <\ Displaystyle п = 2h + 1>N знак равно 2 час + 1 — 1 <\ Displaystyle п = 2 ^ <Л + 1>-1> час
  • Число листьев узлов в идеальном бинарном дереве, это потому , что число не-листа ( так называемый внутренний) узлы . L <\ Displaystyle л>L знак равно ( N + 1 ) / 2 <\ Displaystyle л = (п + 1) / 2>N — L знак равно Σ К знак равно 0 журнал 2 ⁡ ( L ) — 1 2 К знак равно 2 журнал 2 ⁡ ( L ) — 1 знак равно L — 1 <\ Displaystyle п = \ сумма _ <к = 0>^ <\ _ войти <2>(л) -1> 2 ^ <к>= 2 ^ <\ _ войти <2>(л)> — 1 = л -1>
  • Это означает , что совершенное бинарное дерево с листьями имеет узлы. L <\ Displaystyle л>N знак равно 2 L — 1

  • В сбалансированном полном бинарном дереве, (см функция потолка ). час знак равно ⌈ журнал 2 ⁡ ( L ) ⌉ + 1 знак равно ⌈ журнал 2 ⁡ ( ( N + 1 ) / 2 ) ⌉ + 1 знак равно ⌈ журнал 2 ⁡ ( N + 1 ) ⌉ <\ Displaystyle ч = \ lceil \ Log _ <2>(л) \ rceil + 1 = \ lceil \ Log _ <2>((п + 1) / 2) \ rceil + 1 = \ lceil \ Log _ <2 >(п + 1) \ rceil>
  • В идеальном полном бинарном дереве, таким образом . L знак равно 2 час <\ Displaystyle л = 2 ^ <ч>> N знак равно 2 час + 1 — 1 <\ Displaystyle п = 2 ^ <Л + 1>-1>
  • Максимально возможное число нулевых ссылок (т.е., отсутствующих детей узлов) в полном бинарном дереве п узлов ( п + 1), где только один узел существует в нижнем уровне большинства в крайнее левое положение .
  • Количество внутренних узлов в полном бинарном дереве п узлов . ⌊ N / 2 ⌋ <\ Displaystyle \ lfloor п / 2 \ rfloor>
  • Для любого непустого бинарного дерева с п узлами листьев и п2 узлов степени 2, п = п2 + 1.

Комбинаторика

В комбинаторике один рассматривает проблему подсчета числа полных бинарных деревьев заданного размера. Здесь деревья не имеют значения , прикрепленные к их узлов (это было бы просто умножить число возможных деревьев с помощью легко определить фактор), и деревья отличаются только по своей структуре; однако левый и правый ребенок любого узла отличаются (если они разные деревья, то поменяв их будут производить дерево , отличное от исходного). Размер дерева берется число п внутренних узлов (те , с двумя детьми); другие узлы листовые узлы и есть п + 1 из них. Число таких бинарных деревьев объема п равно числу способов полностью в скобки строку п + 1 символов (представляющих листья) , разделенных п бинарных операторов (представляющих внутренние узлы), с тем чтобы определить аргумент подвыражения каждого оператор. Например , для п = 3 надо скобки строку типа , который можно пятью способами: Икс * Икс * Икс * Икс

( ( Икс * Икс ) * Икс ) * Икс , ( Икс * ( Икс * Икс ) ) * Икс , ( Икс * Икс ) * ( Икс * Икс ) , Икс * ( ( Икс * Икс ) * Икс ) , Икс * ( Икс * ( Икс * Икс ) ) ,

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

Существует уникальное бинарное дерево размера 0 (состоящих из одного листа), и любое другое бинарное дерево характеризуется парой левых и правых дети; если они имеют размеры I и J соответственно, полное дерево имеет размер я + J + 1 . Таким образом, число бинарных деревьев объема п имеет следующий рекурсивный описание , и для любого натурального п . Отсюда следует , что является каталонским числом индекса п . С N <\ Displaystyle C_ <п>> С 0 знак равно 1 <\ Displaystyle C_ <0>= 1> С N знак равно Σ я знак равно 0 N — 1 С я С N — 1 — я <\ Displaystyle \ TextStyle C_ = \ сумма _ <я = 0>^ C_ C_ > С N <\ Displaystyle C_ <п>>

Приведенные выше строки в скобках , не следует путать с множеством слов длиной 2 н в языке Dyck , которые состоят только из скобок таким образом , что они должным образом сбалансированы. Число таких строк удовлетворяет тому же рекурсивное описание (каждый Дейк слово длины 2 п определяются по Дейку подслово приложена первоначальный «(» и его соответствующей «)» вместе с ДЕЙКОМ подслово оставшимся после этого закрывающей скобки, чья длина 2 я и 2 J удовлетворяют я + J + 1 = п ); это число , следовательно , и каталонский номер . Таким образом , есть также пять Дейка слов длины 6: С N <\ Displaystyle C_ <п>>

Эти слова Дейка не соответствуют бинарных деревьев таким же образом. Вместо этого, они связаны следующим рекурсивно биекция: Дейк слово равно пустой строке соответствует бинарное дерево размера 0 только с одним листом. Любое другое Дейк слово можно записать в виде ( ) , где , сами по себе (возможно , пустой) Дейка слов и где два письменных Скобки совпадают. Биекция затем определяется, позволяя слова и соответствуют бинарных деревьев, которые левые и правые дети корня. вес 1 <\ Displaystyle w_ <1>> вес 2 <\ Displaystyle w_ <2>> вес 1 <\ Displaystyle w_ <1>> вес 2 <\ Displaystyle w_ <2>> вес 1 <\ Displaystyle w_ <1>> вес 2 <\ Displaystyle w_ <2>>

Взаимно однозначное соответствие также может быть определенно следующим образом : приложить слово Дейка дополнительной пару скобок, так что результат может быть интерпретирован как лисповское выражение списка (с пустым списком () , как только происходит атом); то пунктирная пара выражение для этого правильного списка является полностью выражением в скобках (с NIL как символ и «» в качестве оператора) , описывающее соответствующего двоичного дерево (которое на самом деле внутреннее представление надлежащего списка).

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

Способы хранения бинарных деревьев

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

Узлы и ссылки

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

Этот способ хранения бинарных дерев тратит справедливый бит памяти, так как указатели будут нулевыми (или точкой к часовому) более половины времени; более консервативны представление альтернатива резьбовая бинарное дерево .

В языках с мечеными союзами , такими как ML , узел дерева часто помеченное объединение двух типов узлов, один из которых представляет собой 3-кортеж данных, левого ребенок, а также право ребенок, а другой из которых является «лист «узел, который не содержит никаких данных и функции так же, как нулевое значение в языке с указателями. Например, следующая строка кода в OCaml (An диалектной ML) определяет бинарное дерево , которое хранит символ в каждом узле.

Массивы

Бинарные дерева также могут быть сохранены в ширину первого порядка, как неявная структура данных в массивах , а если дерево полного бинарного дерева, этот метод отходах нет пространства. В этом компактном устройстве, если узел имеет индекс я , его дети находятся в индексах (для левого ребенка) и (на право), в то время как его родитель (если таковой имеется ) по индексу (предполагается , что корень имеет нулевой индекс ). Этот метод извлекает выгоду из более компактного хранения и лучшей локальности ссылок , в частности , во время обхода. Тем не менее, это дорого выращивать и отходы пространства пропорциональна 2 чп для дерева глубины ч с п узлами. 2 я + 1 <\ Displaystyle 2i + 1>2 я + 2 <\ Displaystyle 2i + 2> ⌊ я — 1 2 ⌋ <\ Displaystyle \ \ влево lfloor <\ гидроразрыва <я-1><2>> \ право \ rfloor>

Этот способ хранения часто используется для бинарных куч . Нет свободного места впустую , поскольку узлы добавляются в ширину-первого порядка.

Кодировки

Краткие кодировки

Сжатое структура данных является одним который занимает близко к минимально возможному пространству, как установлено информационных теоретических нижних границ. Число различных бинарных деревьев на узлов , то й Каталонский номер (предполагая , что мы рассматриваем деревья с идентичной структурой , как идентичными). Для больших , это примерно ; Таким образом , нам нужно по крайней мере , о битах для кодирования его. Поэтому сжатое бинарное дерево будет занимать биты. N <\ Displaystyle п>С N <\ Displaystyle \ mathrm _ <п>> N <\ Displaystyle п>N <\ Displaystyle п>4 N <\ Displaystyle 4 ^ <п>> журнал 2 ⁡ 4 N знак равно 2 N <\ Displaystyle \ лог _ <2>4 ^ <п>= 2n> 2 N + о ( N )

Одно простое представление , которое соответствует этой оценке посетить узлы дерева в прямом порядке, вывод «1» для внутреннего узла и «0» для листа. [1] Если дерево содержит данные, мы можем просто одновременно хранить в последовательном массиве в предзаказа. Эта функция выполняет это:

Строка структура имеет только биты в конце концов, где есть число (внутренние) узлы; мы даже не должны хранить его длину. Для того, чтобы показать , что никакая информация не будет потеряна, мы можем преобразовать вывод обратно в исходное дерево , как это: 2 N + 1 <\ Displaystyle 2n + 1>N

Более сложные емкие представления позволяют не только компактное хранение деревьев, но даже полезных операций на этих деревьях прямо в то время как они все еще в своей краткой форме.

Кодирование общих деревьев в виде бинарных деревьев

Существует отображение один к одному между общим упорядоченных деревьев и бинарных деревьев, которые , в частности , используется Лиспе для представления генерала заказал деревьев в виде бинарных деревьев. Для того, чтобы преобразовать общее упорядоченное дерево бинарного дерева, нам нужно только представить общее дерево в левом ребенке правой родственным способе. Результат этого представления будет автоматически бинарное дерево, если смотреть с другой точки зрения. Каждый узел N в упорядоченном дереве соответствует узел в бинарном дереве; левый ребенок N « является узлом , соответствующий первым ребенком N , а правый ребенок является узлом , соответствующего N следующего собрата «s — то есть, следующим узел в порядке среди детей из родитель N . Это бинарное дерево представление общего дерева порядка иногда также называют левым ребенком правой родственным бинарного дерева (LCRS дерева), или дважды приковано деревом , или Филиал-Наследник цепи .

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

Так, например, в дереве на левой стороне, А имеет 6 детей . Он может быть преобразован в бинарном дереве справа.

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

(((NO), И.Я.) компакт-диска ((P), (Q)) Р (М))

которая будет реализована в памяти как бинарное дерево справа, без каких-либо букв на те узлы, которые имеют левую ребенка.

Общие операции

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

вставка

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

листовые узлы

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

Внутренние узлы

Вставка на внутренних узлах немного сложнее , чем на листовых узлах. Скажем , что внутренний узел является узлом А и что узел В является дочерним А. (Если вставки для вставки правильного ребенка, то В является правильным потомком A, а так же с левой вставки ребенка.) А передает свои ребенок в новом узел и новый узел присваивает его родитель A. Затем новый узел назначает свой ребенок B и B назначает свой родитель в качестве нового узла.

делеция

Удаление представляет собой процесс, посредством которого узел удаляется из дерева. Только некоторые узлы бинарного дерева могут быть удалены однозначно.

Узел с нуля или одного детей

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

Узел с двумя детьми

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

пересечение

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

Глубина первого порядка

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

Ширина-первый порядок

Контрастные с глубиной-первого порядка в ширину первого порядка, который всегда пытается посетить узел ближе к корню , что он еще не побывал. См поиска в ширину для получения дополнительной информации. Также называется обход уровня порядка .

В полном бинарном дереве, ширина-индекс узла ( я — (2 г — 1)) может быть использован в качестве инструкции обхода от корня. Чтение побитового слева направо, начиная с битовым г — 1, где d является расстоянием этого узла от корня ( d = ⌊log2 ( я + 1) ⌋) и данный узел не является сам корнем ( д > 0) , Когда ширина индекс маскируется в битовом г — 1, бит значения и 1 означают к шагу влево или вправо, соответственно. Процесс продолжается последовательно не проверяя следующий бит вправо до тех пор, пока не больше. Крайний правый бит указывает конечный обход от родительского узла нужного для самого узла. Существует много времени пространства компромисса между итерацией полным бинарного дерева таким образом , по сравнению с каждым узлом , имеющим указатель / с его родным братом / с.

Илон Маск рекомендует:  Что такое код asp cpuloggingmask

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL