Что такое бинарное дерево поиска?

Двоичное дерево поиска | Набор 1 (Поиск и вставка)

Что такое бинарное дерево поиска?

Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов, которая обладает следующими свойствами:

• 
  Левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла.
  
• 
  Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла.
  
• 
  из левого и правого поддеревьев также должно быть бинарным деревом поиска.
  Там должен быть нет дубликат узлы .
  

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

Как искать ключ в заданном двоичном дереве?

Для поиска значения, если бы у нас был отсортированный массив, мы могли бы выполнить бинарный поиск. Допустим, мы хотим найти число в массиве, в двоичном поиске мы сначала определяем полный список как наше пространство поиска, число может существовать только в пределах пространства поиска. Теперь мы сравниваем искомое число или искомый элемент со средним элементом (медианой) пространства поиска, и если искомая запись меньше среднего элемента, мы ищем в левой половине, иначе ищем в правой половине, в случае равенства мы нашли элемент. В бинарном поиске мы начинаем с «n» элементов в пространстве поиска, и если средний элемент не является элементом, который мы ищем, мы уменьшаем пространство поиска до «n/2», мы продолжаем сокращать пространство поиска, пока не найдем либо запись, которую мы ищем, или мы доберемся только до одного элемента в пространстве поиска и покончим со всем этим сокращением.
Операции поиска в бинарных деревьях поиска будут очень похожими. Допустим, мы хотим найти число, мы начинаем с корня, а затем сравниваем искомое значение со значением корня, если оно равно, мы закончили поиск, если оно меньше, мы знаем, что нам нужно перейти к левому поддереву , потому что в бинарном дереве поиска все элементы в левом поддереве меньше, а все элементы в правом поддереве больше. Поиск элемента в бинарном дереве поиска — это в основном такой обход, на каждом шаге мы идем влево или вправо и на каждом шаге отбрасываем одно из поддеревьев. Если дерево сбалансировано (мы называем дерево сбалансированным, если для всех узлов разница между высотами левого и правого поддеревьев не больше единицы), мы начинаем с пространства поиска из «n» узлов и по мере отбрасывания одного из поддеревьев -trees, мы отбрасываем 'n/2' узлов, поэтому наше пространство поиска сокращается до 'n/2'. На следующем шаге мы уменьшаем пространство поиска до «n/4» и повторяем до тех пор, пока не найдем элемент или наше пространство поиска не уменьшится до одного узла. Поиск здесь также является бинарным поиском, отсюда и название ; Бинарное дерево поиска.


С++

// Функция C для поиска заданного ключа в заданном BST структура узел* поиск( структура узел* корень, интервал ключ) { // Базовые случаи: корень равен нулю или ключ присутствует в корне если (корень == NULL || корень->ключ == ключ) возвращаться корень; // Ключ больше, чем ключ root если (корень-> ключ < ключ) возвращаться поиск(корень->право, ключ); // Ключ меньше, чем ключ root возвращаться поиск(корень->слева, ключ); } Ява // Вспомогательная функция для поиска заданного ключа в BST публичный Поиск узла (корень узла, int ключ) { // Базовые случаи: корень равен нулю или ключ присутствует в корне если (корень == ноль || root.key == ключ) возвращаться корень;   // Ключ больше, чем ключ root если ( root.key < ключ) возвращаться поиск( root.right , ключ);   // Ключ меньше, чем ключ root возвращаться поиск( корень.слева , ключ); }

питон
# Вспомогательная функция для поиска заданного ключа в BST
деф поиск ( корень, ключ ):
 
# Базовые случаи: корень равен нулю или ключ присутствует в корне
если корень Никто или же корень.val == ключ:
возвращаться корень
 
# Ключ больше, чем ключ root
если root.val < ключ:
возвращаться поиск( корень.право,ключ )
 
# Ключ меньше, чем ключ root
возвращаться поиск( корень.слева,ключ )
 
# Этот код предоставлен Бхавья Джайн

С#
// Вспомогательная функция для поиска

// заданный ключ в BST
публичный Поиск узла (корень узла,
инт ключ)
{
// Базовые случаи: корень равен нулю
// или ключ присутствует в корне
если (корень == ноль ||
root.key == ключ)
возвращаться корень;
 
// Ключ больше, чем ключ root
если ( root.key < ключ)
возвращаться поиск( root.right , ключ);
 
// Ключ меньше, чем ключ root
возвращаться поиск( корень.слева , ключ);
}
 
// Этот код предоставлен gauravrajput1

JavaScript

// Вспомогательная функция для поиска // заданный ключ в BST функция поиск(корень, ключ) { // Базовые случаи: корень равен нулю // или ключ присутствует в корне если (корень == ноль || root.key == ключ) возвращаться корень;   // Ключ больше, чем ключ root если ( root.key < ключ) возвращаться поиск( root.right , ключ);   // Ключ меньше, чем ключ root возвращаться поиск( корень.слева , ключ); }   // Этот код предоставлен rrrtnx .