Определение, операции и как их реализовать с нуля.

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

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

Определение и терминология

Пусть (X, ≤) полностью упорядоченное множество.

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

(1) Существует нулевой узел, обозначенный Null;

(2) кортеж из 4 элементов N = (P, x, L , R) такие, что:

  • x принадлежит X,
  • P, L и R - узлы,
  • свойство binary-search-tree выполнено (мы вернемся к нему чуть позже)

это узел. x называется ключом узла, P называется родительским узлом, L - левым дочерним узлом, а R это правильный ребенок.

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

Листья, деревья, глубина, высота и предок

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

Бинарное дерево поиска B может иметь нулевое значение или характеризоваться корневым узлом R. Мы говорим, что R принадлежит B и что узел принадлежит B именно тогда, когда принадлежит его родитель. Если N является узлом, мы просто будем называть дерево, корневой узел которого N, как N. В оставшейся части этой статьи мы будем предполагать, что ключи уникальны в деревьях.

Глубина узла в дереве - это его расстояние до корня. Формально глубина корня равна 0, и если узел (p, v, L, R) имеет глубину x, L и R имеет глубину (x + 1).

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

Наконец, мы говорим, что узел N является предком узла M, если N = M или N является родителем предка M. Мы говорим, что N является правильным предком M, если N является предок M и N ≠ M.

Это позволяет определить тип деревьев как размеченное объединение:

Свойство двоичного поиска

Свойство двоичного поиска позволяет организовать узлы в соответствии с порядком их ключей. Учитывая ненулевой узел (P, x, L, R), он утверждает, что для всех узлов ℓ в дереве L и для всех узлов r в дереве R, ключ (ℓ) ≤ x и x ≤ Key (r).

Например, на изображении ниже показано двоичное дерево поиска. Его корень имеет ключ 4. Его листья имеют ключи 1, 5 и 11.

Но следующее двоичное дерево не является двоичным деревом поиска:

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

Операции

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

  • ходьба,
  • вставка,
  • поиск,
  • поиск,
  • минимальный запрос и максимальный запрос,
  • удаление

Гулять пешком

Обход или обход дерева означает посещение всех узлов в определенном порядке и передачу их какой-либо функции.

Есть три алгоритма ходьбы: заказ, предварительный заказ и пост-заказ. Обход по порядку посещает узел (P, x, L, R), рекурсивно обходя его левую подпрограмму -tree L по порядку, затем печать (или выполнение чего угодно) ключа x и, наконец, рекурсивный обход R по порядку. Реализовано это следующим образом:

  • Обход по порядку печатает все узлы двоичного дерева поиска в отсортированном порядке. Он выполняется за Θ (N) времени в зависимости от количества узлов в дереве.
  • walk_in_order можно сделать хвостовой рекурсией с помощью функции продолжения.
  • Точно так же при обходе до и после упорядочения текущий ключ печатается перед обходом поддеревьев и после обхода поддеревьев, соответственно.

Вставка

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

Процедура, которую мы используем для выполнения этой операции, создает новый лист N с ключом v. Чтобы найти родителя N, мы посещаем дерево от корня до листа, выбирая соответствующую ветвь для сохранения свойства двоичного дерева поиска. Когда мы находим лист (назовем его M), M становится родительским узлом для N. Если v ≤ Key (M) (или Key (M) ‹v соответственно), мы устанавливаем левый дочерний элемент (или правый дочерний элемент, соответственно) от M до N.

Вот рекурсивная реализация:

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

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

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

Вставка выполняется за Θ (H) времени относительно высоты дерева.

Searching

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

Реализация довольно проста. Мы проверяем, содержит ли текущий узел целевой ключ (в этом случае мы возвращаем true) и вызываем рекурсивно в левом поддереве, если целевой ключ меньше ключа текущего узла, или в правом поддереве, если целевой ключ больше . Если мы достигаем нулевого узла до завершения, то целевой ключ не принадлежит BST.

Эту же идею можно реализовать итеративно:

Мин. И макс. Запросы

Поиск минимального (или максимального) ключа в дереве аналогичен поиску. Все, что нам нужно знать, - это идти к самому левому (или самому правому) поддереву, пока не достигнем пустого узла.

Мы реализуем find-min следующим образом:

find-max похоже.

Поиск преемника узла

Учитывая узел N = (p, v, L, R) в дерево R, мы определяем преемника N в R как узел с наименьшим ключом среди тех, чей ключ строго больше, чем v. Такой узел не обязательно существует.

