ДЕРЕВО ПОИСКА

Бинарные деревья часто используются для представления множества данных, среди которых идет поиск элементов по уникальному ключу. Если дерево организовано так, что для каждого узла t все ключи его левого поддерева меньше ключа /, а все ключи правого поддерева больше ключа t, то такое дерево будем называть деревом поиска. В нем легко найти элемент с нужным ключом — достаточно, начав с корня, двигаться в левое или правое поддерево на основании сравнения заданного ключа с ключом текущего узла. Известно, что из п элементов можно построить бинарное дерево с высотой не более log₂ п , поэтому, если дерево идеально сбалансировано, поиск среди его п элементов выполняется максимум за log₂ п сравнений. Подобные деревья широко используются и для сортировки больших массивов данных, так как обход дерева поиска слева направо дает отсортированную в порядке возрастания последовательность ключей.

При обходе слева направо дерева поиска, приведенного на рис. 3.6, получается последовательность: 1,4, 8, 9, 11, 15, 20.

Рис. 3.6. Дерево поиска

ОПЕРАЦИИ НАД ДЕРЕВОМ ПОИСКА

Над деревом поиска могут быть выполнены все операции, определенные для бинарного дерева. Но в основном к дереву поиска применяются операции, определяемые особенностями его организации:

• • поиск элемента с заданным ключом Key в дереве и возвращение адреса элемента, если он найден, в противном случае возвращается значение nil — операция Addr(Key);
• • поиск по дереву с включением — поиск элемента с ключом Key в дереве, подключение узла с этим ключом, если поиск был неудачным (элемент с ключом Key не найден), и возвращение адреса элемента с заданным ключом — операция Search(Key);
• • поиск по дереву с исключением — поиск элемента с заданным ключом в дереве и исключение этого элемента, если он найден, — операция Delete(Key); после исключения дерево должно остаться деревом поиска.

Для построения дерево поиска, можно использовать операцию поиска по дереву с включением Search(Key), считывая из входного потока элементы с заданными ключами и включая их в дерево поиска.

Операция Search(Key) может быть построена таким образом, что она будет включать в дерево элемент и в том случае, если он уже существует в дереве. Использование такой операции для построения дерева поиска позволяет построить дерево с повторяющимися ключами.