Лекции по информатике (984119), страница 9
Текст из файла (страница 9)
Если подать этой программе вьппеописапнуго последовательностс из 21 числа, то мы получим двоичное делрево поиска, топология и ординальность которого будут совсем другими: Дерево поиска может быть использовано для упорядочивания данных. Для этого надо разместить эти данные в дереве поиска, а потом составить в результате его обхода упорядоченнукл после;довательность.
Но для решения этой задачи обычное дерево поиска не подходит: оно не допускает вхож Еения равнозначных элементов. Поэтому всякий новый элемент теперь должен быть включен в дерево. Для этого случай х — р".1ееу необходимо рассматривать вместе с одним из других. Если его объединить с х > р .1ееу, то порядок следования элементов с одинаковыми ключами совпадет с хронологией их поступления в дерево.
Возможность сочетания поиска и упорядочивания растущего множества данных,предоставляемая деревом поиска с включениями, дабт новое качество по сравнению 287 с хранением данных как в списках, так и в массивах. Наттример, этим способом можно эс[эфективно решить задачу составления табтлтщы перекрестных ссылок слов текста, [54[. 5.11.2 Исключение из деревьев Перейдем теперь к решению обратной задачи задачи исключения элементов из упорядоченного дерева поиска: необходихкэ найти и исключить из дерева элемент с ключом т,. Если исклточаемая вершина в дереве есть, то опа может быть либо листом, либо внутренней вершиной с одним или с двумя потомками.
Последний случай представляет определенную трудность в реализации. После изъятия элемента с двумя потомками одна ссылка на него оказывается на разветвлении к потомкам. По построению дерева поиска значение удаляемогс) узла таково, что В его лс.вом подле)тепе находятся меньшис.; элс;менты, а В правом большие.
При этом самый правый элемент левого поддерева больше любого другого элемента этого поддерева и одновременно меныпе любого элемента соседнего с левым правого поддерева. И наоборот, самый левый элемент правого поддерева меньше любого из элементов этого полдерева и больше любого элемента из соседнего левого поддерева. Таким образом, лнэбой из этих элементов может быть помещен вместо удаляемой вершины, и порядок в дерс,ве поиска сохранится.
Итак, удаляемый элемент заменяется либо на самый правый элемент его левого полдерева,, либо на самый левый элемент сто правого поддерева, причем эти элементы не могут иметь больше одного потомка, как максимальный и минимальный элементы соответствующих поддеревьев. Все эти случаи предусматривает рекурсивная пропедура де1е1е: ргосес1пге с1е1е1е(х: денег; айаг р: чср); айаг ц: ~чр; ргосес1пге с1сэ1 (атак г: ттр); Ьепш ~т Обработка, случая двут; потпамков утс)алле»той вериисны, — поиск узла без правого ттоддерева )' 11' 'с".г <> ш1 ФЬеп ~т Сущестпсэтутетп элемент больтие данного )' с1е1(Ь".г) 1' Пуэодолглсаем поиск релевантной вершины в отттологичстсктл градиентнсэм направлении эт е1ве Ьеиш ) Нуэюньи) элемент найдспи все полезньсе данные релеванттттсого элемента копируются в узел.
«удаляемого» элемента, после чего уда.ляется тлпп элеметстти отпкуда были взяты г)аинлле эт с) .1сеу;: 1 .1сеу; с) .соппФ: 1 .сспм; с1:-- 1; 1' Глобальной ссьслке присваивается локальный указатель релевантного узла э) $:-- с".1 1' Подаем левого поддерева релевантного узла, если оно есть, на место перемещенного элемента с ие.лью устранения. разрыва в дереве поиска э~ епс1 епс1; 1'с)е13 Ь ерш 1сЫе1еэс 11' р <ть ш1 ФЬеп 1' Поиск удаляемого элемента продолэссаетпся эт К х < р 1сс)у ФЬеп с1е1ес6 (х, р . 1) е1яе Ы х > р 1сеу ФЬеп с1е!сге(х, р".г) е1яе Ьеи1п ?' Искл)оне)сие р" ? Ч: Р' Ы с1 .г г)11 ФЬеп ? ??равого поддерева нет„вместо удаленного узла сгпасим корень левого ? р : с1 .1 е1яе М с1 .1 — п11 ФЬеп ? Левого поддерева нет, вместо удаленного узла ставим корень правого ?' рь с1 .г е1яе ? Удаляемая вершина имеет двух потомков.
??оиск самого правого элемента левого поддерева — кандидата но, замещение удаляемой вершины 3 с1е11с1 .1); с11ярояе(с1) ? Удаление самого элемента или кандидата на его замещение, найденного среди потомков ? епс1; епс1; ? деЫе Вспомогательная рекурсивная пропсдура с?е! осу)цествляет рекурсивный спуск вдоль правой ветви левого поддерева элемс'нта с? )', исклк)чаемого из дерс'ва, и заменяет его клк)ч и счетчик на соответствуюгцие значения из самой правой компоненты ? 1 левого поддерева, после чсто динамический объект с? ~ можно уничтожить деструктором с11ярояе ()можно было бы с тем же успехом делать рекурсивный спуск по самой левой ветви правого поддерева удаляемого элемента).
Проиллюстрируем процесс удаления нескольких элементов из дерева поиска. При этом возникают все рассмотренные слу )аи. Проанализируем сложностные оценки алгоритма поиска по дереву с включениями. Во-первых ясно, что получаемое дерево не будет идеально сбалансированным и оценка для числа сравнений 1ок2 и может ухудшиться ~54~. ХЭ;евший случай соответствует вырожденному несбалансированному дереву, сформированному строго возрастающей 1или строго убывающей) последователыюстью элементов, когда каждый ключ присоединяется непосредственно справа 1или слева) от его предшественника,, образуя линейный список с известным нам временем поиска 0(111), 11о этот случай маловероятен: оценка в книге 11.
Вирта [54~ показывает, что среднее время поиска отличается от оптимального на 39%. Таков средний выигрыш от всевозможных усовершенствований структуры дерева гю мере нйкОНЛ1'ния статистики запросОВ на ИОиск. Они ОпраВданы, кОгда числО ВС111пин В дереВе достаточно велико или когда доступ к дереву щ1свалируст над включением элементов. 5.11.3 Сбалансированные деревья Поскольку каждое включение элемента приводит к разбалансировке дерева поиска, а значит, и к ухудшению времени доступа, то возникает мысль об оперативной балансировке дерева после операций вставки. Для упрощения операции восстановления дерева после случайного включения отечественными учеными Г. М.
Адельсоном-Вельским и Е. М. Ландисом было предложено ослабить строгую сбалансированность дерева. Сбалансированным деревом ими было названо такое дерево, высоты поддеревьев каждой из вершин которого отличаются не более, чем на единипу. В честь авторов такие деревья названы ЛИ-1Эерсвьям1ь Идеально сбалансированные деревья также являются ЛЧ1-деревьями.
Это определение щ>иводит к простой процедурс ребалансировки дерева, причем средняя длина пути поиска практически совпадает с его длиной в идеально сбалансированном дереве. 290 В сбалансированных деревьях за время., пропорциональное 0(1о8з и), даже в худшем случае, можно вьшолнить слсл,ующие операции: ° найти вергпину с данным ключом; ° вклк>чить новую вершину с заданным клньчом; ° исключить вершину с указанным ключом.
По теореме Адельсона-Вельского — Ландиса сбалансированное дерево никогда пе будет по высоте превыпзать идеалыю сбалансированное более чем на 45%, независимо от количества вершин. Высота сбалансировашюго дерева с и вершинами 6~(п) находится в пределах 1оД,(п $- 1) ( Ьь(и) < 1.4404 1о8з(п+ 2) — 0.328 Минимум достигается, если дерево идеально сбалансировано, т.
е, при в = 2 — 1. Инь тересно узнать и о максимуме для 6~(п), т, е, о самом плохо сбалансированном дереве максимальной высоты для и вершин. Для построения такого дерева, может быть применена следующая идея: будем строить сбалансированные деревья с минимальным числом вершин ди фиксированной высоты Ь. Дерево с минимальным числом вершин Ть высоты 6 построим ипдукцией по высоте. Тд пустое дерево, а Тд дерево с одной единственной вершиной (база индукции). Для построения Та для 6 ) 1 мы будем брать корень и два поддерева опять же с минимальным числом вершин. Следовательно, зти деревья также относятся к классу Т-деревьев.
Одно поддерево, очевидно, должно быть высотой 6 — 1, а другому позволяется иметь высоту на единицу меныпе, т. е. 6 — 2. Ниже представлены деревья высотой 2, 3 и 4. Т' Тз Поскольку принцип их построения очень напоминает определение чисел Фибоначчи, то мы будем называть такие деревья деревьями Фибоначчи. Их определение более, чем стандартно: 1. Пустое дерево есть дерево Фибоначчи высоты О. 2.
Единственная вершина есть дерево Фибопаччи высоты 1. 3. Если Та ~ и 7),, ~ — деревья Фибоначчи высотой 6 — 1 и 6 — 2, то 7~ = (7ь и х, 7'~ з) также дерево Фибона гни высотой 6. 4. Никакие другие деревья деревьями Фибоначчи нс являются. Число вершин в Ть определяется из такого простого рекуррентного отношения: А~о = 0 % = 1 -~ь = Аь-~ 1-1+ Аь-г Число Я; как раз и будет числом вершин для самых худших случаев (верхний предел 6). 5.11.3.1 Включение в сбалансированное дерево Проанализируем операцию включения в сбалансированное дерево новой вершины. Мы надеемся, что цена этой операции не ухудшит замечательные свойства АУ1.-деревьев. Если наше дерево состоит из корня 1 и левого и правого поддеревьев Ь и Л соответственно, то либо оно идеально сбалансировано и вставка новой вершины углубит одно из поддеревьев на единицу.
Либо вставляемая вершина попадет в более низкое поддерево и улучшит сбалансированность. Е1аконец, при попадании нового узла в более высокое поддерево, АУЬ- сбалансированность дерева нарушится и возникнет необходимость балансировки дерева. Рассмотрим дерево Вершины с ключами 9 и 11 можно вставить, не нарушая сбалансированности дерева. Если бы в дерево поиска сначала, пришло бы число 10, то дерево стало бы односторонним.
Дерево с корнем 8 будет лишь лучше сбалансированным. Включение вершин 1, 3, 5, 7 разбалансируст дерево. С точностью до симметрии существует всего лишь две различные возможности несбалансированности, возникгпей из-за включения. Они отличаются местом возникновения перевеса: с края или в середине дерева. Первый случай — вставка вершины 1 или 3, второй --- 5 или 7: Случай 1 Случай 2 С.луча,й 2 Случай 1 Алгоритм включения и балансировки существенно использует информацию о сбалансированности дерева.
Проверять балансировку по дереву. всякий раз при вклк>чении в него слишком дорого: 0(Х), где М - количество вершин дерева. На другом полюсе - хранение в каждой вершине показателя сбалансированности разности высоты правого и левого поддерева, принимающего значения в диапазоне ~ — 1„.11~ — в эти же два бита можно упаковать и три перечислимых балансировочностных значения. 293 Процесс балансировки заключается в вертикальном «подтягивании» одного или двух поддеревьев путем манипуляций ссылками на потомков в вышестсящих вершинах, релевантных для восстановления баланса. Среди этих манипуляций такие: подчинение корня левому поддереву и переподчинение внука, выравнивающее баланс, и подьем на два уровня внутреннего полдерева, включение в которое привело к несбалансированности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
