1/7 для всех N >7; см. упр. 11.) Однократный и двукратный повороты практически равновероятны при Л < 15, однако при Л > 16 двукратные повороты встречаются немного реже.

Таблица 2

ТОЧНЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ 10-ГО ЭЛЕМЕНТА

Из табл. 1 видно, что к < 2 с вероятностью около .143 + .152 + .143 + .143 = .581; следовательно, шаг Аб почти в 60% случаев тривиален. Среднее количество изменений фактора сбалансированности с О на ±1 на этом шаге примерно равно 1.8. Среднее количество изменений фактора сбалансированности с ±1 до О на шагах А7-А10 составляет примерно .534-Ь 2(.233-Ь .232) и 1.5. Таким образом, вставив новый узел, можно добавить в среднем около 1.8 - 1.5 = 0.3 несбалансированного узла. Это согласуется с тем, что около 68% всех узлов в сбалансированных случайных деревьях, построенных по алгоритму А, оказываются сбалансированными.

Приближенная модель алгоритма А была предложена К. К. Фостером (С. С. Foster) [Ргос. АСМ Nat. Conf. 20 (1965), 192-205]. Эту модель сложно назвать абсолютно точной, но она достаточно близка к истине, чтобы дать некоторое понимание происходящего. Предположим, что в большом дереве, построенном по алгоритму А, фактор сбалансированности узла соответственно равен О с вероятностью р, равен - 1 с вероятностью (1 -р) и равен +1 с той же вероятностью. Предположим далее (без обоснования), что факторы сбалансированности различных узлов независимы. Значит, вероятность того, что на шаге Аб число ненулевых факторов и - I равно к-1, равна р*~(1 -р), так что среднее значение и равно 1/(1 - р). Вероятность того, что потребуется повернуть часть дерева, равна 5 и . Вставка нового узла должна увеличить количество сбалансированных узлов в среднем на р; это число увеличивается на 1 на шаге А5, на -р/(1 - р) на шаге Аб, на q на шаге А7 и на 2q на шаге А8 или А9, так что должно получиться

р=1-р/(1-р)+35«5/2-р/(1-р).

Решение этого уравнения относительно р дает хорошее согласование с табл. 1:

9 - л/4Т

р «- « 0.649; 1/(1 - р) « 2.851. (14)

Время работы фазы поиска программы А (строки 01-19) равно

10C + C1 + 2D + 2-3S, (15)

где С, С1 и 5 те же, что и в предыдущих алгоритмах этой главы, а D - число несбалансированных узлов, которью проходятся при поиске. Эмпирические тесты

показывают, что можно принять D « С, Cl « \{С + S), С + S l.OllgA + 0.1, так что среднее время поиска примерно равно 11.3IgiV + 3.3 - 13.75 единиц. (Если поиск осуществляется значительно чаще вставки, конечно же, можно использовать отдельную, более быструю программу поиска, поскольку не нужно следить за факторами сбалансированности. В этом случае среднее время работы при успешном поиске составило бы около (6.6IgiV - 3.4)и и даже в наихудшем случае было бы меньше, чем среднее время работы программы 6.2.2Т.)

При неудачно завершенном поиске время работы фазы вставки программы А (строки 20-45) составляет 8F -Ь 26 -Ь (О, 1 или 2) единиц. Данные из табл. 1 показывают, что в среднем Р « 1.8. Для фазы балансировки (строки 46-101) требуется 16.5, 8, 27.5 или 45.5 (±0.5) единиц времени в зависимости от того, что мы делаем: увеличиваем общую высоту, просто выходим (без балансировки) или выполняем однократный либо двукратный поворот. Первый случай практически не встречается; вероятности остальных составляют около .534, .233 и .232,. так что среднее время работы комбинированной "вставочно-балансировочной" части программы А - примерно бЗи.

