Выберем для замены самый правый узел левого поддерева.
Определим следующее:
D - удаляемый узел;
Р - родитель удаляемого узла;
R - заменяющий узел;
PR - родитель узла R.
Перейти к левому поддереву узла D, потому что заменяющий узел R меньше, чем удаляемый узел D. Заменяющий узел R является максимальным узлом левого поддерева узла D. Спускаемся по правому поддереву и ищем заменяющий узел R. Во время спуска следим за предшествующим узлом PR. При этом возможны два случая:2.1. Правое поддерево пусто. Заменяющий узел R является левым сыном удаляемого узла. PR соответственно указывает на удаляемый узел D. Тогда выполняем следующие действия:
2.1.1. Присоединяем правое поддерево узла D в качестве правого поддерева к узлу R;
2.1.2. Родителя P удаляемого узла присоединяем к R.
2.2. Правое поддерево не пусто. Тогда заменяющий узел будет или листовым узлом или узлом, имеющим только левое поддерево. В любом случае выполняем следующие действия:
2.2.1. Отсоединить узел R от дерева.
2.2.2. Потомков узла R присоединить к его родительскому узлу PR (Левое поддерево R присоединяется в качестве правого поддерева к PR).
2.2.3. Удаляемый узел D заменяется узлом R: наследники узла D присоединяются в качестве наследников к узлу R, узел R присоединяется к родительскому узлу Р.
Лекция №10
Тема: Бинарные деревья, представляемые массивами. Турнирная сортировка. Пирамиды (heap - tree)
Цель: Знать алгоритмы сортировки.
Если данные бинарного дерева хранятся в элементах массива, то к данным может использоваться прямой доступ. Нулевой элемент массива – это корень дерева. Для каждого узла A[i] в n-элементном массиве индекс его наследников вычисляется по следующим формулам:
Индекс левого наследника равен 2*i+1.
Индекс правого наследника равен 2*i+2.
Индекс родителя можно вычислить по следующей формуле:
Индекс родителя равен (i-1)/2.
Представление дерева с использованием массивов удобно использовать для законченного бинарного дерева. Но при хранении дерева с небольшой плотностью в массиве имеются неиспользуемые элементы, что вызывает некоторые проблемы при работе с массивом.
Например:
Законченное бинарное дерево: int A[]={5, 1, 3, 9, 6, 2, 4, 7, 0, 8}; |
Бинарное дерево с меньшей плотностью: int A[]={5, 1, 3, 9, 6, 4, #, 7, #, #, #, 2}; |
Турнирная сортировка
Бинарные деревья находят применение в качестве деревьев принятия решений. Например, при представлении спортивного турнира, где каждый внутренний узел соответствует победителю встречи между двумя игроками.
Турнирное дерево может использоваться для сортировки массива из n элементов.
Рассмотрим алгоритм турнирной сортировки на следующем примере:
Пусть имеется массив из 8-ми элементов A[8]={35, 25, 50, 20, 15, 45, 10, 40}. Необходимо его отсортировать по возрастанию.
1. Элементы массива запоминаются в бинарном дереве на уровне k, где ; n – это количество элементов массива.
В данном случае элементы массива А запоминаются на уровне 3 ().
2. В родительские узлы помещаются наименьшие значения в парах. В результате последнего сравнения наименьший элемент массива попадает в корень дерева на уровне 0.
3. Наименьший элемент удаляется со своего старого места на дереве и копируется во вспомогательный массив.
Так как один элемент был удален, то п.2 выполняется заново, но уже без удаленного элемента.
4. Аналогичные действия выполняются с числом 15:
5. Процесс продолжается до тех пор, пока все листья не будут удалены. Последний (наибольший) узел играет серию матчей, в которых побеждает всех по умолчанию:
Вычислительная эффективность
Эффективность турнирной сортировки составляет.
В массиве, содержащем n = 2 k элементов, для выявления наименьшего элемента требуется n-1 сравнений.
Общее число матчей равно
.
Дерево обновляется, и оставшиеся n-1 элементов обрабатываются посредством k-1 сравнений вдоль пути, проходящего через родительские узлы.
Общее число сравнений равно
.
Пирамиды (heap - tree)
Пирамида - законченное бинарное дерево, имеющее упорядочение узлов по уровням.
Различают максимальные пирамиды и минимальные.
В максимальной пирамиде родительский узел больше или равен каждому из своих сыновей. Корень содержит наибольший элемент.
В минимальной пирамиде родительский узел меньше или равен каждому из своих сыновей. Корень содержит наименьший элемент.
Пирамида используется в тех приложениях, где клиенту требуется прямой доступ к минимальному элементу.
Пирамида является списком, который хранит данные в виде бинарного дерева.
Все алгоритмы обработки пирамид сами должны обновлять дерево и поддерживать пирамидальное упорядочение.
Преобразование массива в пирамиду
Индекс последнего элемента пирамиды равен n-1.
Индекс его родителя равен (n-2)/2, и он определяет последний нелистовой узел пирамиды. Этот индекс является начальным для преобразования массива.
Рассмотрим целочисленный массив
int A[10] = {9, 12, 17, 30, 50, Индексы листьев: 5, 6, ..., 9. Индексы родительских узлов: 4, 3, ..., 0. |
Родитель А[4]=50, он больше своего сына А[9]=19 и поэтому должен поменяться с ним местами. |
Родитель А[3]=30, он больше своего сына А[8]=4 и поэтому должен поменяться с ним местами (если меньших сына два, то меняется местами с наименьшим сыном). |
На уровне 2 родитель А[2]=17 уже удовлетворяет условию пирамидальности, поэтому перестановок не производится. Родитель А[1]=12 больше своего сына А[3]=4 и должен поменяться с ним местами. |
Процесс прекращается в корневом узле. Родитель А[0]=9 должен поменяться местами со своим сыном А[1]. Результирующее дерево является пирамидой. |
Включение элемента в пирамиду
1. Новый элемент добавляется в конец списка. |
2. Если новый элемент имеет значение, меньшее, чем у его родителя, узлы меняются местами. |
3. Новый родитель рассматривается как сын, и проверяется условие пирамидальности для более старшего родителя. |
4. Процесс сканирует путь предков и завершается, встретив родителя, меньше чем новый элемент, или достигнув корневого узла. |
Удаление из пирамиды
Данные удаляются всегда из корня дерева.
1. Удалить корневой узел и заменить его последним узлом. |
2. Если новый корневой узел больше любого своего сына, то необходимо его поменять местами с наименьшим сыном. |
3. Движение по пути меньших сыновей продолжается до тех пор, пока элемент не займет правильную позицию в качестве родителя или пока не будет достигнут конец списка. |
Пирамидальная сортировка
1. Преобразовать массив в пирамиду.
2. Последовательное исключение A[0] и включение его в A[n-1], A[n-2], ..., A[1]. (Этот алгоритм основан на том, что после исключения элемента из пирамиды элемент, бывший до этого хвостовым, замещает корневой узел, а его место освобождается.
В процессе пирамидальной сортировки очередные наименьшие элементы удаляются и последовательно запоминаются в хвостовой части массива. Таким образом производится сортировка по убыванию.
Пример:
Дан массив: int A[]={50, 20, 75, 35, 25}; Исходная пирамида | |
Удалить 20 и запомнить в A[4] | Удалить 25 и запомнить в A[3] |
Удалить 35 и запомнить в A[2] | Удалить 50 и запомнить в A[1] |
Поскольку остался только корень, то массив отсортирован: А = 75, 50, 35, 25, 20.
Вычислительная эффективность
Массив, содержащий n элементов соответствует законченному бинарному дереву глубиной.
Преобразование массива в пирамиду требует n/2 операций, каждая из которых требует не более k сравнений.
Вторая фаза сортировки требует выполнения n-1 операции, которая в худшем случае требует k сравнений.
Худший случай сложности пирамидальной сортировки
.
Сложность алгоритма имеет порядок.
Пирамидальная сортировка не требует дополнительной памяти (для сравнения: при турнирной сортировке требуется создание дополнительного массива).
Лекция №11
Тема: Сбалансированные деревья.
Цель: Ввести основные определения, знать способы включения и удаления в сбалансированные деревья.
Основные определения
Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале дерево является разумно сбалансированным и имеет высоту порядка. Однако при некоторых данных дерево может быть вырожденным. Тогда его высота будет O(n), и доступ к данным существенно замедлится.
Дерево является сбалансированным тогда, и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 (не путать с идеально сбалансированными деревьями, когда для каждого узла дерева количество узлов в левом и правом поддеревьях отличается не более чем на 1).
Сбалансированные деревья еще называют AVL-деревьями (по фамилиям изобретателей: Адельсон-Вельский, Ландис).
Бинарное дерево поиска | AVL-дерево |
Узлы AVL-дерева
AVL-деревья имеют представление, похожее на бинарные деревья поиска. Все операции идентичны, за исключением операций вставки и удаления из дерева.
Для сохранения информации об соотношении высот левого и правого поддеревьев в определение типа узла включается поле - показатель сбалансированности, которое содержит разность высот правого и левого поддеревьев:
struct AVLTREE{
int dann;
int balance;
TREE *pleft;
TREE *pright; };
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
