Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действий:
- Отсортировать список и применить бинарный поиск.
- Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.
Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:
- Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов).
- Каждый узел имеет
0,1или2потомка. - Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.
Внимание: корень «программистского» дерева, в отличие от реального, находится сверху. Каждая ячейка называется вершиной, вершины соединены ребрами. Корень дерева — ячейка с номером 13. Левое поддерево вершины 3 выделено цветом на картинке снизу:
Наше дерево соответствует всем требованиям к бинарным деревьям. Это значит, что каждое его левое поддерево содержит только значения, которые меньше или равны значению вершины, правое — только значения большие или равные значению вершины. Оба левые и правые поддеревья сами являются бинарными поддеревьями.
Способ построения бинарного дерева — не единственный: ниже на картинке вы видите ещё один вариант для того же набора чисел, и их может быть очень много на практике.
Такая структура помогает проводить поиск: минимальное значение находим, двигаясь от вершины влево-вниз каждый раз.
Если нужно найти максимальное число — идем от вершины вниз и вправо. Нахождение числа, которое не является минимальным или максимальным также весьма простое. Мы спускаемся от корня влево или вправо в зависимости от того, больше или меньше наша вершина искомой. Так, если нам нужно найти число 89 мы проходим вот такой путь:
Еще можно выводить числа в порядке сортировки. Например, если нам нужно вывести все числа в порядке возрастания, берем левое поддерево и начиная с самой левой вершины идем наверх.
Прибавить что-то в дерево тоже просто. Главное помнить о структуре. Скажем, нам нужно добавить в дерево значение 7. Идем к корню, и проверяем. Число 7 < 13, поэтому идем влево. Там видим 5, и идем вправо, поскольку 7 > 5. Дальше поскольку 7 < 8 и 8 не имеет потомков, мы конструируем ветку от 8 влево и на неё цепляем 7.
Также можно удалять вершины из дерева, но это несколько сложнее.
Есть три разных сценария для удаления, которые мы должны учесть.
- Самый простой вариант: нам нужно удалить вершину, у которой нет потомков. Например, число
7, которое мы только что добавили. В таком случае мы просто проходим путь до вершины с этим числом и удаляем его. - У вершины есть одна вершина-потомок. В таком случае можно удалить нужную вершину, но её потомка нужно подсоединить к «дедушке», то есть вершине, из которой произрастал её непосредственный предок. Например, из того же дерева нужно удалить число
3. В таком случае, её потомка, единицу, вместе со всем поддеревом присоединяем к5. Это делается просто, поскольку все вершины, слева от5, будут меньше чем это число (и меньше, чем удалённая тройка). - Самый сложный случай — когда у удаляемой вершины есть два потомка. Теперь первым делом нам нужно найти вершину, в которой спрятано следующее большее значение, нужно поменять их местами, а потом удалить нужную вершину. Обратите внимание: следующая по значению вершина не может иметь двух потомков, тогда её левый потомок будет лучшим кандидатом на следующее значение.
Давайте из нашего дерева удалим корневую вершину 13. Сначала ищем самое близкое к 13 число, которое его больше. Это 21. Меняем 21 и 13 местами и удаляем 13.
Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка?
Все числа просто будут прибавляться в правую ветку предыдущего. Если мы захотим найти число, у нас не будет другого выхода, как просто идти по цепочке вниз.
Это ничуть не лучше, чем линейный поиск. Есть и другие структуры данных, более сложные. Но их мы пока рассматривать не будем. Скажем только, что для решения проблемы с построением дерева из отсортированного списка можно перемешать входные данные случайным образом.