Как обойти бинарное дерево

Как обойти бинарное дерево

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

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

Обход в прямом порядке

Каждый узел посещается до того, как посещены его потомки.

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

Посетить узел Обойти левое поддерево Обойти правое поддерево

Примеры использования обхода:

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

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

Посещаем сначало левое поддерево, затем узел, затем — правое поддерево.

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

Обойти левое поддерево Посетить узел Обойти правое поддерево

Обход в обратном порядке

Узлы посещаются ‘снизу вверх’.

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

Обойти левое поддерево Обойти правое поддерево Посетить узел

Примеры использования обхода:

• анализ игр с полной информацией
• разузлование снизу
• динамическое программирование

Обход в ширину

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Для реализации используется структура queue — очередь с методами

• enqueue — поставить в очередь
• dequeue — взять из очереди
• empty — возвращает TRUE, если очередь пуста, иначе — FALSE

q.enqueue(root); // корень в очередь while (! q.empty) < x = q.dequeue(); visit x; // посетить x if (! x.left.empty) // x.left - левое поддерево q.enqueue(x.left); if (! x.right.empty) // x.right - правое поддерево q.enqueue(x.right); >

Рекурсивные обходы можно, очевидно, организовать и с помощью стека, ‘развернув’ рекурсию.

Бинарное дерево. Способы обхода и удаления вершин

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

p = root

и список из вершин текущего уровня в порядке слева-направо:

v = [p]

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

while v: vn = [] for x in v: print(x.data) if x.left: vn += [x.left] if x.right: vn += [x.right] v = vn

В результате, сначала будет выведено значение 7 корневого узла. Затем, сформирован список vn из двух узлов следующего уровня в порядке слева-направо. После этого списку v присваивается новый сформированный список vn следующего уровня и на следующей итерации цикла while во вложенном цикле for будут перебираться уже вершины первого уровня. На экран выведутся значения 2 и 5. Снова сформируется список vn из вершин следующего второго уровня. И на следующей итерации цикла while будут выведены значения 3, 4 и 6. После этого список vn окажется пустым, следовательно, список v также будет пустой и цикл while завершит свою работу. Вот пример реализации алгоритма перебора вершин бинарного дерева в ширину в самом простом варианте. При этом мы обходим по всем узлам дерева ровно один раз.

Алгоритм обхода в глубину

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

def show_tree(self, node): if node is None: return self.show_tree(node.left) print(node.data) self.show_tree(node.right)

С начальным вызовом от корневой вершины:

show_tree(root)

Как она работает? Мы начинаем двигаться от корневого узла. Если он существует, то вызывается та же самая функция для левого узла. В результате, мы как бы попадаем в ту же самую функцию, только параметр node теперь является ссылкой на узел со значением 3. Здесь выполняется та же самая проверка: если узел существует, то по рекурсии мы снова переходим к следующему левому узлу. Это узел со значением 2. Снова делается проверка на его существование и, так как он существует, переходим к следующему левому узлу. Теперь параметр node принимает значение None (на рисунке NULL), рекурсия завершается и мы возвращаемся к прежнему вызову с параметром node узла 2. Это значение отображается на экране и делается попытка пройти по правой ветви. Так как справа объектов нет, то вызов текущей функции завершается и мы попадаем в функцию уровнем выше с параметром node на узел 3. Это значение 3 выводится на экран и делается попытка пройти по правой ветви. Ее нет, поэтому мы возвращаемся на уровень выше, то есть, к корневому узлу со значением 5. Это значение выводится на экран и далее мы переходим к правой вершине 7. Снова вызывается рекурсивная функция с параметром node на узел 7 и делается попытка пройти по левой ветви. Там имеется вершина со значение 6. Она выводится на экран с возвратом к функции узла 7. Затем, отображаем эту семерку на экран и переходит к левому узлу со значением 8. Это значение также отображается, после чего все вызовы рекурсивных функций завершаются. В результате мы на экране увидим следующие значения, записанные в вершинах бинарного дерева: 2, 3, 5, 6, 7, 8 Вы можете подумать, что такой возрастающий порядок значений получился чисто случайно. Однако нет. Если у нас имеется бинарное дерево сформированное по правилу добавления меньших значений в левую ветвь, а больших – в правую, то при обходе дерева в глубину в порядке: левое поддерево (L); промежуточная вершина (N); правое поддерево (R) всегда будет образовываться возрастающая последовательность чисел. Сокращенно такой алгоритм в глубину получил название LNR и относится к симметричному типу обхода. А если пройти сначала по правой ветви, затем вывести значение промежуточной вершины, а после пройти по левой ветви, то получим убывающую последовательность значений в бинарном дереве: 8, 7, 6, 5, 3, 2 Такой алгоритм сокращенно называется RNL и также является одним из видов симметричного обхода. Комбинируя различные варианты обхода и отображения значений вершин можно получать самые разнообразные вариации алгоритмов обхода в глубину.

