Бинарное дерево поиска
I. Понятие и введение
Двоичное дерево поиска (англ.: Binary Search Tree), также известное как бинарное дерево поиска, бинарное дерево поиска, упорядоченное двоичное дерево или отсортированное двоичное дерево. Оно удовлетворяет следующим условиям:
- Если его левое поддерево не пусто, все значения узлов в левом поддереве меньше значения его корневого узла.
- Если его правое поддерево не пусто, все значения узлов в правом поддереве больше значения его корневого узла.
Его левое и правое поддеревья также являются двоичными деревьями поиска.
Как показано на рисунке ниже:
II. Примечания по применимости
Двоичные деревья поиска имеют эффективные операции вставки, удаления и поиска.
Средняя временная сложность —O(log n), в худшем случае —O(n). Двоичные деревья поиска отличаются от куч; они не обязательно являются полными двоичными деревьями, и нижний уровень не легко представить напрямую с помощью массивов, поэтому для реализации двоичных деревьев поиска используются связанные списки.
| Поиск элемента | Вставка элемента | Удаление элемента | |
|---|---|---|---|
| Обычный массив | O(n) | O(n) | O(n) |
| Упорядоченный массив | O(logn) | O(n) | O(n) |
| Бинарное дерево поиска | O(logn) | O(logn) | O(logn) |
Ниже мы сначала представим метод двоичного поиска в виде массива как концептуальную основу, а затем продолжим знакомство с методом поиска в двоичных деревьях поиска.
III. Иллюстрация процесса метода двоичного поиска
Идея двоичного поиска была предложена в 1946 году. Задача поиска — очень важная фундаментальная задача в информатике. Двоичный поиск можно использовать только для упорядоченных последовательностей. Если мы хотим найти элемент, сначала смотрим на соотношение между средним значением V массива и целевыми данными. Возможны три случая:
- 1. Если оно равно целевым данным, оно найдено сразу.
- 2. Если оно меньше V, продолжаем поиск в группе меньше V.
- 2. Если оно больше V, продолжаем поиск в группе больше V.
IV. Пример кода на Java
Загрузка пакета исходного кода:Скачать
Код файла src/example/binary/BinarySearch.java:
/**
* Метод бинарного поиска
*/
public class BinarySearch {
// Метод бинарного поиска: найти target в отсортированном массиве arr
// Если target найден, вернуть соответствующий индекс
// Если target не найден, вернуть -1
public static int find(Comparable[] arr, Comparable target) {
// найти target в arr[l...r]
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// чтобы предотвратить переполнение целых чисел в экстремальных случаях, используйте следующую логику для вычисления mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}