Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 68
Текст из файла (страница 68)
Йеу 4 ге1игп Ткее-Яедксн(х. »еу», Й) 5 е1ае гегнгп ТКЕЕ-БЕАКСН(х. гсдЫ, й) Процедура поиска начинается с корня дерева и проходит вниз по простому пути по дереву, как показано на рис. 32.2. Для каждого встреченного на пути вниз узла х его ключ х. Йеу сравнивается с переданным в качестве параметра ключом й. Если ключи одинаковы, поиск завершается. Если Е меньше х. йеу, поиск продолжается в левом поддереве х, так как из свойства бинарного дерева поиска понятно, что искомый ключ не может находиться в правом поддереве. Аналогично, если Е больше х.
пеу, поиск продолжается в правом поддереве х. Узлы, которые мы посещаем при рекурсивном поиске, образуют простой нисходящий путь от корня дерева, так что время работы процедуры Ткее-Бедксн равно 0(А), где Л— высота дерева. Ту же процедуру можно записать итеративно, "развернув" оконечную рекурсию в цикл ибгйе. На большинстве компьютеров такая версия оказывается более зффектнвной. 3ТЕКАТ1ЧЕ-ТКЕЕ-оЕАКСН (х, /с) 1 пбгйе х ,-Ь нп. и й ф х.лисеу 2 гт" й ( х.йеу 3 х = х.»еу» 4 е2ае х = х.г»уб» 5 гетпгп х Часть!И.
Свруктури данны1 324 Минимум и максимум Элемент с минимальным значением ключа всегда можно найти, следуя по дочерним указателям 1еуг от корневого узла до тех пор, пока не встретится значение 14п., как показано на рис. 12.2. Приведенная ниже процедура возвращает указатель на минимальный элемент поддерева с корнем в данном узле х, который предполагается не равным 141ь. Ткее-М1 ~1м11м(х) 1 ийИе х. 1е11 ф 1чп. 2 х = х.1егг 3 ге1вги х Свойство бинарного дерева поиска гарантирует корректность процедуры ТкееМ1 пмцм.
Если у узла х нет левого поддерева, то, поскольку все ключи в правом поддереве х не меньше ключа х.йеу, минимальный ключ поддерева с корнем в узле х находится в узле х.йеу. Если же у узла х есть левое поддерево, то, поскольку в правом поддереве не может быть узла с ключом, меньшим х.йеу, а все ключи а узлах левого поддерева не превышают х. Йеу, узел с минимальным значением ключа в поддереве с корнем х находится в поддереве, корнем которого является узел х. 1е~1. Псевдокод процедуры ТКЕЕ-МАХ1МиМ симметричен. ТКЕЕ-МАХ1М15М (х) 1 згййе х.пдЬ1 ~ Н1Е 2 х = х.тгдЬ1 3 гегцгп х Обе эти процедуры находят минимальный (максимальный) элемент дерева за время 0(Ь), где Ь вЂ” высота дерева, поскольку, как и в процедуре ТкЕЕ-ЯЕЬКсн, последовательность проверяемых узлов образует простой нисходящий путь от корня дерева.
Предшествующий и последующий элементы Иногда для заданного узла в бинарном дереве поиска требуется определить, какой узел следует за ним в отсортированной последовательности, определяемой порядком центрированного обхода бинарного дерева, и какой узел предшествует данному. Если все ключи различны, последующим по отношению к узлу х является узел с наименьшим ключом, большим х. /сеу. Структура бинарного дерева поиска позволяет найти этот узел, даже не выполняя сравнение ключей. Приведенная далее процедура возвращает узел, следующий за узлом х в бинарном дереве поиска (если таковой существует), и 1чп., если х обладает наибольшим ключом в бинарном дереве. 525 раааа!д Бинарные деревьв ноиска ТКЕЕ-80ССЕББОК(х) 1 !Тх.пдЬ! ф нп. 2 гетпгп ткее-мп пмпм(х.
~дь!) 3 у= х.р 4 нй!1е у ф мп. и х == у. г!дЫ 5 х=у 6 у =ур 7 ге!вгп у Код процедуры ТКЕе-80ССЕББОК разбивается на две части. Если правое поддерево узла х непустое, то следующий за х элемент является крайним слева узлом в правом поддереве х, который выявляется в строке 2 вызовом процедуры Ткее-Мпч!мпм(х, г!дЫ). Например, на рис. 12.2 следующим за узлом с ключом 15 является узел с ключом 17. С другой стороны, как требуется показать в упр.
!2.2.6, если правое поддерево узлах пустое и у х имеется следующий за ним элемент у, то у является наименьшим предком х, левый наследник которого также является предком х. На рис. !2.2 следующим за узлом с ключом 13 является узел с юпочом 15. Для того чтобы найти у, мы просто поднимаемся вверх по дереву от х до тех пор, пока не встретим узел„который является левым дочерним узлом своего родителя. Это действие выполняется в строках 3-7 процедуры ТКЕЕ-ЯОССЕББОК. Время работы алгоритма ТКЕЕ-ЯПССЕББОК в дереве высотой Ь составляет 0(Ь), поскольку мы либо движемся по простому пути вниз от исходного узла, либо по простому пути вверх. Процедура поиска предшествующего узла в дереве Ткее-РкепесеББОк симметрична процедуре Ткее-Впссевзок и также имеет время работы 0(Ь).
Даже если в дереве имеются узлы с одинаковыми ключами, мы можем просто определить последующий и предшествующий узлы как такие, которые возвращаются процедурами ТКЕЕ-ЯОССЕББОК(х) и ТКЕЕ-РКЕОЕСЕББОК(х) соответственно. Таким образом, мы доказали следующую теорему. Теорема П.2 Операции ВЕЛКСП, М!и!МПМ, МЛХ!МОМ, 80ССЕББОК и РКЕОЕСЕББОК над динамическим множеством могут быть реализованы таким образом, что нх время выполнения равно 0(Ь) в бинарном дереве поиска высотой Ь. Упражнения 72.г 7 Предположим, что имеется ряд чисел от 1 до 1000, организованных в виде бинарного дерева поиска, и мы выполняем поиск числа 363. Какая нз следующих последовательностей не может быть последовательностью проверяемых узлов? а 2, 252, 401, 398, 330„ 344, 397, 363. б. 924, 220, 911, 244, 898, 258, 362, 363.
32б Часть П1. Структуры данньи в. 925, 202, 911, 240, 912, 245, 363. г. 2, 399, 387, 219, 266, 382, 381, 278, 363. д. 935, 278, 347, 621, 299, 392, 358, 363. 12.2.2 Разработайте рекурсивные версии процедур Ткнн-Мнимом и Ткне-Млх1мим. 12.2.3 Разработайте процедуру Тквн-Ркнпнснззок. 12.2.4 Разбираясь с бинарными деревьями поиска, студент решил, что обнаружил их новое замечательное свойство. Предположим, что поиск ключа )г в бинарном дереве поиска завершается в листе. Рассмотрим три множества: множество ключей слева от пути поиска А, множество ключей на пути поиска В и множество ключей справа от пути поиска С. Студент считает, что любые три ключа о Е А, 6 е В и с Е С должны удовлетворять неравенству а < 6 < с.
Приведите наименьший возможный контрпример, опровергающий предположение студента. 12.2.5 Покажите, что если узел в бинарном дереве поиска имеет два дочерних узла, то последующий за ним узел не имеет левого дочернего узла, а предшествующий ему — правого. 12.2. б Рассмотрим бинарное дерево поиска Т, все ключи которого различны.
Покажите, что если правое поддерево узлах в бинарном дереве поиска Т пустое и ух есть следующий за ним элемент у, то у является самым нижним предком х, левый дочерний узел которого также является предком х. (Вспомните, что каждый узел является собственным предком.) 12.2. 7 Альтернативный центрированный обход бинарного дерева поиска с и узлами можно осуществить путем поиска минимального элемента дерева с помощью процедуры Ткее-М1м1мпм с последующим и — 1 вызовом процедуры ТнннБисснззок. Докажите, что время работы такого алгоритма равно ку(п).
12.2. 8 Докажите, что какой бы узел ни был взят в качестве исходного в бинарном дереве поиска высотой )ь, для )с последовательных вызовов процедуры Тннн-Бисснззок потребуется время 0()г + )з). 12.2.9 Пусть Т представляет собой бинарное дерево поиска с различными ключами„ х — лист этого дерева, а у — его родительский узел. Покажите, что у. Йеу либо является наименьшим ключом в дереве Т, превышающим ключ х.
лисеу, либо наибольшим ключом в Т, меньшим ключа х. Йеу. Гаева!2 Бинарные деревья наивна 12.3. Вставка н удаление Операции вставки и удаления приводят к внесению изменений в динамическое множество, представленное бинарным деревом поиска. Структура данных должна быть изменена таким образом, чтобы отражать эти изменения, но при этом сохранить свойство бинарных деревьев поиска.
Как мы увидим в этом разделе, вставка нового элемента в бинарное дерево поиска выполняется относительно просто, однаю с удалением придется повозиться. Вставка Для вставки нового значения с в бинарное дерево поиска Т мы воспользуемся процедурой Ткее-1мзект. Процедура получает в качестве параметра узел х, атрибуты которого х. Йеу = о, х. 1е/! = мп. и х.
пд!ь! = мп.. Процедура таким образом изменяет Т и некоторые поля х, что х оказывается вставленным в корректную позицию дерева. Ткее-1мзект(Т, з) ! у =мп. 2 х = Т.гоо! 3 нЫехфмп. 4 у=х 5 1Гз.йеу (х.йеу 6 х = х. 1е/! 7 еЬе х = х.езд!ь! 8 ар=у 9 Ыу==мп. !О Т.гоо! = з // Дерево Т было пустым !1 е!зеИ г.lсеу ( у.кеу 12 у.!е/! = х !3 еЬе у.АМ = з На рис. 12.3 показано, как работает процедура Ткнв-1мзнкт. Подобно процедурам Тквк-ЯкАксн и 1тккАт!УО-Тккн-Яклксн, процедура Тккн-1мзккт начинает работу с корневого узла дерева и проходит по простому нисходящему пути. Указатель х отмечает путь, проходимый в поисках мп., который должен быть заменен входным элементом з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
