Дерево сортировки

Определения и обозначения

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

Корень — первая вершина дерева, от которой строится его структура. В неё помещают первое число последовательности, потому что вначале сравнивать его не с чем. От корня начинаются пути, по которым размещают все остальные значения.

Левый и правый потомки — вершины, связанные с родительской вершиной; их положение определяется сравнением значений. Если новое число меньше текущего, поиск места продолжают через левого потомка, а если больше — через правого. Сравнения на каждом шаге помогают выбрать нужную ветвь и не проверять сразу все вершины дерева.

Лист — вершина, у которой нет потомков. Если при вставке числа мы пришли к свободному месту под такой вершиной, новое значение можно разместить там. Листом может стать вершина, после которой дальнейший путь пока не построен.

Как это устроено

Начинают с последовательности чисел и берут её первое значение: оно становится корнем. Далее каждое новое число сравнивают с вершиной, начиная с корня. Так дерево строится постепенно, а каждое сравнение подсказывает, в какую часть уже созданной структуры идти дальше.

Если новое значение меньше текущего, переходят влево; если больше — вправо. Это правило сохраняет порядок: в левой части оказываются меньшие значения, а в правой — большие. В выбранной вершине сравнение повторяют, пока не встретится пустое место, куда можно поставить число. Благодаря этому не нужно выбирать место наугад или переставлять уже добавленные числа.

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

Чтобы получить отсортированную последовательность, используют обход: сначала полностью обходят левое поддерево, затем посещают текущую вершину и после этого обходят правое поддерево. Поддеревом называют часть дерева, которая начинается от выбранной вершины и включает её потомков. Такой порядок обхода называют «левое поддерево — вершина — правое поддерево». Он работает потому, что меньшие значения лежат слева, а большие — справа.

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

Построение дерева и получение результата

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

Если числа равны, воспользуйтесь заранее выбранным правилом: например, направляйте их вправо. После размещения всех значений выполните обход в указанном порядке.

Разбор задач

Задача 1

Условие. Постройте дерево сортировки для последовательности 5, 2, 7 и запишите результат обхода. Здесь достаточно двух сравнений: оба новых числа сравниваются с корнем. Затем применим обход от левой ветви к правой.

1. Первое число 5 становится корнем дерева.
2. Число 2 меньше 5, поэтому помещаем его слева от корня.
3. Число 7 больше 5, поэтому помещаем его справа от корня.
4. Обходим сначала левую вершину 2, затем посещаем корень 5 и после него правую вершину 7.

Ответ: дерево имеет корень 5, левого потомка 2 и правого потомка 7. Результат обхода — 2, 5, 7.

Задача 2

Условие. Постройте дерево для последовательности 8, 3, 10, 1, 6, 14 и получите упорядоченную последовательность. Здесь некоторые значения нужно сравнить не только с корнем, но и с потомками. Поэтому важно каждый раз продолжать путь, а не выбирать место сразу.

1. 8 становится корнем. Число 3 меньше 8 и занимает место слева, а 10 больше 8 и занимает место справа.
2. Число 1 меньше 8, переходим к 3; оно меньше 3, значит, размещаем его слева от 3.
3. Число 6 меньше 8, поэтому переходим к 3; оно больше 3, значит, ставим его справа от 3.
4. Число 14 больше 8, затем больше 10, поэтому помещаем его справа от 10.
5. Для обхода сначала читаем левую часть: 1, 3, 6; затем корень 8; потом правую часть: 10, 14.

Ответ: 1, 3, 6, 8, 10, 14. На пути к месту для 6 понадобились сравнения сначала с 8, затем с 3: каждое из них определило следующий шаг.

Задача 3

Условие. Для последовательности 6, 2, 9, 1, 4, 8, 11 постройте дерево. Затем выясните, как изменятся дерево и результат, если первым поставить 1. Сравнивать нужно не только значения, но и порядок их поступления: именно он определяет, какой элемент окажется корнем.

1. В исходной последовательности 6 становится корнем; 2 идёт влево, 9 — вправо.
2. Число 1 меньше 6 и меньше 2, поэтому ставим его слева от 2. Число 4 меньше 6, но больше 2, поэтому оно становится правым потомком 2.
3. Число 8 больше 6, но меньше 9, поэтому ставим его слева от 9. Число 11 больше 6 и больше 9, поэтому оно становится справа от 9.
4. Если начать с 1, корнем станет 1. Все остальные числа больше него, поэтому сначала они пойдут вправо; дальнейшие сравнения разместят их по ветвям согласно тому же правилу.
5. В обоих случаях прочитайте значения обходом «левое поддерево — вершина — правое поддерево».

Ответ: исходный обход даёт 1, 2, 4, 6, 8, 9, 11; при корне 1 дерево будет другой формы, но обход даст те же числа по возрастанию. Различается устройство ветвей, а не набор значений и не результат сортировки.

Типичные ошибки

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

Ошибка: принять порядок вставки за результат сортировки. Числа добавляют в том порядке, в каком они даны, и он может не быть упорядоченным. Это легко перепутать, потому что вставка уже использует сравнения. Чтобы проверить себя, отдельно выполните обход и запишите значения именно в порядке «левое поддерево — вершина — правое поддерево».

Ошибка: посещать вершину раньше левого поддерева или пропускать правое. Тогда часть меньших значений может оказаться записана после больших либо не попасть в ответ. Причина часто в том, что порядок обхода вспоминают не полностью. Проверяйте каждую вершину по одному правилу: сначала её левая часть, потом она сама, затем правая часть.

Ошибка: не задавать правило для одинаковых значений. Равные числа не меньше и не больше друг друга, поэтому без договорённости непонятно, куда их ставить. Из-за этого один и тот же набор можно построить по-разному даже при одинаковом порядке чисел. Перед вставкой выберите сторону для равных значений и проверьте, что во всех случаях поступаете одинаково.

Связь с другими темами

Чтобы строить дерево сортировки, нужно уметь сравнивать числа и упорядочивать их — это опирается на знакомые действия с числами. Здесь порядок получают не простым расположением значений в строке, а построением структуры и её обходом. Деревья и обходы встречаются при изучении структур данных: так называют способы хранить и организовывать информацию. Эти идеи пригодятся при знакомстве с алгоритмами поиска, когда нужно находить значение среди множества данных.

Что запомнить

• Первое значение становится корнем дерева.
• При вставке меньшее значение направляют влево, большее — вправо.
• Каждое новое значение сравнивают с вершинами на пути от корня.
• Форма дерева зависит от порядка поступления значений.
• Обход «левое поддерево — вершина — правое поддерево» выдаёт значения по возрастанию.
• Для одинаковых значений нужно соблюдать единое правило размещения.