Привет, ребята, меня зовут Сид, и я, как и вы, энтузиаст информатики. Это мой первый учебник по структурам данных. Сегодня я хочу рассмотреть популярную структуру данных, известную как дерево двоичного поиска или BST. Чтобы сначала понять эту структуру, мы должны сначала понять ключевую концепцию в математике, искусстве и информатике, известную как рекурсия.
Что такое рекурсия?
Во-первых, мы увидим, как компьютер управляет своими действиями по порядку, используя структуру данных, известную как стек.
Начнем с примера. Ниже у меня есть программа, которая создает функцию с именем printHello(), которая просто возвращает вторую созданную функцию hello(). В последней строке этого скрипта ВЫЗЫВАЕТСЯ функция ‘printHello()’. А это, друзья мои, активирует стек вызовов программы. Согласно нашей программе, первое, что должна сделать наша программа, это return printhello(), потому что она была вызвана первой. Итак, мы рассмотрим функцию шаг за шагом.
def printHello():
return hello()
def hello():
return "Hello"
printHello()
Что printHello() говорит компьютеру сделать сейчас, так это вернуть функцию hello(). И это приводит к изменению нашего списка приоритетов. Чтобы завершить printHello(), мы должны выполнить функцию hello(). Это добавляет новый стек в наш стек вызовов. Раньше верхним стеком в стеке вызовов была функция printHello().
Теперь переходим к функции hello(). Эта функция возвращает строку «Hello». Вот и все. Эта функция выполнила то, что должна, а именно вернула значение для стека под ней, или, другими словами, передала что-то для функции printHello(). И вуаля, наша программа наконец-то завершена и возвращает строку «Hello», и таким образом мы «выталкиваем» все слои в нашем стеке вызовов.
Этот пример объясняет ПОЛОВИНУ того, что такое рекурсия. Теперь пора углубиться в вторую половину. Рекурсия в основном означает, что функция ВЫЗЫВАЕТ СЕБЯ. Мы понимаем, что означает вызов функции, но что происходит, когда функция вызывает сама себя? Мы объясним это на известном примере, известном как вычисление факториала числа. Факториал числа - это умножение числа на все числа под ним. Выглядит это примерно так:
Но ждать !? Разве факториал 5 не является умножением 5 на факториал 4? И это абсолютно правильно. Выражение выше в основном таково. И вот здесь мы рекурсивно решаем факториал 5, используя наш стек вызовов:
Почему мы остановились на факториале 1? Факториал 1 равен 1. В рекурсивных программах это часто называют БАЗОВЫМ СЛУЧАЕМ. Базовый случай - это в основном параметр или ввод, который вы передаете функции, что всегда истинно или тривиально. Теперь, когда мы знаем факториал 1, мы можем «вытолкнуть» этот стек вызовов. Итак, мы выяснили, что факториал 5 равен 120. Я также написал фрагмент кода, который вы можете попробовать.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
factorial(5)
Из этих двух примеров вы должны теперь понять, что такое рекурсия. Рекурсия - действительно полезный инструмент, поскольку он позволяет нам решать большие проблемы в виде набора «подзадач». Рекурсия - это инструмент, который часто используется в парадигмах программирования Divide and Conquer, которые мы увидим в будущем. Теперь поговорим о двоичных деревьях поиска.
Дерево двоичного поиска (BST)
Бинарное дерево поиска - это структура данных, которая служит набором узлов. Узел - это объект, имеющий три атрибута. Они есть:
- Данные: переменная, которая хранит данные в узле, т. Е. Число.
- Левое соединение: переменная, которая может хранить другой узел
- Правильное соединение: переменная, которая может хранить другой узел
Затем эти узлы можно упорядочить, чтобы сформировать дерево двоичного поиска, набор узлов:
Поскольку каждый узел является «объектом», мы можем создать класс для узла. Ниже представлена реализация Node, которую мы будем использовать в этом руководстве. Как видите, каждый узел инициализирует себя значением (данными) и устанавливает его левый и правый дочерние элементы как None НА ВРЕМЯ. Первый узел дерева называется корневым узлом. Если вы заметили, древовидная структура данных выглядит как перевернутое дерево. Вот почему этот узел называется корневым. В случае с деревом выше корневым узлом является 8.
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
Теперь вы можете спросить себя, почему мы узнали о рекурсии, чтобы узнать о деревьях? Это потому, что дерево - это то, что я называю рекурсивной структурой данных. Что я имею в виду? Посмотрите на деревья внизу. Это одно и то же дерево. Вспомните, как мы определяли рекурсию как решение подзадач более крупной проблемы. Посмотрите на дерево справа. Это похоже на дерево, состоящее из небольших поддеревьев, и эти поддеревья также состоят из поддеревьев. Вот почему рекурсия так важна для понимания деревьев. В конце концов, рекурсивно, мы доходим до точки, где «поддеревья» являются просто узлами. вот почему узел так важен и в дереве.
Теперь давайте посмотрим на один из методов, используемых в BST, который называется вставкой.
Вставка
Первый метод дерева двоичного поиска, который мы обсудим, - это вставка узлов. Одна из ключевых особенностей бинарного дерева поиска, которая делает его таким особенным, заключается в том, что ЛЕВЫЙ РЕБЕНОК каждого узла МЕНЬШЕ или равен данным в корневом узле, а ПРАВИЛЬНЫЙ РЕБЕНОК каждого узла больше, чем данные в корневом узле. корневой узел. Мы организовываем узлы таким образом, потому что это позволит нам делать что-то довольно полезное, что мы увидим в следующих разделах.
Если у каждого узла может быть только два дочерних узла, и мы хотим ВСТАВИТЬ еще один узел, что нам делать? Мы используем рекурсию.
Если мы встречаем значение МЕНЬШЕ, чем корневой узел, мы переходим к ЛЕВОМУ дочернему элементу корневого узла и сравниваем с данными, хранящимися в этом узле. Опять же, если значение меньше, чем текущий узел, мы идем влево, иначе мы идем вправо, ДО тех пор, пока мы не столкнемся с ситуацией, когда мы должны пойти влево или вправо, и НЕТ РЕБЕНКА, или левый / правый узел текущего узла установлен на None. Здесь мы создадим новый узел и зафиксируем значение. Ниже приведена иллюстрация темы и реализации вставки на языке Python.
В этом случае базовый случай - это когда левый / правый узел текущего узла равен None, и мы можем его заполнить, а рекурсивный случай - когда значение меньше / больше, чем у текущего узла, но соответствующий дочерний узел для узла уже заполнен другим узлом, поэтому мы переходим к этому узлу и повторяем процесс.
def insert(value,node):
if value < node.data:
if node.left == None:
node.left = Node(value)
else:
print "Going Left"
insert(value,node.left)
else:
if node.right == None:
node.right = Node(value)
else:
print "Going Right"
insert(value,node.right)
return
Поиск
Далее мы поговорим о поиске определенного значения в BST. Когда мы ищем значение в двоичном дереве поиска, мы снова должны использовать рекурсию. А с учетом того, как организовано дерево двоичного поиска, поиск по нему на самом деле довольно эффективен.
Рассмотрим следующий пример. Ниже у меня есть дерево, и я хочу найти значение 19, и поскольку это дерево, мне нужно начинать с вершины / корня.
Поскольку 19 меньше 27, я знаю, что он никак не может находиться в правом потомке корневого узла, потому что только значения больше 27 могут идти вправо. Это означает, что мне нужно искать слева, так как туда могут попасть только значения, большие или равные 27. Итак, теперь у нас 14. 19 больше, чем 14, это означает, что мы смотрим вправо. И что вы знаете, мы нашли 19. Эта структура или метод поиска узлов работает, потому что если значение, которое мы пытаемся найти, больше, чем данные в текущем узле, и у правого дочернего узла есть дочерний элемент (другой node), чем показывает нам, что существует некоторая вероятность того, что значение, которое мы пытаемся найти, существует, потому что мы не закончили просмотр дерева. Та же логика применима и к левой стороне. Иначе, если мы находимся в ситуации, когда значение, которое мы ищем, больше, чем данные в текущем узле, но этот узел не имеет правильного дочернего элемента, мы можем сделать вывод, что узел не существует. Потому что нет возможности, что значение, которое мы пытаемся найти, существует в этих ОГРАНИЧЕНИЯХ.
Постой, что за границы !? Что ж, давайте вернемся к приведенному выше примеру. Когда мы ищем 19, первое, что мы говорим: «Хорошо, 19 меньше 27, и, поскольку есть левый дочерний элемент, это означает, что любые числа от -∞ до 27 МОГУТ существовать в левом поддереве». И что вы знаете, в этом диапазоне чисел существует 19. Теперь мы посмотрим на 14, и, поскольку 19 больше 14 и есть правый дочерний узел узла, мы можем сказать: «Хорошо, это означает, что любые числа от 15 до + ∞ МОГУТ существовать в этом правом поддереве». И наконец мы находим 19.
Если бы мы искали, скажем, 20 в том же дереве, и повторяем тот же процесс, мы бы не нашли его. Это потому, что мы закончим 19, у которого нет дочерних элементов, и мы будем говорить: «Хорошо, если нет правильного дочернего элемента, то это означает, что ничего 19 и + ∞ не существует в этом правом поддереве. Следовательно, этого не существует ». И это абсолютно правильно. Ниже приведен код для поиска:
def search(value, node):
if value == node.data:
return True
if value < node.data and node.left == None:
return False
if value >= node.data and node.right == None:
return False
if value <> node.data and node.left == None and node.right == None:
return
else:
if value < node.data:
return search(value, node.left)
elif value >= node.data:
return search(value,node.right)
Этот метод называется Двоичный поиск, и вы, возможно, слышали об этом алгоритме раньше. Это связано с тем, что его уже можно использовать в отсортированном массиве, что приводит меня к третьему методу для нашего BST.
Распечатать отсортировано
Поскольку левый дочерний элемент каждого узла состоит из узлов, меньших, чем текущий узел, мы можем сделать вывод, что крайний левый узел в дереве является наименьшим узлом в дереве, а крайний правый узел в дереве является наибольшим узлом в дереве. Но как насчет узлов «между» минимумом и максимумом?
Если крайний левый узел является наименьшим узлом, то его корневой узел будет вторым наименьшим узлом в дереве, поскольку он будет «следующим по величине» узлом в дереве. С другой стороны корневого узла (правая сторона) будет третье по величине значение в узле. НО ПОМНИ! Под крайним левым / крайним правым мы подразумеваем, что левый / правый дочерний элемент этого узла установлен в None. Итак, в дереве ниже крайний левый узел будет иметь значение 1, а крайний правый узел - 14:
Но что все это значит и почему это полезно? Знание этих вещей позволяет нам распечатать двоичное дерево в виде отсортированного списка. Сортированный список означает, что все значения в списке расположены от наименьшего к наибольшему.
Помните, как мы говорили о том, что дерево является рекурсивной структурой, потому что оно состоит из множества поддеревьев? Что ж, это свойство пригодится. Чтобы распечатать отсортированный список, мы сначала должны рекурсивно перейти к наименьшему узлу в дереве. По мере рекурсивного движения вниз мы продолжаем добавлять новые стеки в наш стек вызовов. Когда мы доходим до него, мы печатаем данные, хранящиеся в узле, а затем проверяем, есть ли у минимального узла правильные дочерние элементы, проверяя, установлено ли оно в None или нет. Когда мы закончим проверку обоих потомков, мы просто «выталкиваем» этот стек и переходим к следующему слою в стеке вызовов.
Теперь мы проделываем этот процесс для каждого из «поддеревьев» узла, и в конце мы получаем отсортированный список чисел, которые есть в дереве. Помните, когда мы решаем эту проблему для каждого поддерева, мы в основном решаем небольшую часть более крупной проблемы.
Давайте сделаем пример с деревом слева. Мы начинаем с узла 8 и продолжаем двигаться вниз, пока не встретим узел без левого дочернего элемента, в данном случае 1. Затем мы печатаем 1 и переходим к 3, после того как понимаем, что узел 1 не имеет правого дочернего элемента. . Распечатываем 3, а затем проверяем, есть ли у него правильный ребенок. У 3 есть правый дочерний элемент, поэтому мы переходим к наименьшему узлу в правом поддереве 3 и достигаем 4. У 4 нет дочерних элементов, поэтому мы возвращаемся к 6 и печатаем 6, и этот процесс сохраняет продолжается до тех пор, пока мы не вернемся к корневому узлу в 8, и в стеке вызовов останется только один уровень. Затем мы печатаем 8 и проверяем, есть ли у узла правильный дочерний элемент. Итак, этот процесс начинается заново для всей правой части дерева. Вот код, и это одна из проблем, в которой имеет смысл выполнить пример этого алгоритма или просто посмотреть на код и получить его:
def printSorted(node):
if node.left <> None:
printSorted(node.left)
print node.data
if node.right <> None:
printSorted(node.right)
Этот код распечатает двоичное дерево в отсортированном виде, и это известно как обход по порядку. Есть две другие формы обхода, известные как предварительный порядок и поступорядочение, но, на мой взгляд, inorder является наиболее полезным, потому что сортировка чего-то, что всегда полезно при работе с проблемами реального мира.
Удаление узла
Ах, это тот самый. Это единственный метод, который действительно требует некоторого размышления. Когда мы впервые читаем заголовок этого раздела, мы можем подумать: «О, давайте просто найдем узел, используя наш search() метод, а затем заменим его данные на None». Что ж, это не так просто. Когда мы заменяем данные в узле на None, мы не удаляем фактическое существование узла из памяти. Мы просто говорим, что этот узел будет хранить None, но узел по-прежнему будет существовать. Это может испортить множество вещей в дереве и не сохранит фундаментальное свойство левого узла меньше корневого, а правого узла больше корневого. Рассмотрение всего, что может пойти не так, при использовании этого метода, выходит за рамки этого руководства, но просто помните, что это не фактическое удаление.
Удаление - большая тема в BST, поэтому давайте начнем с простого. Предположим, мы хотим удалить узел 4 из двоичного дерева ниже. Сначала мы переходим к узлу, ища его, а затем проверяем, есть ли у него дочерние элементы. В этом случае 4 не имеет дочерних элементов, и поэтому мы можем удалить его, не заботясь о каких-либо «незакрепленных строках». Мы удаляем 4, ища узел, который имеет 4 в качестве одного из узлов, а затем устанавливаем этот дочерний элемент равным None. Это уловка при удалении! Мы будем называть этот процесс удаления узла без дочерних узлов базовым случаем в алгоритме.
Теперь давайте посмотрим на следующий случай удаления. Это когда узел, который мы пытаемся удалить, также имеет дочерний узел. Это немного сложнее, поскольку мы, конечно, не можем установить данные в узле равными None, а также не можем использовать трюк, о котором мы говорили ранее. Однако мы можем заменить данные в этом узле на преемника / предшественника узла.
Преемник узла - это узел, который находится сразу после узла, когда у нас есть отсортированное двоичное дерево. Например, в списке чисел от 1 до 10 преемником 1 является 2. Преемник узла всегда находится в его правом поддереве, и это наименьшее значение в правом поддереве (минимум). Когда мы его найдем, мы можем просто скопировать данные из преемника на узел, который хотим удалить. Если узел-последователь не имеет дочерних узлов, мы просто удаляем узел, применяя базовый случай (мы только что говорили об этом), и мы начнем с него с правого дочернего элемента узла, который должен был быть удален в первый. Это удалит узел из дерева, и вы также сможете распечатать дерево в отсортированном виде. Если у узла-преемника есть дочерние узлы, мы повторим этот метод, как вы догадались, рекурсивно на исходном узле-преемнике узла, который мы действительно хотим удалить. Этот процесс будет продолжаться, пока мы не достигнем базового варианта.
Та же логика применима и к предшественнику. Единственное отличие состоит в том, что предшественник - это узел прямо перед узлом, который мы хотим удалить, когда мы распечатываем его в отсортированном виде. Теперь мы ищем этот узел в левом поддереве узла, который мы хотим удалить, и это самый большой узел в поддереве (максимум). Затем мы повторяем тот же процесс, что и для узла-преемника, если мы находим дочерний элемент для узла-предшественника. В противном случае мы выполняем базовый вариант, начиная с левого узла исходного узла, который мы хотели удалить.
Наконец, если узел, который мы хотим удалить, имел двух дочерних узлов, мы ищем преемника узла. Мы можем искать предшественника, если захотим, но это не имеет значения, так как двоичное дерево все еще сохраняется. Итак, вот код. Этот был определенно самым длинным из написанных.
def search(value, node):
if value == node.data:
return True
if value < node.data and node.left == None:
return False
if value >= node.data and node.right == None:
return False
if value <> node.data and node.left == None and node.right == None:
return
else:
if value < node.data:
return search(value, node.left)
elif value >= node.data:
return search(value,node.right)
def maxNode(node):
if node.right <> None:
return maxNode(node.right)
if node.right == None:
return node
def minNode(node):
if node.left <> None:
return minNode(node.left)
if node.left == None:
return node
def deleteChildNode(value, node):
if node.left <> None and node.left.data == value:
node.left = None
return "Node is deleted"
if node.right <> None and node.right.data == value:
node.right = None
return "Node is deleted"
else:
if value < node.data:
return deleteChildNode(value, node.left)
elif value >= node.data:
return deleteChildNode(value,node.right)
def deleteNode(value, node):
if search(value, node) == False:
return "Did not find node"
else:
delete = searchNode(value, node)
if delete.right <> None:
minimum = minNode(delete.right)
delete.data = minimum.data
if minimum.left == None and minimum.right == None:
if delete.right.data == minimum.data:
delete.right = None
return "Node has been deleted"
else:
return deleteChildNode(minimum.data, delete.right)
if minimum.right <> None:
return deleteNone(minimum.right)
if delete.left <> None and delete.right == None:
maximum = maxNode(delete.left)
delete.data = maximum.data
if maximum.left == None and maximum.right == None:
if delete.left.data == maximum.data:
delete.left = None
return "Node has been deleted"
else:
return deleteChildNode(maximum.data, delete.left)
if maximum.left <> None:
return deleteNode(maximum.left)
if delete.left == None and delete.right == None:
return deleteChildNode(value, node)
И да, это некоторые из основных операций двоичного дерева поиска и довольно изящное введение в рекурсию. Мне понравилось писать это руководство, так как оно помогло мне многому научиться в пути, и я надеюсь, что оно поможет и вам. Однако, прежде чем вы уйдете, оставьте еще немного кода. Этот просто объединяет структуру данных в одну class, с которой можно поиграть.
class BinarySearchTree():
def __init__(self, val):
self.root = Node(val)
def insert(self, val):
return insert(val, self.root)
def search(self, val):
return search(val, self.root)
def printSorted(self):
return printSorted(self.root)
def deleteNode(self, val):
return deleteNode(val, self.root)
def searchNode(self, val):
return searchNode(val, self.root)
def maxNode(self):
return maxNode(self.root)
def minNode(self):
return minNode(self.root)
В моем следующем посте мы узнаем о временной сложности различных операций в дереве двоичного поиска. Если вы не знаете, что это значит, я тоже, так что давайте узнаем об этом вместе.
