Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действий:
- Отсортировать список и применить бинарный поиск.
- Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.
Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:
- Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов).
- Каждый узел имеет
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
.
Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка?
Все числа просто будут прибавляться в правую ветку предыдущего. Если мы захотим найти число, у нас не будет другого выхода, как просто идти по цепочке вниз.
Это ничуть не лучше, чем линейный поиск. Есть и другие структуры данных, более сложные. Но их мы пока рассматривать не будем. Скажем только, что для решения проблемы с построением дерева из отсортированного списка можно перемешать входные данные случайным образом.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