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

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

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

C:/ Drive / | | \ Apps Games Music Desktop
  • Для реализации индексов внутри баз данных для очень быстрого доступа к контенту.
  • Чтобы предсказать, что вы набираете на телефоне, учитывая, что каждая буква доступна для поиска внутри Дерева, и дать вам предложения по повышению скорости.

Определения

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

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

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

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

Root / \ Left Right / \ / \ Left Right Left Right

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

root => { value: 1, left: { value: 3, left: { value: 2, left: null, right: null, }, right: { value: 8, left: null, right: null, } }, right: { value: 3, left: null, right: null, } }

Это конкретное дерево выглядит так:

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

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

class Node: value = None left = None right = None def __init__(value, self): self.value = value def add_left(value, self): self.left = Node(value) def add_right(value, self): self.right = Node(value) tree = Node(11) tree.add_left(8) tree.add_right(16) print(tree.value) # 11 print(tree.left.value) # 8 print(tree.right.value) # 16 # Let's add the next items tree.left.add_left(5) tree.left.add_right(10) tree.right.add_right(18) print(tree.value) # 11 print(tree.left.value) # 8 print(tree.right.value) # 16 print(tree.left.left.value) # 5 print(tree.left.right.value) # 10 print(tree.right.right.value) # 18

Класс Node содержит значение переменных состояния, left и right. Конструктор инициализирует значение корневого узла, в то время как методы add_left и add_right используются для настройки левого и правого узлов.

Обратите внимание, что значения left и right являются еще одним экземпляром класса Node. Это не простые значения, это узлы со значением, левым и правым.

Древовидные алгоритмы

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

Есть 2 основных метода обхода:

  1. Метод поиска в глубину (DFS)
  2. Метод поиска в ширину (BFS)

Затем внутри DFS есть 3 подкатегории в зависимости от используемого порядка:

Давайте быстро разберемся с каждым методом обхода за ‹1 минуту каждый:

Предзаказ

Шаги для выполнения этого следующие:

Перед проверкой алгоритма рассмотрим реализацию простой древовидной структуры данных в javascript, которую мы будем использовать в примерах:

class Tree { value = null left = null right = null constructor(value) { this.value = value } addLeft(value) { this.left = new Tree(value) } addRight(value) { this.right = new Tree(value) } } const myTree = new Tree(1)

Это делается рекурсивно, поэтому вам не о чем больше беспокоиться. Вот код в javascript:

preOrder() { console.log(this.value) if (this.left) this.left.preOrder() if (this.right) this.right.preOrder() }

А вот полная реализация с использованием древовидного класса в современном javascript:

class Tree { value = null left = null right = null constructor(value) { this.value = value } addLeft(value) { this.left = new Tree(value) } addRight(value) { this.right = new Tree(value) } preOrder() { console.log(this.value) if (this.left) this.left.preOrder() if (this.right) this.right.preOrder() } } const myTree = new Tree(1)

Чтобы

Шаги для выполнения этого следующие:

Вот код на js:

inOrder() { if (this.left) this.left.inOrder() console.log(this.value) if (this.right) this.right.inOrder() }

И полная реализация:

class Tree { value = null left = null right = null constructor(value) { this.value = value } addLeft(value) { this.left = new Tree(value) } addRight(value) { this.right = new Tree(value) } inOrder() { if (this.left) this.left.inOrder() console.log(this.value) if (this.right) this.right.inOrder() } } const myTree = new Tree(1)

Пост-заказ

Шаги для выполнения этого следующие:

Вот код на js:

postOrder() { if (this.left) this.left.postOrder() if (this.right) this.right.postOrder() console.log(this.value) }

Поиск в ширину (BFS)

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

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

let queue = [] queue.push(1) queue.push(2) queue.push(3) // Now our queue is [1, 2, 3] queue.get() // Returns "1" queue.shift() // Removes "1" console.log(queue) // Returns [2, 3]

Шаги следующие:

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

bfs() { let queue = [] queue.push(this) while (queue.length > 0) { const active = queue[0] console.log(active.value) if (active.left) queue.push(active.left) if (active.right) queue.push(active.right) queue.shift() } }

Вот полная реализация:

