Что такое бинарное дерево
Перейти к содержимому

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

  • автор:

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

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

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

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

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

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

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

Дерево (а) — бинарное. У каждого его узла не более двух дочерних узлов, у каждого из которых тоже не более двух дочерних. Например, узлы 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 # полезная нагрузка

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

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

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

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

Поиск узла

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

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(self, 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

Вставка узла

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

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

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

function insertNode(value) return #insertNode(value, this) > function #insertNode(value, 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); > > >
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)

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

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

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

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

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

function removeNode(value)  return #removeNode(value, this) > function #removeNode(value, 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; > let original = node; node = node.right; while (node.left) node = node.left; > node.right = #removeMin(original.right); node.left = original.left; >
class BinaryTreeNode  // . 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

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

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

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

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

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

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

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

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

function traverseRecursive(node)  if (node != null)  console.log(`node = $node.val>`); traverseRecursive(node.left); traverseRecursive(node.right); > > function 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); > > > function 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)

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

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

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

Двоичное дерево в первую очередь дерево. В программировании – структура данных, которая имеет корень и дочерние узлы, без циклических связей. Если рассмотреть отдельно любой узел с дочерними элементами, то получится тоже дерево. Узел называется внутренним, если имеет хотя бы одно поддерево. 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); 

Заключение

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

Следите за новыми постами по любимым темам

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

Бинарное дерево — что это? B-деревья

Статья расскажет о том, что такое бинарные деревья. Будут представлены способы их представления и основные термины. Отдельное внимание будет уделено B-дереву и его отличию от двоичных структур.

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

tree_1-1801-ce20a6.png

На что следует обратить внимание: — А — корень дерева; — B — корень левого поддерева и предок D; — С — корень правого поддерева; — D — потомок родительского узла B; если D располагается на уровне i, то B – на уровне i-1.

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

Использование

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

Способы обхода

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

tree2_2-1801-44cb3c.png

Есть 3 способа обхода: 1. Обход в прямом порядке — сверху вниз: A, B, C — префиксная форма. 2. Обход слева направо (симметричный порядок): B, A, C — инфиксная форма. 3. Обход снизу вверх (обратный порядок): B, C, A — постфиксная форма.

Реализация

На практике вершину древа можно описать в качестве структуры:

Screenshot_1-1801-d4f65b.png

Тогда обход в префиксной форме будет выглядеть следующим образом:

Screenshot_2-1801-e5f092.png

Теперь инфиксная форма:

Screenshot_3-1801-9f3cac.png

Screenshot_4-1801-44c7e8.png

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

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

Screenshot_5-1801-690117.png

Данные в каждой вершине должны обладать ключами, где определена операция сравнения “

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

Чтобы составить бинарное дерево поиска, пригодится функция добавления узла:

Screenshot_6-1801-1cf04e.png

Удаляем поддерево

Screenshot_7-1801-9af795.png

B-дерево. Поиск по B-дереву

В бинарном дереве поиска каждый узел содержит лишь одно значение (ключ) и не более 2-х потомков. Но существует особый вид древа поиска, называемый B-дерево (Би-дерево). Здесь узел содержит больше одного значения и больше 2-х потомков. Также его называют сбалансированным по высоте деревом поиска порядка m (Height Balanced m-way Search Tree).

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

Возможные операции: 1. Поиск. 2. Вставка (вставляем новый элемент). 3. Удаление.

Каждое B-дерево имеет порядок. Для примера рассмотрим B-дерево порядка m. Оно будет обладать рядом следующих характеристик:

Screenshot_7.1-1801-d40701.png

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

Screenshot_7.2-1801-28274b.png

Поиск аналогичен поиску по двоичному дереву. Следует вспомнить, что в двоичном древе поиск начинается с корня, причем каждый раз принимается 2-стороннее решение (пойти по правому поддереву либо по левому). В В-дереве поиск тоже начинается с корневого узла, но с той лишь разницей, что на каждом шаге принимается не 2-стороннее, а n-стороннее решение, причем n для дерева в данном случае представляет общее число потомков рассматриваемого узла. Сложность поиска такого дерева — O(log n).

Screenshot_8-1801-d03310.png

Также существует такое понятие, как вставка в B-дерево.

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

Screenshot_9-1801-90456d.png

Более подробную информацию всегда можно получить на наших курсах по алгоритмам в Москве:

Бинарное (двоичное) дерево поиска, обходы и применение

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

Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.

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

Одной из форм записи деревьев «на бумаге» называется скобочной записью:

(8 (3 (1) (6 (4) (7))) (10 (14 (13))))

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

(8 (3 (1) (6 (4) (7) ) ) (10 (14 (13) ) ) )

А так оно выглядит на самом деле:

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

Деревья полезны, они используются во многих задачах, например:

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

Важно место в информатике занимают бинарные (или двоичные) деревья, у которых для каждого узла не более 2-х дочерних элементов, это левый и правый наследники. БНФ форма его определения выглядит так:

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

  • Значение в любой вершине не меньше, чем значения её потомков.
  • Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
  • Последний слой заполняется слева направо без «дырок».

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

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

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

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:

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

Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).

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

preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right)
iterativePreorder(node) s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)

Правый потомок заносится первым, так что левый потомок обрабатывается первым

levelorder(root) q ← empty queue q.enqueue(root) while (not q.isEmpty()) node ← q.dequeue() visit(node) if (node.left ≠ null) q.enqueue(node.left) if (node.right ≠ null) q.enqueue(node.right)

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

Прошитое бинарное дерево поиска

Типичная структура данных одного узла такого дерева выглядит так:

struct node < data_type_t dat; node *left, *right; //теперь left и right могут указывать как на дочерние элементы, так и содержать нитки, ведущие на другие уровни bool left_is_thread, right_is_thread; >

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

Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды ( +, –, *, / ), а листья — числовые значения.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *