Структуры данных и алгоритмы (1021739), страница 37
Текст из файла (страница 37)
Отметим,что, поскольку в данном случае SET и указатель на узел — синонимы, функция можетвызывать сама себя для проведения поиска по поддереву, как если бы это поддеревопредставляло все множество. Другими словами, множество можно как бы разбить наподмножество элементов, которые меньше х, и подмножество элементов, больших х.Листинг 5.1. Процедура MEMBER для дерева двоичного поискаfunction MEMBER ( х: elementtype; A: SET ) : boolean;{ возвращает true, если элемент х принадлежит множеству А,false — в противном случае }1Напомним, что любой узел считается (по определению из раздела 3.1 главы 3) предкомсамого себя, поэтому мы здесь не исключаем возможность, что элемент х может совпасть с левым сыном корня.5.1.
ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА147beginif A = nil thenreturn(false) { x не может принадлежать 0 }else if x = At.element thenreturn(true)else if x < At.element thenreturn(MEMBER(x, At.leftchild) )else { x > At.element }return (MEMBER (x, лТ.г1дгЛЬсЛ11<5) )end; { MEMBER }Процедура INSERT(jc, А), которая добавляет элемент х в множество А, также проста для написания. Первым действием этой процедуры должна быть проверка условия А = nil, т.е.
не является ли множество А пустым. Если это так, то создается новый узел, содержащий х, и А делается указателем на этот узел. Если множество А непустое, то, сначала производится поиск элемента, совпадающего с х (это делаетсяпримерно так же, как в функции MEMBER).
Если элемент х уже есть в множестве,то никакие действия дальше не производятся. Если же в процессе поиска будет достигнут указатель nil (т.е. дошли до листа дерева), то он заменяется на указатель,указывающий на новый узел, содержащий элемент х. Код этой процедуры приведенв листинге 5.2.Листинг 5.2. Вставка нового элемента в дерево двоичного поискаprocedure INSERT ( x: elementtype; var A: SET ) ;beginif A - nil then beginnew(A);At .element:= x;At.leftchild:- nil;At.
rightchild:= nilendelse if x < At.element thenINSERT(x. At.leftchild)else if x > At.element thenINSERTU, At.rightchild){ если х = At.element, то никаких действийне производится, т . к . х уже есть в множестве А }end; { INSERT }Удаление элемента представляет некоторые трудности. Сначала надо найтиэтот элемент в дереве. Если х является листом, то он просто удаляется. Но еслих является внутренним узлом (назовем его для краткости inode. от interiornode — внутренний узел), то его нельзя просто удалить, так как нарушится связанность дерева.Если inode имеет только одного сына (как узел 14 на рис.
5.1,6), то его можно заменить этим сыном. Если inode имеет двух сыновей, как узел 10 на рис. 5.1,а, то средипотомков правого сына надо найти элемент с наименьшим значением1 и заменить имудаляемый элемент. Например, для узла 10 на рис. 5.1,а таким будет узел 12.Для написания процедуры DELETE полезно иметь функцию DELETEMIN(A), которая удаляет наименьший элемент из непустого дерева и возвращает значение удаляемого элемента. Код функции DELETEMIN приведен в листинге 5.3, а код процедуры DELETE, использующий эту функцию, — в листинге 5.4.1V148Можно также искать элемент с наибольшим значением среди потомков левого сына.ГЛАВА 5.
СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВЛистинг 5.3. Удаление наименьшего элементаfunction DELETEMIN ( var Л: SET ): elementtype;beginif AT.leftchild = nil then begin{ А указывает на наименьший элемент }DELETEMIN:= AT.element;A:= AT.rightchild{ замена узла, указанного А, его правым сыном }endelse { узел, указанный А, имеет левого сына }DELETEMIN:= DELETEMIN(AT.leftchild)end; { DELETEMIN }Листинг 5.4. Удаление элемента из дерева двоичного поиска>,'••••-:••, *-• '-,-•.
•Г":-.•к/,.- '.••::, .::ад•>•-•'.Л т-йprocedure DELETE ( x: elementtype; var A: SET );beginif A < > nil thenif x < AT.element thenDELETE(x, AT.leftchild)else if x > AT.element thenDELETE(x, AT.rightchild)else if (AT.leftchild= nil) and (AT.rightchild= nil) thenA : = nil { удаление листа, содержащего х }else if AT.leftchild = nil thenA : = AT.rightchildelse if AT.rightchild = nil thenA:= AT.leftchildelse { у узла есть оба сына }AT.element:= DELETEMIN(AT.righ tchild)end; { DELETE }Пример 5.1.
Предположим, надо удалить элемент 10 из дерева, показанного нарис. 5.1,а. В данном случае первым исполняемым оператором в процедуре DELETE будет вызов функции DELETEMIN с аргументом-указателем на узел 14. Этот указатель —значение поля rightchild корня. Результатом этого вызова будет еще один вызов той жефункции DELETEMIN. В этом случае ее аргументом будет указатель на узел 12, который находится в поле leftchild узла 14. Узел 12 не имеет левого сына, поэтому функция возвращает элемент 12 и устанавливает указатель узла 14 на левого сына в состояние nil. Затем процедура DELETE берет значение 12, возвращенное функциейDELETEMIN, и заменяет им элемент 10.
Результирующее дерево показано на рис. 5.2. П15Рис. 5.2. Дерево, представленное нарис. 5.1,а, после удаления элемента 105.1. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКАг1495.2. Анализ времени выполнения операторовВ этом разделе мы проанализируем работу различных операторов, выполняемыхнад деревьями двоичного поиска. Мы покажем, что если в первоначально пустое дерево двоичного поиска вставлено п произвольных элементов, то средняя длина путиот корня до листа будет O(logn). Отсюда следует, что среднее время выполнения оператора MEMBER также будет иметь порядок O(logn).Легко видеть, что если двоичное дерево полное (т.е. все узлы, за исключением самого нижнего уровня, имеют двух сыновей), то не существует пути, содержащего более1 + logn узлов1. Поэтому операторы MEMBER, INSERT, DELETE и DELETEMIN имеютвремя выполнения порядка O(logTi).
Чтобы доказать это, достаточно заметить, что всеэти операторы затрачивают фиксированное время на обработку одного узла, затем рекурсивно вызывают себя для обработки сына рассматриваемого узла. Последовательность узлов, в которых выполняется рекурсивный вызов процедур, формирует путь,исходящий из корня дерева. Поскольку такой путь имеет в среднем длину O(logn), то иобщее время прохождения операторами этого пути будет иметь такой же порядок.Однако когда элементы вставляются в произвольном порядке, они не обязанырасполагаться в виде полного двоичного дерева. Например, если вставка начата снаименьшего элемента и далее элементы вставляются в порядке возрастания, тополучим дерево в виде цепочки узлов, где каждый узел имеет правого сына, ноне имеет левого.
В этом случае, как легко показать, на вставку i-ro элементатребуется O(i) шагов, для завершения всего процесса вставки га элементов необходимо У i = л(п + 1)/2 шагов, т.е. порядка О(п2), или О(п) на одно выполнениеЛт41=\оператора вставки.Мы должны уметь определять, когда "среднее" дерево двоичного поиска из п узловближе по своей структуре к полному двоичному дереву, а когда к цепочке узлов, таккак в первом случае среднее время выполнения операторов имеет порядок O(logn), а вовтором — О(п). Если мы не знаем последовательность выполненных (или тех, которыебудут выполнены в будущем) операций вставки и удаления элементов, а также свойства этих элементов (например, мы не можем всегда удалять только минимальные элементы), то естественно предположить, что анализу подлежат только пути "средней"длины на "случайных" деревьях.
В частности, мы вправе предполагать, что деревьясформированы только вставкой элементов и все последовательности вставляемых элементов равновероятны на фиксированном множестве из п элементов./7-/-1элементов > аРис. 5.3. Построение дерева двоичного поискаПринимая эти достаточно естественные предположения, можно вычислить Р(п) —среднее число узлов в пути от корня до некоторого узла (не обязательно листа).Предполагая, что дерево формируется путем вставки п произвольных элементов в1150Напомним, что все логарифмы, пока не сказано другое, определены по основанию 2.ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВпервоначально пустое дерево, очевидно, что Р(0) = 0 и Р(1) — 1. Пусть в списке изп > 2 элементов, готовых к вставке в пустое дерево, первым находится элемент а.
Если отсортировать список, то элемент а с равной вероятностью может занимать любоеместо от 1 до п. Пусть в списке i элементов меньше а, и, следовательно, п — i — 1элементов больше, чем а. Тогда при построении дерева в его корне поместится элемент а (поскольку он первый элемент списка), i наименьших элементов будут потомками левого сына корня, а оставшиеся п - i - 1 элементов — потомками правого сына корня. Это дерево показано на рис.
5.3.Так как любые последовательности i наименьших элементов и п - i - 1 наибольших элементов равновероятны, мы вправе предположить, что средняя длина путей влевом и правом поддеревьях будет P(i) и Р(п - i - 1) соответственно. Поскольку путидолжны начинаться от корня полного дерева, то к P(i) и Р(п - i - 1) надо еще прибавить 1. Тогда Р(п) можно вычислить путем усреднения для всех i от 0 до п - 1 следующих сумм:~(P(i} + 1) + П~1'1(Р(п - i - 1) + 1) + -,пппгде первое слагаемое — средняя длина пути в левом поддереве с весовым коэффициентом i/n, значение второго слагаемого аналогично, а 1/га соответствует "вкладу" впуть корня.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