Удаление вершин бинарного дерева

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

Удаление листовых вершин

Самый простой случай, когда удаляется листовой узел дерева. Предположим, что это узел 23: Тогда, нам достаточно получить указатель p на родительский узел и указатель s на удаляемый узел. Сделать это очень просто, запоминая при обходе дерева предыдущую (родительскую) вершину и текущую. После этого ссылку, ведущую на удаляемый узел следует приравнять NULL и освободить память из под узла s:

p.left = NULL delete s

Все, листовой узел удален. Как видите, все достаточно просто.

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

Также относительно просто обстоит ситуация, когда у удаляемого узла имеется один потомок (слева или справа). Например, нам нужно удалить узел 5, у которого один потомок справа: Здесь мы также должны иметь два указателя: p – на родительскую вершину; s – на удаляемую вершину. Затем, исключаем из дерева удаляемую вершину 5, меняя связь от родительской вершины 20 к вершине 16 (которая идет после удаляемой):

p.left = s.right delete s

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

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

Несколько сложнее обстоит дело, когда у удаляемой вершины два потомка. Общая идея здесь такая. Сам узел не удаляется, меняется только его значение на новое. А новое берется как наименьшее из правой ветви. Например, если мы хотим удалить узел 5, то следует взять наименьшее значение 16 из правого поддерева. Записать его вместо 5, а листовой узел 16 просто удалить: Но это если справа расположен листовой узел. А что если справа имеется полноценное поддерево с множеством вершин? Как быть в такой ситуации? По сути, также. Идея алгоритма остается прежней. Выбираем узел с наименьшим значением 11 в правом поддереве, заменяем 5 на 11 и удаляем листовой узел 11: Но вершина с наименьшим значением в правом поддереве не всегда является листовой. Возможны и такие ситуации: Однако можно заметить, что у узла с наименьшим значением может быть только один потомок справа. А значит, его удаление будет выполняться по алгоритму удаления вершин с одним потомком. Например, рассмотрим второе дерево. Нам потребуется три указателя: t – на удаляемую вершину (то есть, вершину, у которой будет меняться значение); s – на вершину с наименьшим значением в правом поддереве; p – на родительскую вершину для вершины s: Затем, мы меняем значение вершины 5 на 11:

t.data = s.data

и производим удаление вершины 11 согласно алгоритму удаления вершин с одним потомком:

p.left = s.right delete s

В результате получаем дерево: Вот основные типовые варианты удаления вершин в бинарном дереве:

• удаление листового узла;
• удаление узла с одним потомком (правым или левым);
• удаление узла с двумя потомками.

На следующем занятии, в качестве примера, реализуем бинарное дерево на языке Python, чтобы вы во всех деталях понимали принцип его работы. Курс по структурам данных: https://stepik.org/a/134212

Двоичное(бинарное) дерево: создание и обход

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

В этой статье рассмотрим двоичное дерево, как оно строится и варианты обходов.

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

Дерево обычно рисуется сверху вниз.

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

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

Вторая особенность двоичного дерева, и основное правило его построения, заключается в том что левый потомок меньше текущего узла, а правый потомок больше. Отношение больше/меньше имеет смысл для сравниваемых объектов, например числа, строки, если в дереве содержатся сложные объекты, то для них берётся какая-нибудь процедура сравнения, и она будет отрабатывать при всех операциях работы с деревом.

Создание дерева, вставка

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

Попробуем вставить в это дерево элемент -1.

Из корня идем в левое поддерево, так как -1 меньше 3. Из узла со значением 1 также идём в левое поддерево. Но в этом узле левое поддерево отсутствует, вставляем в эту позицию элемент, создавая новый узел дерева.

Вставим в получившееся дерево элемент 3.5.

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

Если дерево не существует, то есть root равен null, то элемент вставляется в корень, после этого проводится вставка по описанному выше алгоритму.

