Дерево поиска

Обратите внимание на рисунок, приведенный выше. Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.

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

Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:

Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:

- если ключи совпадают, поиск завершен;

- если ключ в корне больше искомого, выполнить поиск в левом поддереве;

- если ключ в корне меньше искомого, выполнить поиск в правом поддереве.

Если дерево пусто, то искомый элемент не найден.

Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность: 1 6 8 10 20 21 25 30.

Можно организовать «зеркально симметричный» обход, начиная с правого поддерева, тогда получим упорядоченную по убыванию последовательность:

30 25 20 10 8 6 1.

Таким образом, деревья поиска можно применять для сортировки значений.