Поиск по бинарному дереву
Назначение его в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рис. 5.8.
В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать N/2 элементов.
Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано.В этом случае для поиска придотся перебрать не больше log2N
элементов.
Строго сбалансированное дерево - это дерево, в котором каждый узел имеет левое и правое поддеревья, отличающиеся по уровню не более, чем на единицу.
Поиск элемента в бинарном дереве называется бинарным поиском по дереву.
Такое дерево называют деревом бинарного поиска.
Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше - правое.
Пусть задан аргумент key
| 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 | p := tree;
whlie p <> nil do begin if key = p^.k then begin search := p; exit; end; if key < p^.k then p := p^.left else p := p^.right; end; search := nil; |
