1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 27
Текст из файла (страница 27)
Каждая операция ПРИНАДЛЕЖАТЬ(а, 5) выполняется последовательными просмотрами этого списка до тех пор, пока не найдется данный элемент а или не будут просмотрены все элементы списка. Выполнение всех операций из О заняло бы тогда время порядка иХ ~а~ как в худшем случае, так и в среднем. Основное преимущество этой схемы в том, что предварительная работа здесь занимает очень мало времени.
Другой путь — разместить элементы множества 5 в таблице расстановки размера йЩ, Операция ПРИНАДЛЕЖАТЬ(а, 5) выполняется поиском в списке й (а). Если можно найти хорошую функцию й, то выполнение о займет время ОИО~) в среднем и 0(и1а~) в худшем случае. Основная трудность здесь связана с нахождением функции расстановки, равномерно распределяющей элементы из 5 в таблице расстановки.
Если на 5 задан линейный порядок (, то третьим решением будет двоичный поиск. Элементы из 5 хранятся в массиве А. Этот массив упорядочивается так, чтобы было А11) ( А 121 (... ( А (и). Теперь, чтобы установить, принадлежит ли элемент а множеству 5, надо сравнить его в элементом Ь, который хранится в ячейке 1 (1+и)/2 ~. Если а=Ь, то остановиться и ответить "да".
В противном случае повторить эту процедуру на первой половине массива, если а(Ь, и на второй, если а~Ь. Повторно разбивая область поиска пополам, можно не более чем за( 1оя (и+1) ) сравнений либо найти а, либо установить, что его нет в 5. Рекурсивная процедура ПОИСК (а, /, 1), приведенная на рис. 4.3, ищет элемент а в ячейках /, /+1, /+2,...,! массива А. Для установления принадлежности а множеству 5 вызывается ПОИСК(а, 1, и).
Чтобы понять, почему эта процедура работает, представим массив А в виде двоичного дерева. Корень находится в ячейке ( (1+и)/2 ~, аеголевый н правый сыновья — в ячейках( (1+и)/4 1 и ( 3(1+и)/4 ) соответственно, и т. д. Эта интерпретация двоичного поиска станет яснее в следующем разделе. с стгиктгиы длнных для задач с множвстнлми ргоседнге ПОИСК(а, /', 1): И /) 1 1Ье ге1игп "неть е)ае И а=А [( (/+1)/2 )1 1Ьеп ге1нгп "да" е!ае И а < А 1 ( (/+ 1)/2 (1 1Ьеп ге1нгп ПОИСК(а, /, ( (/+1)/2 ) — 1) е!ае ге1нгп ПОИСК(а, ! (/+/)/2 ( +1, 1) Рис. 4.3.
Процедура двоичного поиска. Легко показать, что на розыск элемента в А ПОИСК тратит не более Г !ои (а+1) !сравнений, так как никакой путь в рассматриваемом деревенедлиннее! !ои(а+1) 1. Если все элементы как цели для поиска равновероятны, то можно также показать (упр. 4.4), что ПОИСК дает оптимальное среднее число сравнений (а именно, !п)1ой л), необходимое для выполнения операций ПРИНАДЛЕЖАТЬ в последовательности о '). 4.4. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА Рассмотрим следующую задачу. В множество Я вставляются и из него удаляются элементы.
Время от времени нам может понадобиться узнать, принадлежит ли данный элемент множеству 3 или, например, каков в данный момент наименьший элемент в 5. Мы считаем, что элементы добавляются в 5 из большого универсального множества, линейно упорядоченного отношением <. Эту задачу можно сформулировать в общем виде как выполнение последовательности, состоящей из операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ и М1Ы. Мы уже видели, что для выполнения последовательности операций ВСТАВИТЬ, УДАЛИТЬ и ПРИНАДЛЕЖАТЬ хорошей структурой данных может служить таблица расстановки. Но нельзя найти наименьший элемент, не просмотрев всю таблицу.
Структурой данных, пригодной для всех четырех операций, является дерево двоичного поиска. Определение. Деревом двоичного поиска для множества 3 называется помеченное двоичное дерево, каждый узел о которого помечен элементом 1(о) Ео так, что ') Разумеется, поскольку в расстановке участвуют ие только сравнения, то, возможно, она окажется лучше двоичного поиска; во многих случаях зто действительно так. 4.4, ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА Рнс. 4.4.
Дерево двоичного поиска. 1) 1(и) ( 1(о) для казцдого узла и из левого поддерева узла и, 2) 1(и) > 1(п) для каждого узла и из правого поддерева узла о, 3) для каждого элемента а Е В существует в точности один узел о, для которого 1(о) а. Заметим, что из условий 1 и 2 вытекает, что метки этого дерева расположены в соответствии с внутренним порядком. Кроме того, условие 3 следует яз условий 1 и 2. Пример 4.3.
Нз рис. 4 4 изображено возможное двоичное дерево для выделенных слов Алгола Ьед!и, е1зе, епд, Н, 1Ьеп. Здесь линейным порядком является лексикографический порядок. П Чтобы выяснить, принадлежит ли элемент а множеству 3, представленному деревом двоичного поиска, надо сравнить а с меткой корня. Если метка корня равна а, то очевидно, что а Е В. Если а меньше метки корня, то надо перейти к левому поддереву корня (если оно есть). Если а больше метки корня, то надо перейти к правому поддереву корня. Если а присутствует в дереве, его местоположение будет в конце концов обнаружено.
В противном случае процесс окончится, когда надо будет найти несуществующее левое или правое поддерево. Аигоритм 4.1. Просмотр дерева двоичного поиска Вход. Дерево Т двоичного поиска для множества В и элемент а, Выход. "Да", если а ЕВ, и "нет" в противном случае.
Метод. Если дерево Т пусто'), выдать "нет." В противном слу') Хотя наше определение понятия дерева требует, чтобы дерево содержало хотя бы один узел, а именно корень, во многих алгоритмах мы будем трактовать пустое дерево (дерево без узлов) как двоичное. ззу гл, с стргктиры данных для задач с множвствдми ргоседпге ПОИСК(а, о): 1.
И а=1(о) !Ьеп ге!пгп 'да" е(зе 2. И а<1(о) !(теп 3. И о имеет левого сына го !Ьеп ге!пгп ПОИСК(а, го) 4. е1зе ге!цгп "нет" е)зе 5. И о имеет правого сына го !Ьеп ге!пгп ПОИСК(а, го) 6. е!зе ге!ягп "нет" Рис. 4Л. Просмотр дерева двоичиого поиска. чае пусть г — корень дерева Т, Тогда алгоритм состоит из единственного вызова ПОИСК (а, г) рекурсивной процедуры ПОИСК, приведенной на рис. 4,5. (3 Очевидно, что алгоритм 4.1 достаточен для выполнения операции ПРИНАДЛЕЖАТЬ(а, Я). Более того, его легко модифицировать так, чтобы он выполнял операцию ВСТАВИТЬ(а, Я). Если дерево пусто, строится корень с меткой а.
Если дерево непусто, а элемент, который надлежит вставить, не обнаружен в дереве, то процедуре ПОИСК ие удается найти сына в строке 3 или 5. Вместо того чтобы выдать "нети в строке 4 или 6 соответственно, для этого элемента строится новый узел там, где должен был быть отсутствующий сын, Деревья двоичного поиска также удобны для выполнения операций М!Ы и УДАЛИТЬ. Для нахождения наименьшего элемента в дереве двоичного поиска Т просматривается путь о„о„..., о, где о,— кореньдерева Т, о~ — левый сын узла о; и 1(1<р, и у узла ор нет левого сына. Метка в узле ор является наименьшим элементом в Т. В некоторых задачах может оказаться удобным иметь указатель иа о, чтобы обеспечить доступ к наименьшему элементу за постоянное время.
Реализовать операцию УДАЛИТЬ(а, 5) немного труднее. Допустим, что элемент а, подлежащий удалению, расположен в узле о. Возможны три случая: 1) о — лист; в этом случае о удаляется из дерева; 2) у о в точности один сын; в этом случае делаем отца узла о отцом его сына, тем самым удаляя о из дерева (если о — корень, то его сына делаем новым корнем); 3) у о два сына; в этом случае находим в левом поддереве узла о наибольший элемент Ь, рекурсивно удаляем из этого поддерева узел, содержащий Ь, и метим узел о элементом Ь. (Заметим, что среди элементов, меньших а, Ь будет наибольшим элементом всего дерева.) ЬЬ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА Рнс.
4.6. Дерево двоичного поиска после выполнения операции УДАЛИТЬ. В качестве упражнения предлагаем написать программу на Упрощенном Алголе для Операции УДАЛИТЬ. Заметим, что одно выполнение любой из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ и М1Н можно осуществить за время 0 (и). Пример 4.4. Предположим, что надо удалить слово И из дерева двоичного поиска, изображенного на рис. 4.4.
Слово И расположено в корне, у которого два сына. Наибольшее слово, меньшее И (лексикографически), расположенное в левом поддереве корня,— зто епд. Удаляем из дерева узел с меткой епд и заменяем И на епд в корне. Затем, поскольку епа' имеет одного сына (Ьен(п), делаем Ьео)п сыном корня. Полученное дерево показано на рис.
4.6. П Подсчитаем временную сложность последовательности из и операций ВСТАВИТЬ, когда рассматриваемое множество представлено деревом двоичного поиска. Время, требуемое, чтобы в дерево двоичного поиска вставить элемент а, Ограничено по порядку числом сравнений, производимых между а и элементами, уже находящимися в дереве. Поэтому время можно измерять числом производимых сравнений. В худшем случае добавление к дереву и элементов может потребовать квадратичного времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