class Tree { value = null left = null right = null constructor(value) { this.value = value } addLeft(value) { this.left = new Tree(value) } addRight(value) { this.right = new Tree(value) } bfs() { let queue = [] queue.push(this) let counter = 0 while (queue.length > 0 && counter < 100) { const active = queue[0] console.log(active.value) if (active.left) queue.push(active.left) if (active.right) queue.push(active.right) queue.shift() counter++ } } } const myTree = new Tree(1)

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

class Tree { value = null left = null right = null constructor(value) { this.value = value } addLeft(value) { this.left = new Tree(value) } addRight(value) { this.right = new Tree(value) } preOrder() { console.log(this.value) if (this.left) this.left.preOrder() if (this.right) this.right.preOrder() } inOrder() { if (this.left) this.left.inOrder() console.log(this.value) if (this.right) this.right.inOrder() } postOrder() { if (this.left) this.left.postOrder() if (this.right) this.right.postOrder() console.log(this.value) } bfs() { let queue = [] queue.push(this) let counter = 0 while (queue.length > 0 && counter < 100) { const active = queue[0] console.log(active.value) if (active.left) queue.push(active.left) if (active.right) queue.push(active.right) queue.shift() counter++ } } } const myTree = new Tree(1)

И в питоне:

from Queue import Queue class Node: value = None left = None right = None def __init__(self, value): self.value = value def add_left(self, value): self.left = Node(value) def add_right(self, value): self.right = Node(value) def pre_order(self): print(self.value) if self.left: self.left.pre_order() if self.right: self.right.pre_order() def in_order(self): if self.left: self.left.in_order() print(self.value) if self.right: self.right.in_order() def post_order(self): if self.left: self.left.post_order() if self.right: self.right.post_order() print(self.value) def breadth_first_search(self): queue = Queue() queue.put(self) while not queue.empty(): active = queue.get() print(active.value) if active.left: queue.put(active.left) if active.right: queue.put(active.right) # Some sample data tree = Node('html') tree.add_right('body') tree.right.add_left('h1') tree.right.add_right('h2') # A few examples here tree.pre_order() print('\n') tree.in_order() print('\n') tree.post_order() print('\n') tree.breadth_first_search()

Структура данных двоичного дерева поиска

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

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

Предположим, вам нужно создать двоичное дерево поиска из этих входных данных: 20, 10, 49, 28, 59, 29
Начните с корневого узла, в данном случае 20.
Следующий узел, 10, будет помещен слева, потому что 10 меньше 20, поэтому мы имеем:

Затем следующий узел, 49, идет справа от 20, потому что он больше:

Затем узел 28 идет слева от узла 49. Почему? поскольку мы не можем изменять существующие узлы, все, что мы можем сделать, это добавить элементы в текущее дерево, чтобы оно располагалось слева от 49, как это:

После этого мы добавляем узел 59 справа от 49, потому что он больше:

20 / \ 10 49 / \ 28 59

Наконец, мы добавляем элемент 29 справа от 28 следующим образом:

20 / \ 10 49 / \ 28 59 \ 29

Теперь вы можете спросить, почему бы не добавить 29 слева от узла 59? В конце концов, 29 меньше 59, поэтому он может туда попасть. Хороший вопрос. Причина, по которой мы добавляем его справа от 28, а не слева от 59, заключается в том, что двоичное дерево поиска должно быть упорядочено по вертикали, а это означает, что если вы пойдете слева направо, вы увидите, что элементы увеличиваются в значении. Взгляните на текущую структуру. Сначала слева, затем 20 чуть правее и сверху, затем 28 ниже 20, затем 49, 29 ниже 49 и 59. Нет смысла опускаться ниже после перехода к 59.

Чтобы было ясно, мы следуем этому алгоритму:

Вот разбивка последнего добавленного нами элемента, узла 29:

  1. 29 больше или меньше 20? Больше, идите вправо.
  2. 29 больше или меньше 49? Меньше иди налево.
  3. 29 больше или меньше 28? Больше, идите вправо.
  4. Поскольку узлов больше нет, сохраните эту позицию.

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

Вот долгожданный код на Python и javascript для реализации двоичного дерева поиска:

В javascript:

