Ответ 1
Двоичные поисковые деревья
Узел в двоичном дереве - это структура данных, которая имеет элемент и ссылку на два других двоичных дерева, обычно называемых левым и правым поддеревьями. То есть узел представляет интерфейс, подобный этому:
Node:
element (an element of some type)
left (a binary tree, or NULL)
right (a binary tree, or NULL)
Двоичное дерево поиска - это двоичное дерево (т.е. Узел, обычно называемый корнем) со свойством того, что левое и правое поддеревья также являются двоичными деревьями поиска, и что все элементы всех узлов в левом поддереве меньше корневой элемент и все элементы всех узлов в правом поддереве больше корневого элемента. Например,
5
/ \
/ \
2 8
/ \ / \
1 3 6 9
Бинарный поиск
Бинарный поиск - это алгоритм поиска элемента в бинарном дереве поиска. (Это часто выражается как способ поиска упорядоченной коллекции, и это эквивалентное описание. Я опишу эквивалентность позже.) Вот это:
search( element, tree ) {
if ( tree == NULL ) {
return NOT_FOUND
}
else if ( element == tree.element ) {
return FOUND_IT
}
else if ( element < tree.element ) {
return search( element, tree.left )
}
else {
return search( element, tree.right )
}
}
Обычно это эффективный метод поиска, потому что на каждом этапе вы можете удалить половину пространства поиска. Конечно, если у вас плохо сбалансированное бинарное дерево поиска, оно может быть неэффективным (оно может ухудшиться до линейного поиска). Например, он имеет низкую производительность в дереве, как:
3
\
4
\
5
\
6
Бинарный поиск по массивам
Двоичный поиск часто представляется как метод поиска для отсортированных массивов. Это не противоречит приведенному выше описанию. Фактически, это подчеркивает тот факт, что нам на самом деле все равно, как реализовано двоичное дерево поиска; мы просто заботимся о том, чтобы взять объект и сделать с ним три вещи: получить элемент, получить левый подобъект и получить правый подобъект (при условии, конечно, ограничений на элементы в левом существе) меньше элемента, а элементы справа больше и т.д.).
Мы можем сделать все три вещи с отсортированным массивом. В отсортированном массиве "элемент" - это средний элемент массива, левый подобъект - это подрешетка слева от него, а правый подобъект - это подрешетка справа от него. Например, массив
[1 3 4 5 7 8 11]
соответствует дереву:
5
/ \
/ \
3 8
/ \ / \
1 4 7 11
Таким образом, мы можем написать метод двоичного поиска для массивов, например:
search( element, array, begin, end ) {
if ( end <= begin ) {
return NOT_FOUND
}
else {
midpoint = begin+(end-begin)/2
a_element = array[midpoint]
if ( element == midpoint ) {
return FOUND_IT
}
else if ( element < midpoint ) {
return search( element, array, begin, midpoint )
}
else {
return search( element, array, midpoint, end )
}
}
}
Заключение
Как часто представляется, бинарный поиск относится к представленному здесь алгоритму на основе массива, а дерево бинарного поиска относится к структуре данных на основе дерева с определенными свойствами. Однако свойства, которые требует бинарный поиск, и свойства, которые имеют деревья бинарного поиска, делают эти две стороны одной и той же монеты. Быть бинарным деревом поиска часто подразумевает конкретную реализацию, но на самом деле это вопрос обеспечения определенных операций и удовлетворения определенных ограничений. Бинарный поиск - это алгоритм, который функционирует в структурах данных, которые выполняют эти операции и соответствуют этим ограничениям.