Двоичные деревья и их роль в информатике

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    ГЛАВА II. ДВОИЧНЫЕ ДЕРЕВЬЯ В ИНФОРМАТИКЕ 

    2.1. Сортировка данных 

    2.1.1. Метод дерева сортировки 

    Процедура сортировки по методу дерева происходит в два этапа. Предположим нам  даны элементы множества А в качестве неупорядоченного (несортированного) списка а₁, а₂, …, а_N. На первом этапе список используется, чтобы сконструировать дерево сортировки, у которого вершинами являются элементы множества А и корнем является элемент а₁ – первый элемент несортированного списка. Второй этап позволяет получить сортированный список на основании дерева сортировки.

    Прежде  чем перейти к общей процедуре  реализации данного метода рассмотрим следующий пример.

    Пример. Предположим, что начальный список – 6, 2, 9, 4, 15, 1, 12, 7, 20, 10, 3, 11, и требуется его отсортировать по возрастающей. Последовательность деревьев сортировки получается путем добавления каждого элемента списка в определенное место (очередь) в качестве листовой вершины. Множество вершин окончательного (заключительного) дерева сортировки содержит все элементы исходного списка.

    Итак, первый элемент 6 определен в качестве корня. Так как 2 ≤ 6, то мы создаем левую от корня ветку с вершиной 2 на ее конце.

    Затем, так как 9 ≥ 6, то мы  создаем правую для корня 6 ветку и размещаем на ее конце 9.

    Отсортируем следующий элемент 4, для этого  сначала сравним его с корнем 6. так как 4 ≤ 6, то мы должны разместить 4 в левое для корня 6 поддерево. Таким образом, мы рассматриваем левое поддерево, у которого корень – 2. теперь 4 ≥ 2, поэтому мы создаем правую ветку для вершины 2 и на конце этой ветки размещаем вершину 4.

    При вставке следующего элемента 15 мы руководствуемся следующими соображениями: 15 ≥ 6, поэтому идем по правому для корня 6 поддереву к вершине – 9; 15 ≥ 9, поэтому создаем правую ветку для вершины 9 и размещаем на втором уровне вершин.

    На  данной стадии мы построили (выстроили) следующее дерево сортировки (рис. 5):

    

    Будем продолжать наращивать дерево, аналогичным  образом  добавляя остальные элементы исходного списка. Чтобы вставить элемент х, мы сначала сравниваем его с корнем 6. если х  ≤ 6 идем по левому поддереву; иначе идем по правому поддереву. Повторяем сравнение х с корнем нового дерева. На некоторой стадии сложится такая ситуация, при которой у нас не будет ни левого, ни правого поддерева, по которому можно было бы идти, и тогда следует добавить х в качестве левого или правого ребенка.

    Развитие  рассматриваемого процесса применительно  к оставшимся элементам не отсортированного списка показана на рис.6, последнее дерево вмещает в себя уже все элементы исходного списка.

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

    

    Требуемая процедура внесения в список может  быть описана рекурсивно следующим  образом:

1. вносим в список элементы из левого поддерева корня,
2. вносим в список непосредственно сам корень, и
3. вносим в список элементы из правого поддерева корня.

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

    Проиллюстрируем как работает этот метод на некотором шаге. Рассмотрим поддерево, изображенное на рисунке 7.

    

    Чтобы обработать это дерево сортировки, мы начинаем составлять список элементов, в который помещаем сначала элементы дерева сортировки, находящиеся в левом поддереве. В данном случае первым таким элементом будет (1). Далее вносим корневой элемент (2). Затем вносим в список элементы, находящиеся в правом поддереве. Чтобы вносить в список элементы правого поддерева, мы снова осуществляем три описанных шага. Описанный алгоритм дает список 1, 2, 3, 4, и на этом заканчивается первая стадия для главного дерева.

    Вторая  стадия начинается с внесения в список элемента 6 – корня основного  дерева сортировки. Далее мы должны внести в список элементы правого поддерева по аналогии с описанным алгоритмом. Окончательный список в результате сортировки будет 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 15, 20.

    Опишем  процедуру составления списка для  общего случая дерева сортировки, которая состоит из двух этапов:

1. построение дерева сортировки на основе произвольного списка элементов;
2. составление списка упорядоченных элементов на основе дерева сортировки.

    Этап 1. построение дерева сортировки.

    Предположим, что а₁, а₂, …, а_N – исходный, не отсортированный список элементов. Работая с элементами этого списка, мы на каждом шаге присоединяем к дереву сортировки ровно одну ветку. Каждый раз, когда элемент обработан, мы добавляем к дереву ветку с листовой вершиной, которая впоследствии может стать родителем. В самом начале процедуры построения дерева сортировки самый первый элемент а₁ определяется, как корневой элемент дерева и при этом мы получаем дерево сортировки, у которого корень имеет непустые левые и правые поддеревья.

    Добавление  ветки с элементом «х» на конец  происходит следующим образом. Сравниваем элемент «х» с корнем; если х  ≤ v^* переходим к корню левого поддерева, иначе к корню правого поддерева. Далее мы сравниваем «х» с корнем соответствующего поддерева и все повторяем снова.

    Итак, построение дерева сортировки реализует  следующий алгоритм.

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