Эти числа показывают, что операции над сбалансированными деревьями выполняются достаточно быстро, хотя программы при этом несколько больше по размеру. При случайных входных данных простой алгоритм вставки в дерево, описанный в разделе 5.2.2, работает быстрее примерно на 50и на одну вставку. Однако, используя сбалансированные деревья, можно получить хорошие результаты даже при неслучайных входных данных.

Один из способов сравнения программы А с программой 6.2.2Т заключается в рассмотрении наихудшего для последней программы случая. Если попытаться выяснить, сколько времени потребуется для вставки N ключей в порядке возрастания в изначально пустое дерево, то окажется, что программа А работает медленнее при iV < 26 и быстрее - при N > 27.

Представление линейных списков. Теперь вернемся к следующему сделанному в начале этого раздела замечанию: сбалансированные деревья могут использоваться для представления линейных списков таким образом, что можно будет быстро вставлять элементы в список, преодолевая трудности, которые связаны с последовательным расположением элементов, и обеспечивая при этом произвольный доступ к элементам списка, т. е. преодолевая сложности связанного размещения элементов.

Идея состоит во введении нового поля RANK в каждом узле. Это поле указывает относительное положение узла в его поддереве, а именно - единица плюс количество узлов в его левом поддереве. На рис. 24 показаны значения RANK для бинарного дерева, приведенного на рис. 23. При представлении списков поле KEY можно полностью исключить (при желании можно оставить оба поля, чтобы иметь возможность находить элементы как по значению ключа, так и по относительному положению в списке).

Используя такое поле RANK, можно свести поиск по положению элемента к модификации уже изученных нами алгоритмов.

Алгоритм В {Поиск в дереве по положению элемента). Дан линейный список, представленный в виде бинарного дерева. Алгоритм позволяет найти к-й элемент списка {к-й узел дерева в симметричном порядке) по заданному к. Предполагается,

Рис. 24. Поля RANK для поиска по положению элемента в списке.

что, как и в алгоритме А, имеется головной узел и что узлы дерева имеют поля LLINK и RLINK, а также описанное поле RANK.

81. [Инициализация.] Установить М /с, Р RLINK(HEAD).

82. [Сравнение.] Если Р = Л, алгоритм заканчивается неудачно (это может произойти, только если к было больше, чем количество узлов в дереве, или к < 0). В противном случае, если М < RANK(P), перейти к шагу ВЗ; если М > RANK(P), перейти к шагу В4; если М = RANK(P), алгоритм успешно завершается (Р указывает на к-й узел).

83. [Перемещение влево.] Присвоить Р <г- LLINK (Р) и вернуться к шагу В2.

84. [Перемещение вправо.] Присвоить М М-RANK(Р) и Р RLINK(Р) и вернуться к шагу В2. I

В этом алгоритме определенный интерес представляет только операция над М на шаге В4. Аналогично можно модифицировать процедуру вставки элемента, хотя в этом случае имеются определенные тонкости.

Алгоритм С {Вставка в сбалансированное дерево по положению). Дан линейный список, представленный в виде сбалансированного бинарного дерева. Алгоритм вставляет новый узел непосредственно перед к-ш элементом списка по заданным к и указателем Q на новый узел. Если к = N + 1, новый узел вставляется за последним элементом списка.

Бинарное дерево, как и в случае использования алгоритма А, предполагается непустым, имеющим головной узел; также предполагается, что узлы имеют поля LLINK, RLINK и В, а также поле RANK, описанное выше. Этот алгоритм очень похож на алгоритм А; отличие заключается в использовании и обновлении полей RANK вместо KEY.

Cl. [Инициализация.] Установить Т HEAD, S Р RLINK (HEAD), U М /с.

С2. [Сравнение.] Если М < RANK(P), перейти к шагу СЗ, в противном случае перейти к шагу С4.

СЗ. [Перемещение влево.] Установить RANK(P) RANK(P) -Ь 1 (будем вставлять новый узел слева от Р). Установить R <г- LLINK(P). Если R = Л, присвоить LLINK(Р) Q и перейти к шагу С5. В противном случае, если B(R) ф О,