Напишем класс для создания двоичного дерева:

// дополнительный класс для хранения информации узла class BinaryTreeItem < constructor(itemValue) < this.value = itemValue; this.left = null; this.right = null; >> const elementExistMessage = "The element has already in the tree"; class BinaryTree < // в начале работы дерево пустое, root отсутствует constructor() < this.root = null; >insertItem(newItem) < // создание нового узла дерева const newNode = new BinaryTreeItem(newItem); // проверка на пустой root, если пустой, то заполняем // и завершаем работу if (this.root === null) < this.root = newNode; return; >// вызов рекурсивного добавления узла this._insertItem(this.root, newNode); > _insertItem(currentNode, newNode) < // если значение в добавляемом узле // меньше текущего рассматриваемого узла if (newNode.value < currentNode.value) < // если меньше и левое поддерево отсутствует // то добавляем if (currentNode.left === null) < currentNode.left = newNode; >else < // если левое поддерево существует, // то вызываем для этого поддерева // процедуру добавления нового узла this._insertItem(currentNode.left, newNode); >> // для правого поддерева алгоритм аналогичен // работе с левым поддеревом, кроме операции сравнения if (newNode.value > currentNode.value) < if (currentNode.right === null) < currentNode.right = newNode; >else < this._insertItem(currentNode.right, newNode); >> // если элемент равен текущему элементу, // то можно реагировать по разному, например просто // вывести предупреждение // возможно стоит добавить проверку на NaN, // зависит от потребностей пользователей класса if (newNode.value === currentNode.value) < console.warn(elementExistMessage); >> > const binaryTree = new BinaryTree(); binaryTree.insertItem(3); binaryTree.insertItem(1); binaryTree.insertItem(6); binaryTree.insertItem(4); binaryTree.insertItem(8); binaryTree.insertItem(-1); binaryTree.insertItem(3.5); console.log(binaryTree); 

На скриншоте ниже то, какую информацию хранит в себе binaryTree :

Обход

Рассмотрим несколько алгоритмов обхода/поиска элементов в двоичном дереве.

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

Какие возможны варианты обхода (слово поддерево опустим):

• корень, левое, правое (preorder, прямой);
• корень, правое, левое;
• левое, корень, правое (inorder, симметричный, центрированный);
• левое, правое, корень (postorder, обратный);
• правое, корень, левое;
• правое, левое, корень.

Также используется вариант для обхода деревьев по уровням. Уровень в дереве — его удалённость от корня. Сначала обходится корень, после этого узлы первого уровня и так далее. Называется обход в ширину, по уровням, breadth first, BFS — breadth first search или level order traversal.

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

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

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

class BinaryTreeItem < constructor(itemValue) < this.value = itemValue; this.left = null; this.right = null; >> const elementExistMessage = "The element has already in the tree"; class BinaryTree < constructor() < this.root = null; >insertItem(newItem) < // . >inorder(handlerFunction) < // просто вызываем функцию с другими параметрами, // добавляя текущий обрабатываемый узел // в рекурсивные вызов this._inorderInternal(this.root, handlerFunction); >_insertItem(currentNode, newNode) < // . >_inorderInternal(currentNode, handlerFunction) < // если узла нет, то его обрабатывать не нужно if (currentNode === null) return; // порядок обхода, для каждого из поддеревьев: // 1. проваливаемся в левое поддерево // 2. вызываем обрабатывающую функцию // 3. проваливаемся в правое поддерево this._inorderInternal(currentNode.left, handlerFunction); handlerFunction(currentNode.value); this._inorderInternal(currentNode.right, handlerFunction); >> const binaryTree = new BinaryTree(); binaryTree.insertItem(3); binaryTree.insertItem(1); binaryTree.insertItem(6); binaryTree.insertItem(4); binaryTree.insertItem(8); binaryTree.insertItem(-1); binaryTree.insertItem(3.5); binaryTree.inorder(console.log); // вызов inorder(console.log) выведет // -1 // 1 // 3 // 3.5 // 4 // 6 // 8 

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

Рассмотрим inorder алгоритм обхода на примере дерева, созданного в предыдущем блоке кода.

// 1 this._inorderInternal(currentNode.left, handlerFunction); // 2 handlerFunction(currentNode.value); // 3 this._inorderInternal(currentNode.right, handlerFunction); 

