О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 8
Текст из файла (страница 8)
Далее, проверяется значение ключа вкорне. Если оно равно k, значит, узел найден. Если же оно не равноk, значит, в корне находится его предшественник или последователь. Тогда k становится новым корнем и, в зависимости от того,было ли до этого в корне значение, большее k или меньшее, старый корень становится правым или, соответственно, левым сыномкорня. Пример показан на Рис. 24.SPLAY-INSERT(T, x)/* На вход подается дерево T и узел x, который надо добавить вдерево. */1 if root[T] = NULL then2root[T] ← x3return4 SPLAY(T, key[x])5 if key[root[T]] < key[x] then /* в корне находится предшественник x */526left[x] ← root[T]7right[x] ← right[root[T]]8if right[x] ≠ NULL then9parent[right[x]] ← x10 else /* в корне находится последователь x */11right[x] ← root[T]12left[x] ← left[root[T]]13if left[x] ≠ NULL then14parent[left[x]] ← x15 parent[root[T]] ← x16 root[T] ← xpred(k)kSplay(T,k)pred(k)< pred(k)>k> pred(k)< pred(k)(а)succ(k)kSplay(T,k)succ(k)> succ(k)< succ(k)<k> succ(k)(б)Рис.
24. Вставка узла с ключом k через операцию splay:(а) в корне находится предшественник узла с ключом k (pred(k));(б) в корне находится последователь узла с ключом k (succ(k))5.2 Удаление узла из самоперестраивающегосядерева53Перед тем, как удалить узел с ключом k из самоперестраивающегося дерева T, необходимо выполнить операцию splay(T, k) и проверить значение в корне. Если оно не равно k, то узла с таким ключом в дереве нет, поэтому удалять нечего.
Если оно равно k, то корень удаляется, а его левое и правое поддеревья склеиваются спомощью операции слияния concat(T->left, T->right). Пример приведен на Рис. 25.kSplay(T,k)Concat(T1,T2)T2T2T1T1Рис. 25. Удаление узла с ключом k через операции splay и concatОперация concat (T1, T2) – слияние двух деревьев поиска T1 и T2,таких, что все ключи в дереве T1 меньше, чем любой ключ в дереве T2, в одно дерево поиска, производится следующим образом.Сначала выполняется операция splay(max(T1), T1), в результате которой максимальный ключ в дереве T1 становится его корнем.
После этого у корня T1 не будет правого сына. Затем дерево T2 присоединяется в качестве правого сына к корню T1. Нетрудно проверить, что получившееся дерево сохранит свойства дерева поиска.Действительно, у корня T1 слева все ключи меньше него, т.к. в корень был помещен узел с максимальным ключом. А справа всеключи больше него, т.к. по условию все ключи в дереве T2 большевсех ключей в дереве T1. Схема выполнения операции слиянияприведена на Рис. 26.CONCAT(T1, T2)/* На вход подаются два дерева – T1 и T2, возвращается объединенное дерево. */1 if root[T1] = NULL then2return T23 if root[T2] = NULL then544return T15 y ← TREE-MAXIMUM(T1)6 SPLAY(T1, key[y])7 right[root[T1]] ← root[T2]8 parent[root[T2]] ← root[T1]9 return T1SPLAY-DELETE(T, k)/* На вход подается дерево T и значение ключа k, узел с которымнадо удалить из дерева.
Возвращается удаленный узел или NULL,если узла с таким ключом в дереве не оказалось. */1 SPLAY(T, k)2 if root[T] = NULL или key[root[T]] ≠ k then /* дерево пусто илиудаляемого узла в дереве нет */3return NULL4 x ← root[T]5 root[T] ← CONCAT(left[root[T]], right[root[T]])6 return xSplay(T,max(T1))T1T2T2Рис. 26. Слияние деревьев T1 и T2 через операцию splay5.3 Выполнение операции splay(T, k)Теперь рассмотрим, каким образом выполняется сама операцияsplay(T,k). Сначала производится поиск узла с ключом k в деревеобычным способом, спускаясь вниз, начиная с корня. При этомзапоминается пройденный путь. В итоге, получаем указатель наузел дерева либо с ключом k, либо с его предшественником илипоследователем, на котором закончился поиск.
Далее, происходит55возвращение назад по запомненному пути, с перемещением этогоузла к корню. Для того, чтобы при этом сохранялись свойства двоичного дерева поиска, необходимы повороты.Если узел c ключом k является сыном корня, как, например, в случае на Рис. 27, то потребуется одинарный поворот этого узла относительно корня таким образом, чтобы он сам стал корнем. В указанном примере понадобится поворот направо. Но можно в качестве примера привести симметричный случай, который потребуетаналогичного поворота налево.FkT1kT3NNT1T2FT2T3Рис.
27. Поднимаем узел с ключом k наверх – правый поворотЕсли у узла с ключом k есть дед, и при этом сам узел и его родитель являются одинаковыми потомками своих родителей (оба левыми или оба правыми), т.е. цепочка «узел – родитель – дед» образует прямую линию, как на Рис. 28, то понадобится последовательность из двух одинарных поворотов, которая приведет к тому,что узел с ключом k окажется наверху – сначала поворот деда вокруг отца, потом отца вокруг самого узла.
В примере на Рис. 28повороты будут правые.Также можно привести симметричный случай, где понадобятсядва последовательных поворота налево. Если последовательностьиз двух поворотов еще не приведет к тому, что узел с ключом kстанет корнем, потребуются новые повороты. В зависимости отрасположения новых родителя и деда узла с ключом k могут потребоваться повороты в другую сторону или двойной поворот,описанный ниже.
И так, пока случай не сведется к тому, которыйпоказан в примере на Рис. 27, где требуется одинарный поворотдля того, чтобы k оказался в корне.56GFT4FkT1kT3NT1NkT1GT2NT3FT4T2GT2T3T4Рис. 28. N-F-G образуют прямую линию: два правых поворотадля перемещения узла с ключом k в кореньДвойной поворот представляет собой уже известную из предыдущих разделов перестройку треугольника «узел – родитель – дед»таким образом, чтобы нижний узел стал верхним, а родитель и дедстали его новыми сыновьями. Применяется в тех случаях, когдаузел, его родитель и дед образуют не прямую линию, а угол, как впримере на Рис.
29.GT4FT1kT2kNNFT1GT2T3T4T3Рис. 29. N-F-G образуют угол: двойной поворот для перемещенияузла c ключом k в кореньSPLAY(T, k)/* На вход подается дерево T и значение ключа k */1 n ← TREE-SEARCH-INEXACT(T, k) /* в n будет либо узел сключом k, либо узел, на котором остановился поиск (его последователь или предшественник) */2 while n ≠ NULL и parent[n] ≠ NULL do3f ← parent[n]4g ← parent[f]5if g = NULL then6if n = left[f] then5778910111213141516171819202122TREE-ROTATE-R(T, f)elseTREE-ROTATE-L(T, f)elseif f = left[g] thenif n = left[f] thenTREE-ROTATE-R(T, g)TREE-ROTATE-R(T, f)elseTREE-ROTATE-LR(T, g)elseif n = right[f] thenTREE-ROTATE-L(T, g)TREE-ROTATE-R(T, f)elseTREE-ROTATE-RL(T, g)5.4 Оценка сложности операцийнад самоперестраивающимся деревомВо-первых, заметим, что все вышеперечисленные базовые операции(поиск, вставка, удаление) требуют выполнения O(1) операций splayи O(1) дополнительного времени.
Действительно, при поиске ивставке требуется одна операция splay, а при удалении – две. Дополнительные действия – просмотр корня, удаление вершины и т.п.занимают фиксированное время, которое не зависит от высоты дерева. Сама операция splay занимает O(n) времени, где n – количество узлов в дереве. Это происходит тогда, когда дерево совсем несбалансировано. Но, в целом, эти деревья за счет того, что они самоперестраивающиеся, имеют тенденцию к сбалансированности.Введем следующие понятия.Определение 7: Весом узла x называется количество узлов в поддереве T с корнем в x, включая сам узел: |T(x)|.58Определение 8: Рангом узла называется двоичный логарифм еговеса: r ( x) log 2 T ( x) .Проведем усредненную оценку сложности операций с помощьютак называемого метода бухгалтерского учета.
Представим, чтокаждая операция с деревом стоит фиксированную сумму денег заединицу времени. В самом начале каждый узел содержит кредит –r(x) рублей, т.е. сумму, равную его рангу, которая может частичноили полностью использоваться для оплаты операций. Также можно инвестировать дополнительную сумму для оплаты операций,помимо кредита. Если после серии операций над деревом и передначалом новых операций суммарный кредит (сумма рангов всехвершин) будет не меньше, чем до них, то будем говорить о сохранении денежного инварианта. Тогда можно проводить эту сериюопераций любое количество раз. Докажем следующую лемму.Лемма 2: Операция splay(T, x) требует инвестирования не болеечем 3 log 2 n 1 рублей с сохранением денежного инварианта.Доказательство:Сложность будет оцениваться по количеству поворотов.
Обозначим через r(x) и r (x) значения ранга узла x до и после поворота(1-го типа – одинарного, 2-го типа – серии из двух одинарных или3-го типа – двойного).Рассчитаем, какую сумму потребуется инвестировать, чтобы еехватило и на сохранение денежного инварианта, и непосредственно на операции.Ниже будет показано, что для выполнения поворота любого типа исохранения денежного инварианта требуется не более3(r( x) r ( x)) 1 рублей, причем 1 добавляется только при одинарном повороте.
При выполнении операции splay(T, x) производится последовательность из k поворотов 2-го и 3-го типов и поворота 1-го типа на заключительном этапе. После каждого поворотаранг узла x будет меняться. Пусть изначально ранг узла x состав59ляет r0(x), а после i-го поворота ri(x). Тогда для выполнения последовательности из k поворотов потребуется суммаk1 3(ri ( x) ri1 ( x)) 1 3(rk ( x) r0 ( x))(13)i 1Учитывая, что rk(x) = r(T), поскольку в конце последовательностиповоротов узел оказывается в корне всего дерева, а r0(x) = r(x), получаем общее количество рублей, необходимое для выполненияоперации splay(x, T) и сохранения денежного инварианта, равное3(r (T ) r ( x)) 1 рублей.
Учитывая, что минимальное значениеr(x) равно 0, а ранг дерева является логарифмом от количества егоузлов, получаем верхнюю оценку: 3 log 2 n 1 рублей.Теперь покажем, что для выполнения поворота и сохранения денежного инварианта требуется не более 3(r( x) r ( x)) 1 рублей.Рассмотрим каждый тип поворота по отдельности.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