Если R не равно NULL, то преемником N будет минимум R.

Если R имеет значение null, N может все еще иметь преемника: это его ближайший правый предок, то есть ближайший предок, левое поддерево которого содержит N.

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

Более формально:

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

Если правый дочерний элемент N равен нулю, то N имеет преемника тогда и только тогда, когда он имеет правого предка (в этом случае наследник N является его ближайшим правым предком).

Схема доказательства:

Если R не равно нулю, пусть m будет минимумом R. Если N - левый узел своего родителя, то по свойству двоичного дерева поиска m меньше, чем все предки N, поэтому он должен быть преемником of N. Если N - правый узел своего родителя, то каждый предок меньше его, поэтому m является его преемником.

Предположим теперь, что R равно нулю. Пусть m обозначает ближайшего правого предка N, если он существует. Тогда m больше N по определению правого предка и свойству BST. Если m находится в левом поддереве своего родителя, то никакие предки m не меньше его. Если m находится в правом поддереве своего родителя, то никакие предки m не превышают N. Поскольку m является * ближайшим * правым предком N, любой собственный предок N, который не является предком m, является левым предком N , следовательно, меньше, чем это. Этого достаточно, чтобы доказать, что m является наследником N.

Наконец, предположим, что R имеет нулевое значение и N не имеет правильных предков. Все дочерние элементы R меньше его (по свойству BST). Все предки являются левыми предками, следовательно, их также меньше N. Это доказывает, что у N нет наследников.

Это позволяет нам написать следующую реализацию:

Он возвращает NULL, если tree не имеет преемников.

Время работы - O (H) и Θ (H) в худшем случае.

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

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

Пересадка

Первое, что мы делаем, это объявляем процедуру repot, которая заменяет узел другим.

Строки со 2 по 6 просят родителей next забыть о своем ребенке (мы передадим новых родителей next в должное время).

Если previous не имеет родителей (т.е. является корнем tree), мы просто присваиваем next tree.

В противном случае узел, который является родительским для previous, становится родительским для next (строка 12), и мы назначаем next соответствующему дочернему элементу previous (строки с 13 по 17).

Удаление

Если хотя бы один из двух дочерних элементов N имеет значение null, мы вызываем repot N C, где C - левый дочерний элемент N, если его правый дочерний элемент имеет значение null, в противном случае - его правый дочерний элемент.

Рассмотрим следующий пример, где мы хотим удалить узел y.

Первое условие delete (строка 2) выполнено. Когда мы вызываем repot y NULL, строка условия 13 удовлетворяется, поэтому левый дочерний элемент родительского элемента y, то есть x .Right, становится нулевым. Затем мы можем стереть y из памяти. Обновленное дерево выглядит так:

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

Цель состоит в том, чтобы заменить 17 его преемником 20.

Первый шаг состоит в использовании функции repot для подключения правого поддерева 20 к 23. Это дает следующее временное дерево:

Затем мы соединяем правое поддерево 17 с 20: мы устанавливаем 20.Right <- 17.Right и 20.Right.Parent <- 20.

20 теперь имеет соответствующее правое поддерево. Нам нужно установить его левое поддерево и его родителя. Для этого мы вызываем repot 17 20, а затем подключаем левое поддерево 17 к 20: 20.Left <- 17.Left и 20.Left.Parent <- 20.

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

Вот окончательная реализация:

Вывод: слово на высоте

Сложность выполнения большинства описанных нами операций пропорциональна высоте дерева. Высота дерева с n узлами асимптотически находится между log n и n. Если мы вставим узлы в отсортированном порядке, мы получим одномерное дерево: высота узла будет Θ (n), поэтому не будет никакой пользы от использования дерева, а не списка. . Предположим теперь, что у вас есть набор из n ключей, и вы создаете BST, вставляя все ключи в случайном порядке. Бывает, что ожидаемая высота дерева оптимальна: O (log_2 (n)). Также существуют самобалансирующиеся деревья двоичного поиска, которые сохраняют минимальную высоту при вставке и удалении узлов. Красно-черные деревья являются примером самобалансирующихся двоичных деревьев поиска. Они будут предметом будущей статьи.

Поддержите меня!

Если вы нашли эту статью полезной, подумайте о том, чтобы подписаться на меня, чтобы помочь мне достичь порога в 100 подписчиков, необходимого для участия в программе Medium Partner Program. Это бесплатно и действительно помогает.

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

🐙