Поиск по бинарному дереву. Эффективность поиска по бинарному дереву.

Вначале рассмотрим просто поиск по бинарному дереву.

Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рисунке ниже

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать n/2 элементов.

Наибольший эффект использования дерева достигается в том случае, когда дерево сбалансировано.

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

Поиск элемента в сбалансированном дереве называется бинарным поиском по дереву. Такое дерево называют деревом бинарного поиска.

При бинарном поиске по дереву перебирается не больше log₂N элементов. Другими словами, эффективность бинарного поиска по дереву имеет порядок O(log₂N).

Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше - правое.

 

 

Алгоритм поиска по бинарному дереву

p = tree

whlie p <> nil do

if key = k(p) then

search = p

return

endif

if key < k(p) then

p = left(p)

else

p = right(p)

endif

endwhile

search = nil

return

Очень часто следствием поиска являются ситуации:

если узел с заданным ключом не найден, то его надо вставить;

 

если узел с заданным ключом найден, то его надо удалить.

 

 

Поиск по бинарному дереву с включением.

Вначале рассмотрим просто поиск по бинарному дереву.

Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рисунке ниже

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать n/2 элементов.

Наибольший эффект использования дерева достигается в том случае, когда дерево сбалансировано.

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

Поиск элемента в сбалансированном дереве называется бинарным поиском по дереву. Такое дерево называют деревом бинарного поиска.

При бинарном поиске по дереву перебирается не больше log₂N элементов. Другими словами, эффективность бинарного поиска по дереву имеет порядок O(log₂N).

Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше - правое.