Новиков Ф.А. Дискретная математика для программистов (860615), страница 60
Текст из файла (страница 60)
Нетрудно проверить, чтоусловие дерева сортировки выполняется и в этом случае.[ 3 ] Правая связь удаляемого узла р пе пуста и ведёт в узел и, левая связь которого не пуста. Поскольку дерево сортировки конечно, можно спуститься от узлаи до узла v, левая связь которого пуста (см. рис.
9.12, справа). В этом случаевыполняются два преобразования дерева. Сначала информация в узле р заменяется информацией узла v. Поскольку узел v находится в правом поддереве узлар и в левом поддереве узла и, имеем p.i < v.i < u.i. Таким образом, после этогопреобразования условие дерева сортировки выполняется. Далее правое поддерево 4 узла v подцепляется слева к узлу w, а сам узел v удаляется. Посколькуподдерево 4 входило в левое поддерево узла к;, условие дерева сортировки такжесохраняется.•ЗАМЕЧАНИЕВ книге [14], из которой заимствован данный алгоритм, показано, что хотя алгоритм «выглядит несимметричным» (правые и левые связи обрабатываются по-разному), па самомделе в среднем характеристики дерева сортировки не искажаются.9.4.7.
Вспомогательные алгоритмыдля дерева сортировкиАлгоритмы трех предыдущих разделов используют вспомогательные функции,описанные здесь.1. Поиск узла — функция Find.Вход: дерево сортировки Т, заданное указателем на корень; ключ а : key.Выход: р — указатель па найденный узел или nil, если в дереве пет такого ключа;q — указатель па отца узла р; s — способ подцепления узла q к узлу р (s = — 1,если р слева от q; s — +1, если р справа от q; s = 0, если р — корень).p: = T;q: = nil; s : — 0 { инициализация }while р Ф nil doif p.i = a thenreturn p, q, send ifq: = p { сохранение значения p }if a < p.i thenp : = p.i; s : = — 1 { поиск слева }else3219.4. Деревья сортировкир: — p.r; s: = +1 { поиск справа }end ifend whilereturn p, q, sОТСТУПЛЕНИЕВ этой простой функции стоит обратить внимание па использование указателя q, который отслеживает значение указателя р «с запаздыванием», то есть указатель q «помнит»предыдущее значение указателя р.
Такой приём полезен при обходе однонаправленныхструктур данных, в которых невозможно вернуться назад.2. Удаление узла — процедура Delete.Вход: р\ — указатель на удаляемый узел; р2 — указатель па подцепляющий узел;рЗ — указатель па подцепляемый узел; s — способ подцепления.Выход: преобразованное дерево,if s = - 1 thenp2.l:=p3 { подцепляем слева }end ifif s = +1 thenp2.r: = p3 { подцепляем справа }end ifdispose(pl) { удаляем узел }3. Создание нового узла — конструктор NewNode.Вход: ключ а.Выход: указатель р па созданный узел,new(p);p.i : = a; p.i: = nil; p.r: — nilreturn p9.4.8. Сравнение представлений ассоциативной памятиПусть п — количество элементов в ассоциативной памяти.
Тогда сложность операций для различных представлений ограничена сверху следующим образом.НеупорядоченныймассивДобавитьНайтиУдалитьУпорядоченныймассивДеревосортировки0(Т)0(п)0(log2(n))..0(n)0(п)Q(N)O(log 2 (n))О(П)0(log 2 (n))..0(n)Q(log 2 (n))..Q(n)Эффективность операций с деревом сортировки ограничена сверху высотой дерева.ЗАМЕЧАНИЕДерево сортировки может расти неравномерно. Например, если при загрузке дерева исходные данные уже упорядочены, то полученное дерево будет право- или леволинейпыми окажется даже менее эффективным, чем неупорядоченный массив.322Глава 9. ДеревьяВ последующих подразделах обсуждаются методы уменьшения высоты деревасортировки.9.4.9. Выровненные и полные деревьяБинарное дерево называется выровненным, если все листья находятся на одном(последнем) уровне. В выровненном дереве все ветви имеют одну длину, равную высоте дерева, однако выровненное дерево не всегда является эффективнымдеревом сортировки.Пример Дерево, состоящее из корня и двух поддеревьев, леволинейного и праволинейного, ведущих к двум листьям, является выровненным, однако такоедерево имеет высоту (р - 1)/2.Бинарное дерево называется заполненным, если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях.
Другими словами, в заполненном дереве Т все ярусы D(r,i), кроме, может быть, последнего,заполнены:Vг е 0..(h(T) — 1) (|£>(г,г)| =2*).Пример На рис. 9.13 приведены диаграммы заполненного (слева) и незаполненного (справа) деревьев.ЛЕММАYLI=O2 I=2 K + 1~Lформуле для суммы геометрической прогрессии jT\ = 0 2г == 1 + 2 + ... + 2 == 2k+1 - 1.•ДОКАЗАТЕЛЬСТВОПОfcЗаполненное дерево имеет наименьшую возможную для данного р высоту h.ТЕОРЕМАДля заполненного бинарного дерева log2(p + 1) - 1 ^ h < log2(p + 1).9.4.
Деревья с о р т и р о в к и323На г-м уровне может быть самое большее 2г вершин, следовательно, Yli=o< Р ^ J2i=0 2*. По лемме 2h < р + 1 ^ 2h+1, и, логарифмируя,имеем: h < log2(р + 1) и h + 1 ^ log2(p + 1). Следовательно, log2(p + 1) - 1 ^ h <<log2(p+l).•ДОКАЗАТЕЛЬСТВО2{Выровненное заполненное бинарное дерево называется полным. В полном бинарном дереве все листья находятся па последнем уровне и все узлы, кромелистьев, имеют полустепень исхода 2. Другими словами, в полном дереве всеярусы заполнены.СЛЕДСТВИЕПолное бинарное дерево высотой h имеет 2h+1 - 1 узлов.Иногда полным называют бинарное дерево, в котором все нелистовые узлы имеют полустепень исхода 2, но листья могут встречаться на любом уровне. Высотадерева, полного в таком смысле, может изменяться в широких пределах.ЗАМЕЧАНИЕЗаполненные деревья дают наибольший возможный эффект при поиске.
Однако известно,что вставка/удаление в заполненное дерево может потребовать полной перестройки всегодерева, и, таким образом, трудоёмкость операции в худшем случае составит 0(р).Желательно выделить такой подкласс деревьев сортировки, в котором высотаограничена и в то же время операции по вставке и удалению элементов выполняются эффективно. Было найдено несколько таких подклассов, наиболеепопулярный из них описывается в следующем подразделе.9.4.10. Сбалансированные деревья(Бинарное) дерево называется подровненным деревом, или АВЛ-деревом (АдельсоиВельский1 и Лаидис2, 1962), или сбалансированным по высоте деревом, если длялюбого узла высоты левого и правого поддеревьев различаются не более чем на 1.Пример На рис.
9.14 приведена диаграмма максимально несимметричного сбалансированного по высоте дерева, в котором для всех узлов высота левого поддерева ровно на 1 больше высоты правого поддерева.ЗАМЕЧАНИЕКроме сбалансированных по высоте, рассматривают и другие классы деревьев, например,сбалансированные по весу деревья, в которых для каждого узла количества узлов в левоми правом поддеревьях находятся в определённом соотношении. Здесь такие классы нерассматриваются, поэтому далее термин «сбалансированное дерево» означает сбалансированное по высоте бинарное дерево сортировки.12Георгий Максимович Адельсон-Вельский (р.
1922).Евгений Михайлович Лаидис ( 1 9 2 1 - 1 9 9 7 ) .Рис. 9 . 1 4 . Сбалансированное деревоТЕОРЕМАДля сбалансированного по высоте бинарного дерева h < 2 log2 p.Рассмотрим наиболее несимметричные сбалансированные деревья, скажем, такие, у которых всякое левое поддерево на 1 выше правого.Такие сбалансированные деревья имеют максимальную возможную высоту средивсех сбалансированные деревьев с заданным числом вершин.
Пусть Р}х — числовершин в наиболее несимметричном сбалансированном дереве высоты h. По построению имеем: р = Ph = Ph-i + Ph-2 + 1. Непосредственно проверяется, чтоРо = 1. Pi = 2, Р 2 = 4. Покажем по индукции, что P/t > {y/2)h. База: Ро = 1,(л/2)° = 1, 1 ^ 1; Pi = 2 (л/2)1 =Пусть Ph > {V2)h. ТогдаДОКАЗАТЕЛЬСТВОPh+1 =Ph + Р/г—i + 1 ^ (V2) h + (V2) h ~ l + 1 == ^ ( 1 + т + ш ) > {V~2)h ( 1+ ш) >=Имеем: (\/2) /l = 2h/2 ^ Ph = р, следовательно, | ^ log 2 p и h ^ 21og2p.•Можно заметить, что рекуррентное соотношение для Ph похоже па определениечисел Фибоначчи F(n) (см. 5.7.3), откуда легко выводимоСЛЕДСТВИЕЕсли h >0,то Ph = F(h) + Ph-ЬП О индукции.
База: Pi = 2, F ( l ) = 1, Р 0 = 1, 2 = 1 + 1. Пусть= F(h-l) + Ph-2. Рассмотрим Ph. Имеем Ph = Ph-i + Ph-2 + l = F(h-1) ++Ph-2+F{h- 2) + Ph-3 + l = F{h - 1 ) + F(h - 2)+PH-2+Ph-3+ l = F{h)+Ph-1.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕИзвестна более точная оценка высоты сбалансированного дерева: h < log/yg+1\ ,2 2 log2p.Сбалансированные деревья уступают заполненным деревьям по скорости поиска (менее чем в два раза), однако их преимущество состоит в том, что известныалгоритмы вставки узлов в сбалансированное дерево и удаления их из него, которые сохраняют сбалансированность и в то же время при перестройке дерева3259.4.
Деревья сортировкизатрагивают только конечное число узлов (см. следующий подраздел). Поэтомуво многих случаях сбалансированное дерево оказывается наилучшим вариантомпредставления дерева сортировки.9.4.11. Балансировка деревьевПри добавлении (или при удалении) узла в сбалансированном дереве сортировки может возникнуть ситуация, в которой баланс нарушается. В этом случаенеобходимо перестроить дерево, чтобы восстановить баланс. Алгоритм балансировки дерева представлен на рис. 9.15 и 9.16, при этом использованы следующиеобозначения: х — добавляемый узел, v — первый узел, в котором нарушен балансна пути от корпя г к новому узлу х. Тогда возможны два варианта.
Путь от vк х состоит либо из дуг одной ориентации (скажем, только из левых дуг), либоиз левых и правых дуг. Варианты, в которых путь состоит только из правых дуглибо из правых и левых дуг, зеркально симметричны. В первом варианте деревоперестраивается в соответствии с правилом простого вращения, представленнымпа рис. 9.15.h-hh-1\ уhh+ 1Рис. 9 . 1 5 . Простое вращение326Глава 9.
ДеревьяПростое вращение восстанавливает баланс и сохраняет условие дерева сортировки. Действительно, до преобразования имееми < v,p < v,q < v,p <и,q>u,w > v.Следовательно,p < u,u < v,u < q,u < w,q < v,w > vи преобразование не нарушает условия дерева сортировки. Во втором вариантедерево перестраивается в соответствии с правилом двойного вращения, представленным на рис. 9.16. Двойное вращеиие восстанавливает баланс и сохраняетРис. 9.16. Двойное вращениеусловие дерева сортировки. Действительно, до преобразования имееми <v,w > v,p > v,q> v,p < w,q > w,s > v,t > v,s < w,t < w,s < p,t > p.9.5. Кратчайший остов327Следовательно,v < р, и < р, s < р, и < v, s > v,w > p,t > p,q > p,t < w,q > wи преобразование не нарушает условия дерева сортировки.ЗАМЕЧАНИЕДетальное обсуждение алгоритмов работы с АВЛ-деревьями, включая оценки трудоёмкости в среднем и в худшем случае, можно найти в [26] и [16].9.5.
Кратчайший остовЗадача отыскания кратчайшего остова графа является классической задачей теории графов. Методы решеиия этой задачи послужили основой для многих другихважных результатов. В частности, исследования алгоритма Краскала1, описанного в подразделе 9.5.3, привели в конечном счёте к теории жадных алгоритмов,изложенной в подразделе 2.6.4.9.5.1. ОпределенияПусть G(V, Е) — граф. Остовный подграф графа G(V, Е) — это подграф, содержащий все вершины. Остовный подграф, являющийся деревом, называется остовомили каркасом.ЗАМЕЧАНИЕОстов определяется множеством рёбер, поскольку вершины остова суть вершины графа.Несвязный граф не имеет остова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
