Главная Промышленная автоматика.

Q end then

С begin )

elsej Рис. 4.4. Дерево двоичного поиска.

1) l(u)<.l{v) для каждого узла и из левого поддерева узла v,

2) 1{и)> I (v) для каждого узла и из правого поддерева узла V,

3) для каждого элемента aS существует в точности один узел V, для которого l{v)=a.

Заметим, что из услови< 1 и 2 вытекает, что метки этого дерева расположены в соответствии с внутренним порядком. Кроме того, условие 3 следует из условий 1 и 2.

Пример 4.3. На рис. 4.4 изображено возможное двоичное дерево для выделенных слов Алгола begin, else, end, if, then. Здесь линейным порядком является лексикографический порядок. □

Чтобы выяснить, принадлежит ли элемент а множеству S, представленному деревом двоичного поиска, надо сравнить а с меткой корня. Если метка корня равна а, то очевидно, что agS. Если а меньше метки корня, то надо перейти к левому поддереву корня (если оно есть). Если а больше метки корня, то надо перейти к правому поддереву корня. Если а присутствует в дереве, его местоположение будет в конце концов обнаружено. В противном случае процесс окончится, когда надо будет найти несуществующее левое или правое поддерево.

Алгоритм 4.1. Просмотр дерева двоичного поиска

Вход. Дерево Т двоичного поиска для множества S и элемент а.

Выход. "Да", если agS, и "нет" в противном случае.

Метод. Если дерево Т пусто ), выдать "нет." В противном слу-

) Хотя наше определение понятия дерева требует, чтобы дерево содержало хотя бы один узел, а именно корень, во многих алгоритмах мы будем трактовать пустое дерево (дерево без узлов) как двоичное.



procedure ПОИСК(а, v):

1. if a = l(v) tlien return "да" else

2. if a < / (v) then

3. if V имеет левого сына w then return ПОИСК(а, w)

4. else return "нет" else

5. if V имеет правого сына w then return ПОИСК(а, w)

6. else return "нет"

Рис. 4.5. Просмотр дерева двоичного поиска.

чае пусть г - корень дерева Т. Тогда алгоритм состоит из единственного вызова ПОИСК (а, г) рекурсивной процедуры ПОИСК, приведенной на рис. 4.5. □

Очевидно, что алгоритм 4.1 достаточен для выполнения операции ПРИНАДЛЕЖАТЬ (а, S). Более того, его легко модифицировать так, чтобы он выполнял операцию ВСТАВИТЬ (а, S). Если дерево пусто, строится корень с меткой а. Если дерево непусто, а элемент, который надлежит вставить, не обнаружен в дереве, то процедуре ПОИСК не удается найти сына в строке 3 или 5. Вместо того чтобы выда1ь "нет" в строке 4 или 6 соответственно, для этого элемента строится новый узел там, где должен был быть отсутствующий сын.

Деревья двоичного поиска также удобны для выполнения операций MIN и УДАЛИТЬ. Для нахождения наименьшего элемента в дереве двоичного поиска Т просматривается путь Vo, Vi, . . ., Vp, где у о-корень дерева Т, -левый сын узла Vi-i, lip, и у узла Vp нет левого сына. Метка в узле является наименьшим элементом в Г. В некоторых задачах может оказаться удобным иметь указатель на Vp, чтобы обеспечить доступ к наименьшему элементу за постоянное время.

Реализовать операцию УДАЛИТЬ (а, S) немного труднее. Допустим, что элемент а, подлежащий удалению, расположен в узле v. Возможны три случая:

\) V - лист; в этом случае v удаляется из дерева;

2) у V в точности один сын; в этом случае делаем отца узла v отцом его сына, тем самым удаляя v из дерева (если v - корень, то его сына делаем новым корнем);

3) у у два сына; в этом случае находим в левом поддереве узла v наибольший элемент Ь, рекурсивно удаляем из этого поддерева узел, содержащий Ь, и метим узел v элементом Ь. (Заметим, что среди элементов, меньших а, b будет наибольшим элементом всего дерева.)



( begin then }

Рис. 4.6. Дерево двоичного поиска после выполнения операции УДАЛИТЬ.

В качестве упражнения предлагаем написать программу на Упрощенном Алголе для операции УДАЛИТЬ. Заметим, что одно выполнение любой из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ, УДАЛИТЬ и MIN можно осуществить за время О (п).

Пример 4.4. Предположим, что надо удалить слово if из дерева двоичного поиска, изображенного на рис. 4.4. Слово if расположено в корне, у которого два сына. Наибольшее слово, меньшее if (лексикографически), расположенное в левом поддереве корня,- это end. Удаляем из дерева узел с меткой end и заменяем if на end в корне. Затем, поскольку end имеет одного сына (begin), делаем begin сыном корня. Полученное дерево показано на рис. 4.6. □

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

В худшем случае добавление к дереву п элементов может потребовать квадратичного времени. Например, допустим, что последовательность элементов, которые надлежит добавить, оказалась упорядоченной (в порядке возрастания). Тогда дерево поиска будет просто цепью правых сыновей. Но если вставляется п случайных элементов, то, как показывает следующая теорема, вставка потребует время О (п log п).

Теорема 4.4. Среднее число сравнений, необходимых для вставки п случайных элементов в дерево двоичного поиска, пустое вначале, равно О(п log/г) для /г> 1.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 [42] 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021