Дискретная математика (998286), страница 45
Текст из файла (страница 45)
Рис. 9.11 справа). В этом случае выполняются два преобразования дерева. Сначала информация в узле р заменяется на информацию узла с, Поскольку узел с находится в правом поддереве узла р и в левом поддереве узла и, имеем Рл < с.т < и.т. Таким образом, после этого преобразования условие дерева сортировки выполняется. Далее правое поддерево 4 узла с подцепляется слева к узлу тл, а сам узел с удаляется. Поскольку поддерево 4 входило в левое поддерево узла тн, условие дерева сортировки также сохраняется. П ЗАМЕЧАНИЕ В книге [8[, нз которой заимствован данный алгоритм, показано, что хотя алгоритм «вьн глядит несимметричным» (правые н левые связи обрабатываются но-разному), на самом деле в среднем характеристики дерева сортировки не искажаются.
9.4.7. Вспомогательные алгоритмы для дерева сортировки Алгоритмы трех предыдуптих разделов используют вспомогательные функции описанные здесь. 252 Глава 9. Деревья 1?оиск узла — функция г)пд. ?3ход: дерево сортировки Т, заданное указателем на корень; ключ а. 13ыход: р — указатель на найденный удел или пИ, если в дереве нет такого ключа; д— указатель,на отца узла р; в — способ подцеплеиия узла д к узлу р (в = — 1, если р слева от 9; в = +1, если р справа от д; в = О, если р — корень).
р:=Т;9:=пй;в:=О ( инициализация ) »гЬИе р ~ пй Йо Н рл = а Сйеп гегпгп р,д,в епц Н 9: =р ( сохранение значения р ) ?т а < рл т?геп Р: = Р.1; в: = -1 ( поиск слева ) е?зе Р: = р.г; з; =+1 ( поиск справа ) спи!? спи «пйе ОТСТ)ГПЛЕНИЕ В этой простой функции стоит обратить внимание на использ ва ие у рый от»леживает значение указателя р вс запаздыванием», то ееть указатель д »помнит» предыдущее значение указателя р. Такой прием полезен при обходе одноиаправлюшых структур данных, в которых невозможно вернуться назад.
2. Удаление узла — процедура?)е)е$е. Вход: р1 — указатель на удаляемый узел; р2 — указатель на подцепляющнй узел; РЗ— указатель на подцепляемый узел; в — способ подцепления. Выход: преобразованное дерево. К в = — 1 йеп р22: = РЗ ( подцепляем слева ) епИ ц 11 в = +1 Г?»еп р2ж:=РЗ ( подцепляем справа ) епц 11 о1эрозе(р1) ( удаляем узел ) 3. Создание нового узла — конструктор 1чеэг?Чог?е.
Вход: ключ а. Выход: указатель р на созданный узел. пеж(р); рл': = а; рд: = щ1; р.г: = пИ геьагп р 9.4.8. Сравнение представлений ассоциативной памяти Пусть и — количество элементов в ассоциативной памяти. Тогда сложность-операций для различных представлений ограничена сверху следующим образом. 253 9.4. Де ья сортировки Дерево сортировки Неупорядоченный Упорядоченный массив массив Эффективность операций с деревом сортировки ограничена сверху высотой де- рева. ЗАМЕЧАНИЕ Дерево сортировки может расти неравномерно. Например, если при загрузке дерева ис- ходные данные уже упорядочены, то полученное дерево будет право- или леволинейным и булет даже менее аффективным, чем неупорядоченный массив.
9.4.9. Выровненные деревья Ордерево называется аыров еиным, если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях. Выровненное дерево имеет наименьшую возможную для данного р высоту 6. Пример На рнс. 9.12 приведены диаграммы выровненного (слева) и невыровненного (справа) деревьев. Рис. 9.12. Выровненное (слева) и невыровненное деревья ЛЕММА Е.=о 2 = 2ь+г 1 доказательство Индукция по )с. База: и = 0 =в 2о = 1, 2' — 1=1, 1=1.
ь Пусть 2,' 2' = 2ь+' — 1, тогда Ь+1 Ь ~2г = ~» 2г Р 2 + = 2~+~ — 1+2ь+~ =21~+г)+ — 1. Добавить Найти Удалить О(!) О(п) О(п) О(п) О(!оке(п)) О (и) О()ок,(п)),.О(п) О()ов (п))..О( ) О(!ок (п))..О(п) Глава 9 Деревья ТЕОРЕМА Для выровненного бинарного дерева 1ояз(р+ 1) — 1 < Ь <!ойз(р+ 1). Докаааткпьство На г-м уровне может быть самое большее 2* вершин, следовательно, 2'«р<~~г 2'.
а=о По лемме имеем: 2" — 1 < р < 2 "+' — 1 и 2" < р+ 1 < 2"+'. Логарифмируя, имеем: 1г < 1ойз(р+ 1) Й Ь+ 1 > >1окз(р+ 1), Следовательно, 1ок,(р+ 1) — 1 «А < 1ок,(р+ 1). ЗАМЕЧАНИЕ Выровненные деревья дают нанболыпнй возможный эффект прн поиске. Однако известно, что вставка/удаление может потребовать полной перестройки всего дерева н, таким образом, трудоемкость операции в худшем случае составит О(р).
9.4.10. Сбалансированные деревья (Бинарное) дерево называется подровненным деревом, или АВЛ-деревом (Адельсон-Вельский и Ландис, 1962), или сбалансированным деревом, если для любого узла высота левого и правого поддеревьев отличается не более чем на 1. Пример На рис. 9.13 приведена диаграмма максимально несимметричного сбалансированного дерева, в котором для всех узлов высота левого поддерева ровно на 1 больше высоты правого поддерева. ТЕОРЕМА Для подровненного бинарного дерева Ь' < 2 1окз р.
Доклзаткпьство Рассмотрим наиболее несимметричные АВЛ-деревья, скажем, такие, у которвгх всякое левое поддерево на 1 выше правого. Такие АВЛ-деревья имеют максимальную возможную высоту среди всех АВЛ-деревьев с заданным числом вершин. Пусть Рь — число вершин в наиболее несимметричном АВЛ-дереве высоты Ь.
По постРоению имеем: Р = Рь = Рь г + Рь г + 1. НепосРедственно проверяется, что Ро =.1, Рг = 2, Рг = 4. Покажем по индукции, что Рь > (ъ~2)". База: Ро = 1, (ъ~~)о = 1 1 > 1. Р, = 2 (,/2) г =,Г2 2 >,/2. 9.9. Кратчайший остов Рис. 9.13. Сбалансированное дерево Пусть Р„> (т/2)л. Тогда Рвет = Рл + Рл — г + 1 > (ч 2) + (т/2)л т + 1 = = (Л)л(1+ — + — ) > (Л)л(1+ — ) > (Л)лЛ = (Л)л+'. (т/2) (т/2) л (т/2) Имеем: (т/2)" = 2л/з ( Рл — — р, следовательно, -" < 1оят р и Ь < 2 1ояв р. П ЗАМЕЧАНИЕ Известна более точная оценка высоты АВЛ-дерева: Ь < 1оя,ге+тат 2 1ояв Р.
Сбалансированные деревья уступают выровненным деревьям по скорости поиска (менее чем в два раза), однако их преимущество состоит в том, что известны алгоритмы вставки и удаления узлов в сбалансированное дерево, которые сохраняют сбалансированность и в то же время при перестройке дерева затрагивают только конечное число узлов (см., например, (13]). Поэтому в подавляющем большинстве случаев АВЛ-дерево оказывается наилучшим вариантом представления дерева сортировки. 9.5.
Кратчайший остов Задача отыскания кратчайшего остова графа является классической задачей теории графов. Методы решения этой задачи послужили основой для многих других важных результатов. В частности, исследования алгоритма Краснела, описанного в подразделе 9.5.3, привели в конечном счете к теории жадных алгоритмов, изложенной в разделе 2.7.5. 256 Глава 9. Деревья 9.5.1. Определения Пусть С()г Е) — граф. Остовной ноддэаф графа б(тг Е) — это подграф, содержащий все вершины. Остовный подграф, являющийся деревом, называется остоВОЛ4. ЗАМЕЧАНИЕ Остов определяется множеством ребер, поскольку вершины остова суть вершяны графа.
Несвязный граф не имеет остова. Связный граф может иметь много остовов. ОТСТУПЛЕНИЕ Если задать длины ребер, то можно поставить задачу нахождения кротчайшего остова. Эта залача имеет множество практических интерпретаций. Например, пусть задано множество аэродромов и нужно определить минимальный (по сумме расстояний) набор авиарейсов, который позволил бы перелететь с любого аэродрома на любой другой. Решением этой задачи будет кратчайший остов полного графа расстояний между аэродромами. ЗАМЕЧАНИЕ Существует множество различных способов найти какой-то остов графа.
Например, алгоритм поиска в глубину строит остов (тю ребрам возврата). Множество кратчайших путей нз заданной вершины ко всем остальным также образует остов. Однако этот остов может ие быть кратчайшим. Пример На рис. 9.14 показаны диаграммы (слева направо) графа, дерева кратчайших путей иэ вершины 1 с суммарным весом 5 и два кратчайших остова этого графа. 33 34 1 33 1 33 1 э, 33 34 1 эт эт 1 43 34 Рис.
9. 14. Граф, дерево кратчайших путей и деа кратчайших остова 9.5.2. Схема алгоритма построения кратчайшего остова Рассмотрим следующую схему алгоритма построения кратчайшего остова. Пусть Т вЂ” множество непересекающихся деревьев, являющихся подграфами графа сг. Вначале Т состоит из отдельных вершин графа ст, в конце Т содержит единственный элемент — кратчайший остов графа 44. 267 9.5.
КРатчайший остов Алгоритм 9.6. Построение кратчайшего остова Вход: граф С($; Е), заданный матрнпей длин ребер С. Выход: кратчайший остов Т. Т: = !г тчйй!е в Т больше одного элемента до взять любое поддерево из Т найти к нему ближайшее соединить эти деревья в Т епд чав!е ТЕОРЕМА Алгоритм 9.6 строит кратчайший остов. Доказатвльство Пусть Т, и Т, — два произвольных поддерева С, Т; П Т ф О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
