Сортирующее дерево

Бинарным деревом поиска называется бинарное дерево из элементов, в котором ключ элемента в каждой вершине больше ключей всех элементов левого поддерева и меньше ключей элементов правого поддерева. Ниже приведен пример бинарного дерева поиска с числовыми значениями ключей.

Можно схему бинарного поиска в таблице, упорядоченной по возрастанию ключей, представить деревом поиска. В корне будет находиться элемент со средним индексом, элементы со средними индексами верхней и нижней половин таблицы составят значения левого и правого сыновей корня, следующий уровень вершин составят средние элементы всех четвертей таблицы и так далее.
Дерево поиска удобно для нахождения элемента с заданным ключом. Этот ключ сначала сравнивается с ключом корня. Если ключ корня больше, то переходим к левому сыну корня, иначе – к правому. Процесс продолжается в направлении от корня к листьям до нахождения элемента или получения отрицательного результата.
Деревья поиска применяют, например, в трансляторах для хранения и быстрого поиска ключевых слов или идентификаторов программы.
Наряду с поиском деревья поиска обеспечивают сортировку элементов. Действительно, обход дерева в порядке слева направо дает перечисление элементов по возрастанию ключей.
Включение нового элемента в дерево поиска выполняется следующим образом. Сначала производится поиск элемента с ключом, равным ключу нового элемента. После прихода в лист элемент войдет в новую вершину дерева, которая будет левым или правым сыном найденного листа в зависимости от значения ключа элемента.
Удаление элемента из дерева поиска предполагает такую перестройку дерева, чтобы оно не содержало указанного элемента, но оставалось деревом поиска. Возможны следующие три случая при удалении элемента из дерева поиска.

Удаляемый элемент находится в листе дерева. В этом случае удаляется соответствующая ссылка из отцовской вершины.
Удаляемый элемент находится в вершине с одним сыном. На место вершины с данным элементом помещается ее единственный сын со всеми своими потомками, то есть подтягивается все поддерево по имеющейся ветви.
Удаляемый элемент находится в вершине с обоими сыновьями. Сначала на место удаляемого элемента помещается один из двух элементов с соседними значениями ключа. Это может быть элемент с меньшим значением ключа из самой правой вершины левого поддерева либо с большим значением ключа из самой левой вершины правого поддерева. Для нахождения вершины с этим элементом достаточно спуститься из вершины с удаляемым элементом по левой ветви и далее идти по правым ветвям, пока это возможно, либо аналогичным образом найти этот элемент в правом поддереве. Найденная вершина имеет не более одного сына, поэтому дальнейшие действия сводятся к одному из первых двух случаев.

Например, удаление элемента с ключом 20 из дерева поиска, приведенного выше, даст следующий результат

Рассмотрим следующую задачу. С клавиатуры вводится последовательность слов. Требуется последовательно включать эти слова в дерево поиска, учитывая число вхождений каждого слова. Далее обеспечить удаление некоторых слов. При удалении уменьшать счетчик числа повторений слова и полностью удалять слово при обнулении этого счетчика. После каждой операции выдавать дерево поиска на экран, перечисляя вершины по алфавиту слов с указанием уровня вершин и счетчика повторений.

Сортировка выбором с помощью бинарного дерева или турнирная сортировка выполняется следующим образом. Элементы массива делятся на пары и образуют нижний уровень бинарного дерева. Минимальные элементы каждой пары составляют предпоследний уровень и в свою очередь делятся на пары и т. д. В итоге в корне дерева оказывается минимальный элемент, который выбирается для обработки. Затем он замещается в дереве величиной ¥, и процесс повторяется. Турнирная сортировка обязана своим названием схемой сравнений, напоминающей турнир с выбываниями. Метод отличается высокой скоростью, но требует больших затрат памяти для организации дерева, поэтому применяется редко.