Сначала мы спустимся в самое левое поддерево — узел -1. Зайдем в его левое поддерево, которого нет, первая конструкция выполнится, ничего не сделав внутри функции. Вызовется обработчик handlerFunction , на узле -1. После этого произойдёт попытка войти в правое поддерево, которого нет. Работа функции для узла -1 завершится.

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

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

Аналогично продолжая рассуждения, и запоминая на какой строке для определенного узла мы вошли в рекурсивный вызов, можем пройти алгоритм «руками», лучше понимая его работу.

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

class BinaryTreeItem < constructor(itemValue) < this.value = itemValue; this.left = null; this.right = null; >> const elementExistMessage = "The element has already in the tree"; class BinaryTree < constructor() < this.root = null; >insertItem(newItem) < // . >breadthFirstHandler(handlerFunction) < if (this.root === null) return; // массив, в который будем добавлять элементы, // по мере спускания по дереву const queue = [this.root]; // используем позицию в массиве для текущего // обрабатываемого элемента let queuePosition = 0; // можем убирать обработанные элементы из очереди // например функцией shift // для обработки всегда брать нулевой элемент // и завершать работу, когда массив пуст // но shift работает за линейное время, что увеличивает // скорость работы алгоритма // while (queue.length >0) < // const currentNode = queue.shift(); while (queuePosition < queue.length) < // текущий обрабатываемый элемент в queuePosition const currentNode = queue[queuePosition]; handlerFunction(currentNode.value); // добавляем в список для обработки дочерние узлы if (currentNode.left !== null) < queue.push(currentNode.left); >if (currentNode.right !== null) < queue.push(currentNode.right); >queuePosition++; > > _insertItem(currentNode, newNode) < // . >> const binaryTree = new BinaryTree(); binaryTree.insertItem(3); binaryTree.insertItem(1); binaryTree.insertItem(6); binaryTree.insertItem(4); binaryTree.insertItem(8); binaryTree.insertItem(-1); binaryTree.insertItem(3.5); binaryTree.breadthFirstHandler(console.log); // вызов breadthFirstHandler(console.log) выведет // 3 корень // 1 узлы первого уровня // 6 // -1 узлы второго уровня // 4 // 8 // 3.5 узел третьего уровня 

Поиск

Операция поиска — вернуть true или false, в зависимости от того, содержится элемент в дереве или нет. Может быть реализована на основе поиска в глубину или ширину, посмотрим на реализацию на основе алгоритма обхода в глубину.

search(value) < return this._search(this.root, value); >_search(currentNode, value) < // дополнительные проверки, // обрабатывающие завершение поиска // либо проваливание в несуществующий узел // либо найденной значение if (currentNode === null) return false; if (currentNode.value === value) return true; // this._search проваливаются в дерево // когда поиск завершен // то по цепочке рекурсивных вызовов // будет возвращен результат if (value < currentNode.value) < return this._search(currentNode.left, value); >if (value > currentNode.value) < return this._search(currentNode.right, value); >> 

Функция сравнения или получение ключа

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

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

class BinaryTreeItem < constructor(itemValue) < this.value = itemValue; this.left = null; this.right = null; >> const elementExistMessage = "The element has already in the tree"; class BinaryTree < // параметр при создании дерева - // функция получения ключа // ключи должны быть сравнимы constructor(getKey) < this.root = null; this.getKey = getKey; >insertItem(newItem) < const newNode = new BinaryTreeItem(newItem); if (this.root === null) < this.root = newNode; return; >this._insertItem(this.root, newNode); > breadthFirstHandler(handlerFunction) < // . >_insertItem(currentNode, newNode) < // отличие во всех процедурах сравнения // вместо просто сравнивания value // перед этим применяем функцию получения ключа if (this.getKey(newNode.value) < this.getKey(currentNode.value)) < if (currentNode.left === null) < currentNode.left = newNode; >else < this._insertItem(currentNode.left, newNode); >> if (this.getKey(newNode.value) > this.getKey(currentNode.value)) < if (currentNode.right === null) < currentNode.right = newNode; >else < this._insertItem(currentNode.right, newNode); >> if (this.getKey(newNode.value) === this.getKey(currentNode.value)) < console.warn(elementExistMessage); >> > const getKey = (element) => element.key; const binaryTree = new BinaryTree(getKey); binaryTree.insertItem(< key: 3 >); binaryTree.insertItem(< key: 1 >); binaryTree.insertItem(< key: 6 >); binaryTree.insertItem(< key: 4 >); binaryTree.insertItem(< key: 8 >); binaryTree.insertItem(< key: -1 >); binaryTree.insertItem(< key: 3.5 >); binaryTree.breadthFirstHandler(console.log); 

