Что такое бинарное дерево

Что такое бинарное дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

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

Способ представления бинарного дерева:

  • A — корень дерева
  • В — корень левого поддерева
  • С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.

Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

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

Остальные элементы – внутренние узлы (узлы ветвления).

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

Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

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

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Существует три способа обхода дерева:

  • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
  • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
  • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева

Узел дерева можно описать как структуру:

При этом обход дерева в префиксной форме будет иметь вид

Обход дерева в инфиксной форме будет иметь вид

Обход дерева в постфиксной форме будет иметь вид

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

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

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

    Переводы, 26 августа 2015 в 16:02

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

В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.

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

Для начала мы рассмотрим обычное дерево.

Деревья

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

Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный способ представления и хранения такой информации.

19 ноября 2019 – 10 января 2020, Гусев и онлайн, беcплатно

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

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

Двоичное дерево поиска похоже на дерево из примера выше, но строится по определенным правилам:

  • У каждого узла не более двух детей.
  • Любое значение меньше значения узла становится левым ребенком или ребенком левого ребенка.
  • Любое значение больше или равное значению узла становится правым ребенком или ребенком правого ребенка.
Читайте также:  Игры про марвел на пк список

Давайте посмотрим на дерево, построенное по этим правилам:

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

Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.

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

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

Рассмотрим подробнее первые шаги.

В первую очередь добавляется 8. Это значение становится корнем дерева. Затем мы добавляем 4. Поскольку 4 меньше 8, мы кладем ее в левого ребенка, согласно правилу 2. Поскольку у узла с восьмеркой нет детей слева, 4 становится единственным левым ребенком.

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

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым ребенком 2, согласно третьему правилу.

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

Класс BinaryTreeNode

Класс BinaryTreeNode представляет один узел двоичного дерева. Он содержит ссылки на левое и правое поддеревья (если поддерева нет, ссылка имеет значение null ), данные узла и метод IComparable.CompareTo для сравнения узлов. Он пригодится для определения, в какое поддерево должен идти данный узел. Как видите, класс BinaryTreeNode очень простой:

Класс BinaryTree

Класс BinaryTree предоставляет основные методы для манипуляций с данными: вставка элемента ( Add ), удаление ( Remove ), метод Contains для проверки, есть ли такое значение в дереве, несколько методов для обхода дерева различными способами, метод Count и Clear .

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

Метод Add

  • Поведение: Добавляет элемент в дерево на корректную позицию.
  • Сложность: O(log n) в среднем; O(n) в худшем случае.

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

  1. Дерево пустое.
  2. Дерево не пустое.

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

Метод Remove

  • Поведение: Удаляет первый узел с заданным значением.
  • Сложность: O(log n) в среднем; O(n) в худшем случае.

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

В целом, алгоритм удаления элемента выглядит так:

  • Найти узел, который надо удалить.
  • Удалить его.

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

Случай 1: У удаляемого узла нет правого ребенка.

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

Случай 2: У удаляемого узла есть только правый ребенок, у которого, в свою очередь нет левого ребенка.

В этом случае нам надо переместить правого ребенка удаляемого узла (6) на его место. После удаления дерево будет выглядеть так:

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

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

Давайте посмотрим, почему это так. Мы знаем о поддереве, начинающемся с удаляемого узла следующее:

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

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

Читайте также:  Загрузка сообщений из icloud

После удаления узла дерево будет выглядеть так:

Теперь, когда мы знаем, как удалять узлы, посмотрим на код, который реализует этот алгоритм.

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

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

Метод Contains

  • Поведение: Возвращает true если значение содержится в дереве. В противном случает возвращает false .
  • Сложность: O(log n) в среднем; O(n) в худшем случае.

Метод Contains выполняется с помощью метода FindWithParent , который проходит по дереву, выполняя в каждом узле следующие шаги:

  1. Если текущий узел null , вернуть null .
  2. Если значение теккущего узна равно искомому, вернуть текущий узел.
  3. Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
  4. В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

Поскольку Contains возвращает булево значение, оно определяется сравнением результата выполнения FindWithParent с null . Если FindWithParent вернул непустой узел, Contains возвращает true .

Метод FindWithParent также используется в методе Remove .

Метод Count

  • Поведение: Возвращает количество узлов дерева или 0, если дерево пустое.
  • Сложность: O(1)

Это поле инкрементируется методом Add и декрементируется методом Remove .

Метод Clear

  • Поведение: Удаляет все узлы дерева.
  • Сложность: O(1)

Обход деревьев

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

Пример дерева для обхода

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

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

Метод Preorder (или префиксный обход)

  • Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
  • Сложность: O(n)
  • Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8

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

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

Метод Postorder (или постфиксный обход)

  • Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
  • Сложность: O(n)
  • Порядок обхода: 1, 3, 2, 6, 8, 7, 5, 4

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

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

Метод Inorder (или инфиксный обход)

  • Поведение: Обходит дерево в инфиксном порядке, выполняя указанное действие над каждым узлом.
  • Сложность: O(n)
  • Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8

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

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

Метод GetEnumerator

  • Поведение: Возвращает итератор для обхода дерева инфиксным способом.
  • Сложность: Получение итератора — O(1). Обход дерева — O(n).

Продолжение следует

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

Заметки по программированию на C# .NET, Python, Java и Android программированию

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

Что такое бинарное дерево

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

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

Читайте также:  Как освободить место на айфон 5s

Для такого дерева должны выполняться следующие условия:

  1. Левое и правое поддерево так же являются бинарными деревьями;
  2. У всех узлов левого поддерева произвольного узла x значения ключей данных меньше значения ключа данных самого узла x ;
  3. У всех узлов правого поддерева произвольного узла x значения ключей данных больше либо равны значению ключа данных самого узла x .

Основные операции с бинарным деревом

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

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай):Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

  • Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
  • Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

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

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

  1. x — спускаемся в левое поддерево;
  2. x>5 — спускаемся в правое поддерево;
  3. x — спускаемся в левое поддерево;
  4. x>17 — спускаемся в правое поддерево;
  5. x=18 — мы нашли элемент.

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

Удаление элемента из бинарного дерева

Удаление листьев

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

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

  1. Указываем, что родителем элемента 17 теперь будет элемент 5.
  2. Указываем, что правым потомком элемента 5 теперь является элемент 17.

После удаления значений 31 и 20 дерево приобретает такой вид:

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

  1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
  2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево:Удалим элемент 35. Для этого:

  1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
  2. Ему же в качестве левого поддерева присваиваем элемент 34;
  3. Элементу 34 указываем нового родителя — 99;
  4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Получим такое дерево:

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

  1. Элементу 18 в качестве левого узла присвоим элемент 1;
  2. Элементу 1 присвоим 18 как родителя;
  3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
  4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

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

В своем коде я использовал нерекурсивный механизм удаления.

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

Поработать с классом можно следующим образом:

Получим такой вывод:

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

Код примерно такой же, только для C# он будет гораздо полезнее.

Ссылка на основную публикацию
Adblock detector