Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действий:
- Отсортировать список и применить бинарный поиск.
- Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.
Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:
- Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов).
- Каждый узел имеет
0
,1
или2
потомка. - Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.
![Бинарное дерево - 1](https://cdn.javarush.com/images/article/4950f44a-3e5f-4650-bc02-53851892b34a/original.png)
Внимание: корень «программистского» дерева, в отличие от реального, находится сверху. Каждая ячейка называется вершиной, вершины соединены ребрами. Корень дерева — ячейка с номером 13
. Левое поддерево вершины 3 выделено цветом на картинке снизу:
![Бинарное дерево - 2](https://cdn.javarush.com/images/article/41771953-5122-455a-b111-f03572bfb260/original.png)
Наше дерево соответствует всем требованиям к бинарным деревьям. Это значит, что каждое его левое поддерево содержит только значения, которые меньше или равны значению вершины, правое — только значения большие или равные значению вершины. Оба левые и правые поддеревья сами являются бинарными поддеревьями.
Способ построения бинарного дерева — не единственный: ниже на картинке вы видите ещё один вариант для того же набора чисел, и их может быть очень много на практике.
![Бинарное дерево - 3](https://cdn.javarush.com/images/article/582dd74f-7e55-4e98-a780-33ab8a704929/original.png)
Такая структура помогает проводить поиск: минимальное значение находим, двигаясь от вершины влево-вниз каждый раз.
![Бинарное дерево - 4](https://cdn.javarush.com/images/article/919e78a5-84bc-4534-be57-f0944b1ef241/original.png)
Если нужно найти максимальное число — идем от вершины вниз и вправо. Нахождение числа, которое не является минимальным или максимальным также весьма простое. Мы спускаемся от корня влево или вправо в зависимости от того, больше или меньше наша вершина искомой. Так, если нам нужно найти число 89
мы проходим вот такой путь:
![Бинарное дерево - 5](https://cdn.javarush.com/images/article/8e97f2fc-fd33-4a37-82f5-d8d95e86c9b0/original.png)
Еще можно выводить числа в порядке сортировки. Например, если нам нужно вывести все числа в порядке возрастания, берем левое поддерево и начиная с самой левой вершины идем наверх.
Прибавить что-то в дерево тоже просто. Главное помнить о структуре. Скажем, нам нужно добавить в дерево значение 7
. Идем к корню, и проверяем. Число 7 < 13
, поэтому идем влево. Там видим 5
, и идем вправо, поскольку 7 > 5
. Дальше поскольку 7 < 8
и 8
не имеет потомков, мы конструируем ветку от 8
влево и на неё цепляем 7
.
![Бинарное дерево - 6](https://cdn.javarush.com/images/article/06f4d405-0e29-4531-b721-64bf423b8a9f/original.png)
![Бинарное дерево - 7](https://cdn.javarush.com/images/article/18f0f97e-3c75-4d16-8014-d24824e59cb5/original.png)
Также можно удалять вершины из дерева, но это несколько сложнее.
Есть три разных сценария для удаления, которые мы должны учесть.
- Самый простой вариант: нам нужно удалить вершину, у которой нет потомков. Например, число
7
, которое мы только что добавили. В таком случае мы просто проходим путь до вершины с этим числом и удаляем его. - У вершины есть одна вершина-потомок. В таком случае можно удалить нужную вершину, но её потомка нужно подсоединить к «дедушке», то есть вершине, из которой произрастал её непосредственный предок. Например, из того же дерева нужно удалить число
3
. В таком случае, её потомка, единицу, вместе со всем поддеревом присоединяем к5
. Это делается просто, поскольку все вершины, слева от5
, будут меньше чем это число (и меньше, чем удалённая тройка). - Самый сложный случай — когда у удаляемой вершины есть два потомка. Теперь первым делом нам нужно найти вершину, в которой спрятано следующее большее значение, нужно поменять их местами, а потом удалить нужную вершину. Обратите внимание: следующая по значению вершина не может иметь двух потомков, тогда её левый потомок будет лучшим кандидатом на следующее значение.
![Бинарное дерево - 8](https://cdn.javarush.com/images/article/20c2d6f6-3b19-47f7-b680-1f7356f32b2e/original.png)
Давайте из нашего дерева удалим корневую вершину 13
. Сначала ищем самое близкое к 13
число, которое его больше. Это 21
. Меняем 21
и 13
местами и удаляем 13
.
![Бинарное дерево - 9](https://cdn.javarush.com/images/article/cb4475f7-e7f4-40f7-ae61-819e8d5d26d1/original.png)
![Бинарное дерево - 10](https://cdn.javarush.com/images/article/3138f714-e313-441e-a2eb-232b58a8a982/original.png)
Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка?
![Бинарное дерево - 11](https://cdn.javarush.com/images/article/39b1020d-a322-4a2b-8139-6af20116eb34/original.png)
Все числа просто будут прибавляться в правую ветку предыдущего. Если мы захотим найти число, у нас не будет другого выхода, как просто идти по цепочке вниз.
![Бинарное дерево - 12](https://cdn.javarush.com/images/article/d2b911bb-f9f9-4556-af88-d6d4a0013520/original.png)
Это ничуть не лучше, чем линейный поиск. Есть и другие структуры данных, более сложные. Но их мы пока рассматривать не будем. Скажем только, что для решения проблемы с построением дерева из отсортированного списка можно перемешать входные данные случайным образом.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