Можно передать в конструктор специальную функцию сравнения. Эту функцию можно сделать как обычно делают функции сравнения в программировании, возвращать 0, если ключи равны. Значение больше нуля, если первый переданный объект больше второго, и меньше нуля если меньше. Важно не перепутать когда что возвращается и правильно передать параметры. Например, текущий узел, уже существующий в дереве, первым параметром, а тот, с которым производится текущая операция — вторым.

Для реализации такой возможности потребуется во всех местах сравнения использовать эту функцию

class BinaryTreeItem < constructor(itemValue) < this.value = itemValue; this.left = null; this.right = null; >> const elementExistMessage = "The element has already in the tree"; class BinaryTree < // в конструкторе передаем функцию сравнения constructor(compareFunction) < this.root = null; this.compareFunction = compareFunction; >insertItem(newItem) < const newNode = new BinaryTreeItem(newItem); if (this.root === null) < this.root = newNode; return; >this._insertItem(this.root, newNode); > breadthFirstHandler(handlerFunction) < // . >_insertItem(currentNode, newNode) < // вместо сравнения value // вызываем функцию сравнения // и проверяем больше или меньше нуля // получился результат сравнения if (this.compareFunction(currentNode.value, newNode.value) >0) < if (currentNode.left === null) < currentNode.left = newNode; >else < this._insertItem(currentNode.left, newNode); >> // текущий узел меньше нового, // значит новый узел должен быть отправлен // в правое поддерево if (this.compareFunction(currentNode.value, newNode.value) < 0) < if (currentNode.right === null) < currentNode.right = newNode; >else < this._insertItem(currentNode.right, newNode); >> if (this.compareFunction(currentNode.value, newNode.value) === 0) < console.warn(elementExistMessage); >> > const compare = (object1, object2) => < return object1.key - object2.key; >; const binaryTree = new BinaryTree(compare); binaryTree.insertItem(< key: 3 >); binaryTree.insertItem(< key: 1 >); binaryTree.insertItem(< key: 6 >); binaryTree.insertItem(< key: 4 >); binaryTree.insertItem(< key: 8 >); binaryTree.insertItem(< key: -1 >); binaryTree.insertItem(< key: 3.5 >); binaryTree.breadthFirstHandler(console.log); 

Заключение

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

Бинарные деревья — Алгоритмы на деревьях

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

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

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

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

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

Рассмотрим примеры деревьев на следующем рисунке:

Дерево (а) — бинарное. У каждого его узла не более двух дочерних узлов, у каждого из которых тоже не более двух дочерних. Например, узлы E, G, H, I и K — листовые, значит, у них ноль дочерних узлов. У узла C только один дочерний узел, а у узлов A, B, D и F по два дочерних.

Как только правило двух дочерних нарушается, то дерево перестает относиться к классу бинарных. Так, дерево (б) не является бинарным, так как у узла E три дочерних узла.

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

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

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

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

Что такое бинарные деревья поиска

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

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

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

. Это значительно меньше, если хранить значения в списках —

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

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

Рассмотрим на примере поиска элемента (10) сравнение операций поиска в отсортированном массиве, списке и бинарном дереве поиска:

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

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

Как бинарные деревья поиска реализуются в коде

Напомним свойства бинарных деревьев:

• Должно быть не более двух дочерних узлов
• Дочерние узлы тоже должны быть бинарными деревьями
• Дочерние узлы называют левыми и правыми

В этом случае структура узла принимает следующий вид:

class BinaryTreeNode  constructor(value, parent)  this.left = null; //ссылка на левый дочерний узел this.right = null; //ссылка на правый дочерний this.parent = parent; //ссылка на родителя this.value = value; //полезная нагрузка > >

class BinaryTreeNode  public BinaryTreeNode left = null; public BinaryTreeNode right = null; public BinaryTreeNode parent; public Object value; BinaryTreeNode(Object value, BinaryTreeNode parent)  this.parent = parent; this.value = value; > >

class BinaryTreeNode: def __init__(self, value, parent=None): self.left = None # ссылка на левый дочерний узел self.right = None # ссылка на правый дочерний узел self.parent = parent # ссылка на родителя self.value = value # полезная нагрузка

