18. Бинарные деревья . Начало | Структуры данных

18. Бинарные деревья . Начало | Структуры данных сад и огород
дерево 0 и 1 информатика

Бинарные деревья . Начало

В этом уроке рассматривается новая тема. – бинарные деревья . Что это такое; Предположим, вам нужно хранить и обрабатывать иерархические данные в программе. структуры Например, такие данные, как семейные деревья. или структура Каталог, файлы и т. д.

18. Бинарные деревья . Начало | Структуры данных

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

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

Структура бинарного дерева

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

18. Бинарные деревья . Начало | Структуры данных

Каждая вершина такого дерева содержит как минимум три поля

  • Data — данные, хранящиеся в вершине дерева,
  • Left — ссылка (индекс) на потомка слева,
  • Right — ссылка (индекс) на потомка справа.

Ссылки также могут быть добавлены к родительским узлам. Однако в большинстве случаев эти три поля ограничены. Корневой индекс ведет к вершине дерева, называемой корнем. Именно через этот индекс выполняется вся работа с бинарным дерева: добавление/удаление элементов — проходит через все узлы дерева. Другими словами, он может быть передан от корневого узла к любому другому узлу дерева. В этом случае количество узлов, через которые нужно пройти, чтобы достичь узла, определяет уровень дерева. Если дерево не содержит узлов, то root = null; а если у узла нет левых или ближайших потомков, то соответствующий индекс получает нулевое значение.

Добавление вершин в бинарное дерево

Теперь давайте посмотрим, как можно сформировать бинарное дерево, то есть добавить новый узел. Обычно новый узел добавляется в свободный индекс (то есть в тот, который получает нулевое значение), начиная Из корня. Это означает, что первый узел всегда добавляется в корень, без каких-либо других вариантов. Затем он решает, какой узел добавить — левый или правый. Строго говоря, здесь нет никаких ограничений. Добавление дополнений может быть очень разным в зависимости от поставленной задачи. Например, если нужно сформировать родословное дерево, очевидно, что узлы должны показывать последовательность потомков. Нулевой уровень — несколько человек — первый уровень — мама, папа — второй уровень — бабушка, дедушка и т. д. Однако вершины бинарного в дереве хранятся данные, которые можно сравнить с большим или меньшим (например, числа), а добавление новых узлов происходит по правилам.

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

Предположим, например, что вы сохраняете в узле бинарного Числа в дереве являются целыми числами. Также добавьте к цене последующие узлы. Первое значение 10 добавляется к узлу. Следующее значение — 5. Посмотрите на корень; 5 меньше 10. В таком случае, согласно нашему правилу, это значение должно быть записано в левой ветви. Сформируйте новый узел с ценой 5. Следующее значение — 7. Снова от корня дерева. 7 меньше 10, поэтому мы переносим его в левую ветвь. Здесь у нас есть узел с ценой 5, а так как 5 больше 7, нам нужно добавить 7 к узлу 5 как к правому узлу дерева. Тогда получится число 16. как правый узел корневого узла. Затем находится число 13, большее, чем 13, но меньшее, чем 16. Следовательно, левый узел должен быть добавлен к узлу 16. Следующее значение 2 меньше 10 и меньше 5. Узел 5 и последнее значение 20 являются самыми большими и, следовательно, правыми узлами дерева.18. Бинарные деревья . Начало | Структуры данныхПри таком подходе к формированию бинарного дерева есть узлы с меньшими значениями, чем узлы в левой ветви, и с большими ценами, чем узлы в соответствующей отрасли. Затем этот вывод применяется к выбранному разделу активов, например

Поиск значений в бинарном дереве

Хорошо, но что это нам дает? Видите ли, вот несколько интересных последствий попадания в игру: во-первых, это ускоряет поиск определенной цены. Например, нам нужно определить, входит ли число 2 в последовательность чисел 10, 5, 7, 16, 13, 2 и 20. o (n), где n — количество элементов в таблице. Нужно найти все элементы в последовательности и сравнить цену с числом 2. Противоположность. в бинарном Дерево немного отличается и в среднем работает быстрее. Изначально число 2 сравнивается с 10 предметами, поэтому оно проходит по левому сектору с менее чем 10 узлами. В результате группы подходящих элементов, цена которых не равна 2, сразу перехватываются. Это ускоряет поиск. Далее сравниваем 2 с 5. 2 меньше 5, поэтому снова проходим по левой ветке. Найдите заданную цену. Как видите, для поиска числа 2 потребовалось всего три сравнения. в бинарном Дерево. Начиная с большой позиции, среднее количество операций, необходимых для нахождения искомого значения, составляет. Это гораздо быстрее, чем линейный поиск в таблице или связном списке. Рассмотрим работу алгоритма в случае, если искомое значение в бинарном отсутствует в дереве. Например, это число 11. Очевидно, что сначала нужно перейти на правую ветвь в точке пересечения 16 с левой ветвью и достичь узла листа 13. Впоследствии в дереве не будет узла, в котором не было бы найдено ни одного значения. Следовательно, число 11 в дереве не существует. В качестве альтернативы можно привести такой пример. Необходимо найти число 5. Оно хранится в промежуточном узле. Поэтому, как только оно будет достигнуто, дальнейший процесс поиска прерывается. Цена прерывается. Вот принципы поиска верхней цены бинарного дерева.

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

Внимательный зритель сейчас может возразить и сказать, что у нас все очень хорошо, потому что мы привели примеры «красивых бинарного дерево на самом низком уровне (всего два):18. Бинарные деревья . Начало | Структуры данныхНо если числа в древовидном образовании идут в другом порядке: 2, 5, 7, 10, 13, 16, 20 или уменьшенном: 20, 16, 13, 10, 7, 5, 2 то деревья они будут сильно отличаться:18. Бинарные деревья . Начало | Структуры данныхФактически, они вырождаются в один связный список, и объем вычислений для поиска в нем конкретного значения составляет O(n). Как и в обычных таблицах и связанных списках. Большего выигрыша нет. Такие вырождения. деревья (и подобные им) называются несбалансированными. В отличие от первого случая, этот относится к сбалансированным. В общем случае, если поддеревья от вершины отличаются только на один уровень, дерево называется сбалансированным. И они находятся на сбалансированном дереве. деревьях Поиск значения вершины выполняется за минимальное количество шагов с вычислительной сложностью O(log n). Таким образом, на практике они стремятся построить деревья близкие к балансу. Для этого используются бинарные методы балансировки. деревьев Наиболее известными из них являются следующие

  • Дерево AVL, разработанное в 1968 году,
  • Красно-черное дерево, разработанное в 1972 году,
  • Расширяющееся дерево (Expanding Tree или Spray Tree), разработанное в 1983 году.

Может быть применен любой из этих методов в бинарном Дерево, которое вызывается при добавлении нового узла. В результате получается более сбалансированное дерево для любой последовательности входных данных. Эти темы не рассматриваются в данном уроке. Если вам интересно, вы можете легко найти дополнительную информацию об этих методах в Интернете. Следует лишь отметить, что если известно, что в решаемой задаче данные (значения) поступают в случайном порядке, то в среднем будет сформировано дерево, более близкое к сбалансированному. бинарное Дерево, близкое к сбалансированному. На этом наше первое знакомство завершено. с бинарными Далее мы опишем алгоритм обхода и удаления узлов в дереве. бинарных деревьев . Курс по структурам Данные: https://stepik. org/a/134212

Оцените статью