1. для множества, состоящего всего лишь из одного элемента, этот элемент и является корнем, а дерево сортировки представляет собой дерево сортировки с одним элементом, который является вершиной этого дерева. Для множества не из одного элемента первый элемент выбираем корнем.
2. элемент а_n сравниваем с корнем. Если а_n ≤ корня, то переходим к левому поддереву. Если левое поддерево пусто, то добавляем а_n в качестве левого ребенка корня. Если корень ≤ а_n, то переходим к правому поддереву. Если правое поддерево пусто, то добавляем а_n в качестве правого ребенка корня. Чтобы образовать следующее дерево сортировки, увеличиваем n до n+1 и повторяем шаг 2.

 

    

Метод кучи 

    Алгоритм  сортировка кучи использует специальный вид двоичного дерева, называемого «кучей», и в данном случае вершины двоичного дерева – элементы списка, который нужно сортировать. «Форма»  кучи выбирается такой, чтобы она имела минимальную высоту при заданном числе имеющихся вершин. Это достигается в результате такого подхода застройки дерева, при котором, если мы отбросим самый высокий уровень дерева, то остальная часть дерева одновременно окажется полной и совершенной. Кроме того, листовые вершины на самом высоком уровне оказываются расположенными на диаграмме максимально далеко слева.

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

    Этап 1. Создание кучи.

    Пусть задан не отсортированный список   а₁, а₂, …, а_N. Множество, состоящее из одного элемента, представляет собой тривиальный случай. Предположим, что элементы а₁, а₂, …, а_к-1 уже были сформированы в виде кучи, и мы должны добавить следующий элемент а_к. Имеется единственная позиция, при которой, добавляя а_к, мы удовлетворяем условиям определения ниспадающей кучи. Это либо ближайшая правая позиция от самой правой вершины на самом высоком уровне, либо, если самый высокий уровень полностью укомплектован, крайняя левая позиция на новом более высоком уровне.

    Однако  добавление а_к в такое положение еще не гарантирует с неизбежностью образование кучи.

    Создание  кучи из исходного списка а₁, а₂, …, а_N может быть получено на основании следующего алгоритма.

    Алгоритм  создания кучи:

1. Множество а₁ – корень.
2. Добавляем следующий элемент таким образом, чтобы дерево удовлетворяло условиям 1 и 2 из определения кучи.
3. Если необходимо, восстанавливаем кучу по методу «пузырькового» подъема новой вершины вдоль дерева.
4. повторяем шаги 2 и 3 для каждого элемента списка.

    Этап 2. Получение упорядоченного (отсортированного) списка на основании кучи.

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

    Алгоритм  преобразования кучи.

1. обменяем корень с последней вершиной «u», то есть с самой правой вершиной на самом высоком уровне. Зафиксируем положение полученной последней вершины. ( Под фиксацией положения вершины, мы подразумеваем, что зафиксированная вершина игнорируется при всех последующих манипуляциях дерева).
2. восстановим дерево до кучи, путем осаждения вниз нового корня «u» следующим образом: поменяем местами корень «u» с самым большим из двух его детей, затем переходит к поддереву, меняя каждый раз вершину «u» с самым большим из её детей. Если это поддерево имеет высоту 0, то переходим к шагу 3, иначе повторяем шаг 2 для этого поддерева.
3. повторяем шаги 1 и 2 пока все вершины не окажутся зафиксированными.

    Пример. Произвести сортировку по методу «кучи» списка 10, 7, 8, 5, 4, 9, 1, 3, 6,  2.

    Предположим, что куча на рисунке 8 получена из исходного не отсортированного списка.

    Корень  кучи – это максимальный элемент, который поэтому должен быть помещен  в конце списка. Поменяем этот корень местами с последней вершиной в куче. Зафиксируем положение последней вершины.

    Мы  должны восстановить кучу, помня о  том, что вершина 10 уже находится  в своей окончательной позиции  и её никуда не следует перемещать. Итак, чтобы восстановить кучу, надо корень 4 опустить вниз по дереву, последовательно обменивая число 4 с большим из его детей, то есть с 9. и так далее продолжая процесс, мы приходим к такому преобразованию дерева, при котором все его вершины находятся в своем окончательном положении.  

Представление алгебраических выражений с помощью двоичных деревьев 

       Пусть S представляет собой множество, на котором определены две двоичные операции Å и *. Без соглашения о порядке выполнения операций выражение типа x Å y * z могут быть прочитаны неоднозначно: или (x Å y) * z, или x Å (y * z).

       Такие выражения могут быть однозначно представлены на основе двоичных деревьев следующим образом. Выражение могут  быть определены рекурсивно, как Х a У, где a - символ двоичной операции, а Х и У являются элементами множества S или выражений, составленных из элементов множества S. Такое выражение может быть представлено как двоичное дерево  с корнем a, левым ребенком Х и правым ребенком У. Например, рис. 9. 

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Заключение 

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