parent = $parent; $this->value = $value; > >

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

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

• Искать узел
• Вставлять узел
• Удалять узел
• Выполнять обход дерева

Разберем каждую операцию подробнее.

Поиск узла

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

function findNode(value) let node = this; while (node) if (value == node.value) return node; if (value  node.value) node = node.left; if (value > node.value) node = node.right; > return null; >

class BinaryTreeNode  // . BinaryTreeNode findNode(int value)  BinaryTreeNode node = this; while (node != null)  if (value == node.value)  return node; > if (value  node.value)  node = node.left; > if (value > node.value)  node = node.right; > > return null; > >

def find_node(root, value): node = self while node: if value == node.value: return node if value  node.value: node = node.left if value > node.value: node = node.right return None

value) < return $node; >if ($value < $node->value) < $node = $node->left; > if ($value > $node->value) < $node = $node->right; > > return null; > >

Вставка узла

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

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

Операция вставки использует рекурсивный подход аналогично операции поиска. Переведем данный алгоритм на язык JavaScript и получим следующий код метода вставки:

class BinaryTreeNode  insertNode(value) return this.#insertNode(value, this) > #insertNode(value, parentNode) if (value  parentNode.value) if (parentNode.left == null) parentNode.left = new BinaryTreeNode(value, parentNode); > else  this.#insertNode(value, parentNode.left); > > if (value > parentNode.value) if (parentNode.right == null) parentNode.right = new BinaryTreeNode(value, parentNode); > else  this.#insertNode(value, parentNode.right); > > > >

class BinaryTreeNode  // . public void insertNode(int value)  insertNode(value, this); > private void insertNode(int value, BinaryTreeNode parentNode)  if (value  parentNode.value)  if (parentNode.left == null)  parentNode.left = new BinaryTreeNode(value, parentNode); > else  insertNode(value, parentNode.left); > > if (value > parentNode.value) if (parentNode.right == null) parentNode.right = new BinaryTreeNode(value, parentNode); > else  insertNode(value, parentNode.right); > > > >

def insert_node(self, value): return self._insert_node(value, self) def _insert_node(self, value, parent_node): if value  parent_node.value: if parent_node.left is None: parent_node.left = BinaryTreeNode(value, parent_node) else: self._insert_node(value, parent_node.left) elif value > parent_node.value: if parent_node.right is None: parent_node.right = BinaryTreeNode(value, parent_node) else: self._insert_node(value, parent_node.right)

insertNode($value, $this); > public function insertNodeRecusive($value, ?BinaryTreeNode $parentNode = null) < $parentNode = $parentNode ?? $this; if ($value < $parentNode->value) < if ($parentNode->left == null) < $parentNode->left = new BinaryTreeNode($value, $parentNode); > else < $this->insertNodeRecusive($value, $parentNode->left); > > if ($value > $parentNode->value) < if ($parentNode->right == null) < $parentNode->right = new BinaryTreeNode($value, $parentNode); > else < $this->insertNodeRecusive($value, $parentNode->right); > > > >

Удаление узла

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

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

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

Оба варианта приемлемы для нашего дерева. Реализуем в коде второй вариант:

class BinaryTreeNode  removeNode(value)  return this.#removeNode(value, this) > #removeNode(value, node)  if (node == null) return null; if (value  node.value)  node.left = this.#removeNode(value, node.left); > else if (value > node.value)  node.right = this.#removeNode(value, node.right); > else  if (node.left == null) return node.right; if (node.right == null) return node.left; > let original = node; node = node.right; while (node.left) node = node.left; > node.right = this.#removeMin(original.right); node.left = original.left; > >

class BinaryTreeNode  // . public void removeNode(int value)  this.removeNode(value, this); > private BinaryTreeNode removeNode(int value, BinaryTreeNode node)  if (node == null)  return null; > if (value  node.value)  node.left = removeNode(value, node.left); > else if (value > node.value)  node.right = removeNode(value, node.right); > else if (node.left == null)  return node.right; > if (node.right == null)  return node.left; > > BinaryTreeNode original = node; node = node.right; while (node.left != null) node = node.left; > node.right = removeNode(original.right); node.left = original.left; return node.right; > >