class BinarySearchTree { value = null left = null right = null constructor (value) { this.value = value } addNode (value) { if (value >= this.value && !this.right) { this.right = new BinarySearchTree(value) } else if (value < this.value && !this.left) { this.left = new BinarySearchTree(value) } else if (value >= this.value && this.right) { this.right.addNode(value) } else if (value < this.value && this.left) { this.left.addNode(value) } } bfs() { let queue = [] queue.push(this) let counter = 0 while (queue.length > 0 && counter < 100) { const active = queue[0] console.log(active.value) if (active.left) queue.push(active.left) if (active.right) queue.push(active.right) queue.shift() counter++ } } } // BST with 20, 10, 49, 28, 59, 29 let b = new BinarySearchTree(20) b.addNode(10) b.addNode(49) b.addNode(28) b.addNode(59) b.addNode(29) b.bfs()

В питоне:

import Queue from Queue class BinarySearchTree: value = None left = None right = None def __init__(self, value): self.value = value def add_node(self, value): if value >= self.value and self.right is None: self.right = BinarySearchTree(value) elif value < self.value and self.left is None: self.left = BinarySearchTree(value) elif value >= self.value and self.right is not None: self.right.add_node(value) elif value < self.value and self.left is not None: self.left.add_node(value) def breadth_first_search(self): queue = Queue() queue.put(self) while not queue.empty(): active = queue.get() print(active.value) if active.left: queue.put(active.left) if active.right: queue.put(active.right) # BST with 20, 10, 49, 28, 59, 29 binarySearchTree = BinarySearchTree(20) binarySearchTree.add_node(10) binarySearchTree.add_node(49) binarySearchTree.add_node(28) binarySearchTree.add_node(59) binarySearchTree.add_node(29) binarySearchTree.breadth_first_search()

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

Метод add_node использует рекурсию для добавления узлов, вызывая одну и ту же функцию снова и снова, пока элемент не будет размещен. Это означает, что все рекурсивные вызовы будут храниться в памяти, поэтому, если вы работаете на компьютере с небольшой памятью, вы можете столкнуться с проблемами, если создадите массивное двоичное дерево поиска. Если вам интересно узнать об ограничениях памяти в рекурсивных функциях, посетите эту страницу https://rosettacode.org/wiki/Find_limit_of_recursion, где вы увидите фактические ограничения для каждого языка.

Например, в javascript максимальная глубина рекурсии в chrome составляет 10473, а в firefox - 3000. Хотя она может варьироваться от версии к версии. В моем случае я получаю 11402 уровня в глубину, прежде чем он достигнет предела памяти. Вы можете попробовать это самостоятельно на своем компьютере, запустив эту функцию в инструментах разработчика Chrome (щелкнув правой кнопкой мыши и выбрав «Проверить» на любой странице, чтобы затем открыть вкладку консоли, куда вы можете вставить этот код):

function recurse(depth) { try { return recurse(depth + 1); } catch(ex) { return depth; } } let maxRecursion = recurse(1); console.log("Recursion depth on this system is " + maxRecursion)

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

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

Поиск значений в двоичных деревьях поиска

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

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

Вот реализация на javascript:

existsNode (value) { if (value > this.value && this.right) { return this.right.existsNode(value) } else if (value < this.value && this.left) { return this.left.existsNode(value) } return value == this.value }

И в питоне:

def exists_node(self, value): if value > self.value and self.right: return self.right.exists_node(value) elif value < self.value and self.left: return self.left.exists_node(value) return value is self.value

Удаление значений в двоичных деревьях поиска

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

Удаление узла без дочерних узлов

Вот как это выглядит:

10 10 / \ \ 8 20 -Delete 8-> 20

По сути, мы оставляем пустое место. Итак, в коде он должен делать следующее:

  1. Найдите узел, который нужно удалить
  2. Проверьте, не имеет ли удаляемый узел потомков
  3. Если да, просто очистите его значение, заменив его на null или None в зависимости от вашего языка.

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

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

Итак, в javascript:

