Разница между бинарным поиском и деревом двоичного поиска?

Ответ 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 )
    }
  }
}

Заключение

Как часто представляется, бинарный поиск относится к представленному здесь алгоритму на основе массива, а дерево бинарного поиска относится к структуре данных на основе дерева с определенными свойствами. Однако свойства, которые требует бинарный поиск, и свойства, которые имеют деревья бинарного поиска, делают эти две стороны одной и той же монеты. Быть бинарным деревом поиска часто подразумевает конкретную реализацию, но на самом деле это вопрос обеспечения определенных операций и удовлетворения определенных ограничений. Бинарный поиск - это алгоритм, который функционирует в структурах данных, которые выполняют эти операции и соответствуют этим ограничениям.

Ответ 2

Нет, они не то же самое.

Дерево двоичного поиска:

• Структура дерева
• Каждый node имеет до двух детей
• Левое поддерево node содержит только узлы с ключами меньше клавиши node
• В правом поддереве node содержатся только узлы с ключами, превышающими ключ node

Двоичный поиск:

• Алгоритм , который работает с упорядоченной структурой данных (обычно, но не обязательно, с массивом), и на каждом шаге просматривает значение в середине и рекурсирует либо влево, либо влево в зависимости от того, будет ли целевое значение меньше или больше значения в середине (или останавливается, если оно равно).

И, конечно, структура данных такова:

Конкретный способ хранения и организации данных на компьютере, чтобы он мог эффективно использоваться.

Пока algorithm:

Пошаговая процедура вычислений.

Процесс поиска в двоичном дереве поиска (где мы ищем конкретное значение в дереве) можно считать похожим на (или экземпляр, в зависимости от ваших определений и того, используете ли вы сбалансированный BST) бинарный поиск, так как это также смотрит на "средний" элемент и возвращает либо влево, либо вправо, в зависимости от результата сравнения между этим значением и целевым значением.

Ответ 3

Для тех, кто пришел сюда, чтобы быстро проверить, какой из них использовать. В дополнение к ответам, опубликованным выше, я хотел бы добавить сложности в отношении операций для обоих этих методов.

Дерево бинарного поиска:

Поиск: θ (log (n)), наихудший случай (O (n)) для несбалансированного BST,

Вставка узла: θ (log (n)), наихудший случай (O (n)) для несбалансированного BST

Удаление узла: θ (log (n)), наихудший случай (O (n)) для несбалансированного BST

Сбалансированное бинарное дерево поиска:

Поиск: log (n),

Вставка узла: O (log (n))

Удаление узла: O (log (n))

Бинарный поиск по отсортированному массиву:

Поиск: O (log (n)) Но,

Вставка узла: невозможно, если массив статически размещен и уже заполнен. В противном случае O (n) (O (n) для перемещения больших элементов массива к смежным справа)

Удаление узла: O (log (n)) + O (n). (Таким образом, было бы O (log (n)) для нахождения позиции удаления + O (n) для перемещения более крупных элементов массива к смежным слева)

Таким образом, исходя из ваших требований, вы можете выбрать, нужно ли вам быстро вставлять и удалять. Если вам это не нужно, то хранение вещей в отсортированном массиве будет работать для вас, так как массив займет меньше памяти по сравнению с деревом

Ответ 4

Двоичное дерево поиска - это просто структура данных, а не алгоритмы, тогда как бинарный поиск - это алгоритм, в котором он сравнивает значение ключа поиска с ключевым значением среднего элемента массива. Если ключи совпадают, то найден соответствующий элемент и возвращается его индекс или позиция. В противном случае, если ключ поиска меньше, чем ключ среднего элемента, тогда алгоритм повторяет свое действие в подмассиве слева от среднего элемента или, если ключ поиска больше, в поддиапазоне справа. Если оставшийся массив, подлежащий поиску, пуст, тогда ключ не может быть найден в массиве, и возвращается специальное "не найденное" значение