def remove_node(self, value): return self._remove_node(value, self) def _remove_node(self, value, node): if node is None: return None if value  node.value: node.left = self._remove_node(value, node.left) return node elif value > node.value: node.right = self._remove_node(value, node.right) return node else: if node.left is None: return node.right elif node.right is None: return node.left else: original = node node = node.right while node.left: node = node.left node.right = self._remove_min(original.right) node.left = original.left return node

removeNodeRecursive($value, $this); > public function removeNodeRecursive($value, $node) < if ($node == null) < return null; >if ($value < $node->value) < $node->left = $this->removeNodeRecursive($value, $node->left); > elseif ($value > $node->value) < $node->right = $this->removeNodeRecursive($value, $node->right); > else < if ($node->left == null) < return $node->right; > if ($node->right == null) < return $node->left; > > $original = $node; $node = $node->right; while ($node->left != null) < $node = $node->left; > $node->right = $this->removeNodeRecursive($original->right); $node->left = $original->left; return $node->right; > >

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

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

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

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

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

• Прямой обход (КЛП): корень → левое поддерево → правое поддерево
• Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево
• Обратный обход (ЛПК): левое поддерево → правое поддерево → корень

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

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

class BinaryTreeNode  traverseRecursive(node)  if (node != null)  console.log(`node = $node.val>`); traverseRecursive(node.left); traverseRecursive(node.right); > > traverseWithStack()  let stack = []; stack.push(this); while (stack.length > 0)  let currentNode = stack.pop(); console.log(`node = $currentNode.val>`); if (currentNode.right != null)  stack.push(currentNode.right); > if (currentNode.left != null)  stack.push(currentNode.left); > > > traverseWithQueue()  let queue = []; queue.push(this.root); while (queue.length > 0)  let currentNode = queue.shift(); console.log(`node = $currentNode.val>`); if (currentNode.left)  queue.push(currentNode.left); > if (currentNode.right)  queue.push(currentNode.right); > > > >

class BinaryTreeNode  // . public void traverseRecursive()  traverseRecursive(this); > private void traverseRecursive(BinaryTreeNode node)  if (node != null)  System.out.println("node color: #000000;font-weight: bold">+ node.value); traverseRecursive(node.left); traverseRecursive(node.right); > > public void traverseWithStack()  DequeBinaryTreeNode> stack = new ArrayDeque<>(); stack.push(this); while (stack.size() > 0)  BinaryTreeNode currentNode = stack.pop(); System.out.println("node color: #000000;font-weight: bold">+ currentNode.value); if (currentNode.right != null)  stack.push(currentNode.right); > if (currentNode.left != null)  stack.push(currentNode.left); > > > public void traverseWithQueue()  DequeBinaryTreeNode> queue = new ArrayDeque<>(); queue.push(this); while (queue.size() > 0)  BinaryTreeNode currentNode = queue.removeFirst(); System.out.println("node" + currentNode.value); if (currentNode.left != null ) queue.push(currentNode.left); > if (currentNode.right != null)  queue.push(currentNode.right); > > > >

def traverse_recursive(node): if node is not None: print(f"node = node.value>") traverse_recursive(node.left) traverse_recursive(node.right) def traverse_with_stack(root): stack = [] stack.append(root) while len(stack) > 0: current_node = stack.pop() print(f"node = current_node.value>") if current_node.right is not None: stack.append(current_node.right) if current_node.left is not None: stack.append(current_node.left) def traverse_with_queue(root): queue = [] queue.append(root) while len(queue) > 0: current_node = queue.pop(0) print(f"node = current_node.value>") if current_node.left: queue.append(current_node.left) if current_node.right: queue.append(current_node.right)

traverseRecursiveInner($this); > private function traverseRecursiveInner($node) < if ($node != null) < echo "node = value>\n"; $this->traverseRecursiveInner($node->left); $this->traverseRecursiveInner($node->right); > > public function traverseWithStack() < $stack = new SplStack(); $stack->push($this); while (!$stack->isEmpty()) < $currentNode = $stack->pop(); echo "node = value>\n"; if ($currentNode->right != null) < $stack->push($currentNode->right); > if ($currentNode->left != null) < $stack->push($currentNode->left); > > > public function traverseWithQueue() < $queue = new SplQueue(); $queue->enqueue($this); while (!$queue->isEmpty()) < $currentNode = $queue->dequeue(); echo "node = value>\n"; if ($currentNode->left != null) < $queue->enqueue($currentNode->left); > if ($currentNode->right != null) < $queue->enqueue($currentNode->right); > > > >