deleteNode (value, parent) { // Find the node to delete using recursion if (this.value == value) { if (parent.left && parent.left.value == value) { parent.left = null return true } else { parent.right = null // One of the branches must be the exact value so we remove the right if the left is not the right value return true } } else if (value > this.value && this.right) { return this.right.deleteNode(value, this) } else if (value < this.value && this.left) { return this.left.deleteNode(value, this) } else { return false // We didn't find the element } }

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

Удаление узла с одним дочерним элементом

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

10 10 / \ / \ 8 20 -Delete 20-> 8 11 / 11

И код на javascript. В конце этого руководства вы также найдете окончательный код на Python:

deleteNode (value, parent) { // Find the node to delete using recursion if (this.value == value) { if (parent.left && parent.left.value == value) { // If the element we are trying to delete has a child and only one we replace it with that child if (this.left && !this.right) { parent.left = this.left } else if (!this.left && this.right) { parent.left = this.right } else if (this.left && this.right) { // The node we want to delete has 2 children } else { // The node we want to delete has no children parent.left = null } } else { // One of the branches must be the exact value so we remove the right if the left is not the right value if (this.left && !this.right) { parent.right = this.left } else if (!this.left && this.right) { parent.right = this.right } else if (this.left && this.right) { // The node we want to delete has 2 children } else { // The node we want to delete has no children parent.right = null } } return true } else if (value > this.value && this.right) { return this.right.deleteNode(value, this) } else if (value < this.value && this.left) { return this.left.deleteNode(value, this) } else { return false // We didn't find the element } }

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

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

Удаление узла с 2 детьми

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

10 10 / \ / \ 8 20 -Delete 20-> 8 14 / \ / \ 14 23 11 17 / \ \ 11 17 23

Мы удалили узел 20, а затем решили заменить это пустое пространство левым узлом, подняв его, зная, что правая сторона удаленного узла, 23, будет помещена в крайнее правое место поднятого узла. Таким образом, узел 23 будет размещен в самом большом узле ветви 14, а последний элемент - в крайнем правом месте.

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

Вот как это выглядит в javascript:

deleteNode (value, parent) { // Find the node to delete using recursion if (this.value == value) { if (parent.left && parent.left.value == value) { // If the element we are trying to delete has a child and only one we replace it with that child if (this.left && !this.right) { parent.left = this.left } else if (!this.left && this.right) { parent.left = this.right } else if (this.left && this.right) { // The node we want to delete has 2 children // 1. We will replace the deleted node with the left one so find the largest node on the left and place the hanging right node there // 2. Then replace the node after the hanging one has been taken care of (we can only have 2 children in binary trees) parent.left = this.left let currentNode = this.left let isAdded = false while (!isAdded) { if (currentNode.right) { currentNode = currentNode.right } else { // Add the hanging right node to the end of the left branch from the right currentNode.right = this.right isAdded = true } } } else { // The node we want to delete has no children parent.left = null } } else { // One of the branches must be the exact value so we remove the right if the left is not the right value if (this.left && !this.right) { parent.right = this.left } else if (!this.left && this.right) { parent.right = this.right } else if (this.left && this.right) { // The node we want to delete has 2 children parent.right = this.left let currentNode = this.left let isAdded = false while (!isAdded) { if (currentNode.right) { currentNode = currentNode.right } else { // Add the hanging right node to the end of the left branch from the right currentNode.right = this.right isAdded = true } } } else { // The node we want to delete has no children parent.right = null } } return true } else if (value > this.value && this.right) { return this.right.deleteNode(value, this) } else if (value < this.value && this.left) { return this.left.deleteNode(value, this) } else { return false // We didn't find the element } }

Вот объяснение:

// The node we want to delete has 2 children parent.right = this.left let currentNode = this.left let isAdded = false while (!isAdded) { if (currentNode.right) { currentNode = currentNode.right } else { // Add the hanging right node to the end of the left branch from the right currentNode.right = this.right isAdded = true } }
  • Сначала он заменяет удаляемый узел левым дочерним элементом, включая все дочерние элементы, поскольку они автоматически соединяются ссылками.
  • После этого нам нужно поместить висящего правого дочернего элемента в конец правой ветви левого дочернего элемента. Мы запускаем while цикл, который обращается к левому дочернему элементу, который мы подняли прямо сейчас, и находим самый правый узел. Это узел с наибольшим значением.
  • Мы знаем, что последний правый узел не имеет дочерних узлов, поэтому мы используем оператор if и устанавливаем висящий правый узел как дочерний для последнего правого узла от левого дочернего.
  • Теперь удаленный узел был заменен левым дочерним элементом, а правый дочерний элемент был помещен внизу левого дочернего элемента, поскольку это наибольшее значение, поскольку мы используем упорядоченные двоичные деревья.

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

Не забудьте присоединиться к моему списку рассылки, чтобы получать по электронной почте эксклюзивные руководства, которые вы не найдете в других местах, написанные мной благодаря 5-летнему опыту работы в программировании здесь: http://eepurl.com/dDQ2yX

Первоначально опубликовано на https://merunas.io 19 декабря 2019 г.