О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 2
Текст из файла (страница 2)
Возвращается узел дерева, в котором находится искомый ключ, или NULL, если узла с искомым ключом в деревенет. */1 x ← root[T]2 while x ≠ NULL и k ≠ key[x] do/* Просматриваем текущий узел, спускаясь по дереву вниз, пока ненайдем искомый ключ или не дойдем до пустого поддерева. */3if k < key[x] then4x ← left[x] /* присваиваем x его левого сына */5else6x ← right[x] /* присваиваем x его правого сына */7 return x7Эффективность по времени и памяти по сравнению с рекурсивнойреализацией достигается за счет того, что не нужно на каждом шаге заново вызывать функцию и хранить информацию, связанную стекущим ее вызовом.Определение 1: Высота дерева – это максимальная длина путиот корня до листа.При поиске узла на каждой итерации мы спускаемся на один уровень вниз, поэтому время поиска узла в двоичном дереве поиска,то есть, количество шагов, ограничено сверху высотой этого дерева.
Используя О-символику, можно обозначить время поиска вхудшем случае как O(h), где h – высота дерева.Если требуется найти в дереве узел с минимальным (максимальным) ключом, то, учитывая свойства дерева поиска, можно заметить, что это будет самый левый (самый правый) узел в дереве.Найти этот узел можно, двигаясь от корня только налево (направо)до тех пор, пока у рассматриваемого узла существует левый (правый) сын. На Рис. 1 минимальный ключ 30 находится в самом левом узле, а максимальный ключ – 89 – в самом правом узле. Поэтому операции поиска будут выглядеть следующим образом:TREE-MINIMUM(T)/* На вход подается дерево T, и возвращается узел с минимальнымзначением ключа в дереве.
*/1 x ← root[T]2 while left[x] ≠ NULL do /* ищем самый левый узел в дереве */3x ← left[x]4 return xTREE-MAXIMUM(T)/* На вход подается дерево T, и возвращается узел с максимальным значением ключа в дереве. */1 x ← root[T]2 while right[x] ≠ NULL do /* ищем самый правый узел в дереве */3x ← right[x]4 return x8Время их выполнения также будет O(h).Еще одна процедура поиска, которая может потребоваться, – поиск последователя узла, то есть, узла со следующим по значениюключом, который имеется в дереве. Если правое поддерево узла x сключом k не пусто, то последователем узла x будет самый левыйузел его правого поддерева, потому как это он имеет минимальныйключ среди всех ключей, больших k, имеющихся в дереве. Например, в дереве на Рис.
1 у узла с ключом 44 последователем является узел с ключом 45. Если правое поддерево узла x пусто, то надоискать, поднимаясь наверх, первого предка, для которого узел xокажется в левом поддереве. В примере на Рис. 1 у узла с ключом42 нет правого поддерева. Поднимаясь наверх, мы видим его родителя – узел с ключом 36, для которого узел с ключом 42 – правыйсын, поэтому узел с ключом 36 не может быть последователем.Поднимаясь далее, мы приходим в узел с ключом 44, для котороговсе предыдущее поддерево – левое. 44 больше и чем 36, и чем 42,значит, последователь найден.TREE-SUCCESSOR(T, x)/* На вход подается дерево T и узел x, и возвращается узел, который является его последователем. Если у узла нет последователя,то есть, узел является самым правым в дереве, то возвращаетсяNULL.
*/1 if right[x] ≠ NULL then/* Если у узла есть правое поддерево, то возвращаем самый левыйузел правого поддерева. */2return TREE-MINIMUM(right[x])/* Если у узла нет правого поддерева, то поднимаемся по родителям наверх, пока не найдем того, для которого рассматриваемыйузел – левый сын. */3 y ← parent[x]4 while y ≠ NULL и x = right[y] do5x←y6y ← parent[y]7 return y9Как видно из приведенного выше фрагмента кода, данная задачаимеет элегантное решение при наличии в описании узла дереванеобязательного поля – указателя на родительский узел.Время выполнения операции поиска последователя будет O(h),потому как оно ограничено высотой дерева – поиск идет либотолько вниз (когда ищем самый левый узел правого поддерева),либо только вверх (когда ищем первого предка, для которогоузел x окажется в левом поддереве).2.2 Вставка узла в двоичное дерево поискаВставка узла в двоичное дерево поиска выполняется после того, какнайдено место, куда можно вставить новый узел так, чтобы сохранились свойства дерева поиска.
Для этого выполняется поиск узла сэтим ключом в дереве. Если узел с таким ключом в дереве уже имеется, то вставку выполнять не нужно. В противном случае поискостановится на некотором узле, к которому впоследствии будетподсоединяться узел слева или справа в зависимости от значенияего ключа.
Так, в примере на Рис. 1 для вставки узла с ключом 32нужно запустить процедуру поиска, которая остановится на узле сключом 31, потому как поиск должен продолжаться в правом поддереве, а оно пусто. Затем узел 32 присоединится к нему справа.Опишем модифицированную операцию поиска, которая, если узелс искомым ключом не найден, возвращает не NULL, а тот узел, накотором остановился поиск.TREE-SEARCH-INEXACT(T, k)/* На вход подается дерево T, в котором производится поиск, и k– значение ключа.
Возвращается узел дерева, в котором находится искомый ключ, или тот узел, на котором остановился поиск. */1 y ← NULL2 x ← root[T]3 while x ≠ NULL и k ≠ key[x] do /* продолжаем поиск до тех пор,пока не найдем ключ или не дойдем до пустого дерева */104y←x5if k < key[x] then6x ← left[x]7else8x ← right[x]9 if x ≠ NULL /* ключ найден */10y ← x /* кладем в y узел x с ключом k вместо его родителя */11 return yTREE-INSERT(T, z)/* На вход подается дерево T и узел z, который надо добавить вдерево.
*/1 y ← TREE-SEARCH-INEXACT(T, key[z])2 parent[z] ← y3 if y = NULL then /* если дерево было пусто, то z станет корнем */4root[T] ← z/* Присоединяем z к y слева или справа в зависимости от значенияключа. */5 else if key[z] < key[y] then6left[y] ← z7 else8right[y] ← zВставка в двоичное дерево поиска требует O(h) шагов для выполнения поиска и еще O(1) (константное значение) шагов для выполнения непосредственно операции вставки, поэтому итоговое времявыполнения – O(h).2.3 Удаление узла из двоичного дерева поискаПри удалении узла из двоичного дерева поиска необходимо рассмотреть три случая:1. У узла нет сыновей – узел является листовым.В этом случае узел удаляется, и соответствующее поддерево егородителя становится пустым (Рис.
2(а)).112. У узла только один сын.Узел удаляется, и его сын переходит к его родителю (Рис. 2(б)).3. У узла два сына.Пусть В – удаляемый узел. Ищем его последователя С – узла с минимальным ключом в правом поддереве удаляемого узла. Переносим ключ узла C в узел В и сводим задачу к удалению узла С (Рис.2(в)). Эта процедура является корректной, потому что после удаления узла B его место должен занять как раз его последователь.Время поиска последователя, как было показано выше, ограниченовысотой дерева.CAACABBB(а)(б)УдаляемыйузелBСADСADADПереписываемзначениеCC(в)Рис.
2. Удаление узла из двоичного дерева поиска: (а) у узла нетсыновей; (б) у узла один сын; (в) у узла два сынаНиже приведена реализация функции удаления узла из двоичногодерева поиска. Узел исключается из дерева с помощью связываниямежду собой его сына (если есть) и отца (если есть). Память, занимаемая узлом, не освобождается, и этот узел возвращается функцией, чтобы затем его можно было использовать в других структу12рах. Если узел больше использоваться не будет, то память можноосвободить.TREE-DELETE(T, z)/* На вход подается дерево T и узел z, который надо удалить.
Возвращается удаленный узел. */1 if left[z] = NULL или right[z] = NULL then/* Если у узла z нет сыновей или один сын, то удаляемым узлом yбудет он сам. */2y←z3 else/* Если у узла z два сына, то удаляемым узлом y будет его последователь. У узла y может быть только правый сын, потому чтоэто самый левый элемент правого поддерева узла z. Таким образом, у узла y в любом случае только один сын.*/4y ← TREE-SUCCESSOR(z)/* В строках 5–16 прикрепляем x (сына y, если есть), к отцу y, либо делаем x корнем дерева. */5 if left[y] ≠ NULL then /* неприменимо, если y – последователь z */6x ← left[y]7 else8x ← right[y]9 if x ≠ NULL then10parent[x] ← parent[y]11 if parent[y] = NULL then12root[T] ← x13 else if y = left[parent[y]] then14left[parent[y]] ← x15 else16right[parent[y]] ← x17 if y ≠ z then/* Если удаляемым узлом оказался не z, а его последователь, токопируем в z ключ из y.
*/18key[z] ← key[y]19 return y13Удаление из двоичного дерево поиска требует O(h) шагов для поиска удаляемого узла, также может потребоваться дополнительноO(h) шагов для поиска его последователя, и O(1) шагов для выполнения непосредственно операции удаления узла. Поэтому итоговое время выполнения – O(h).2.4 Балансировка двоичного дерева поискаКак было показано выше, время выполнения базовых операций вдереве поиска линейно зависит от его высоты.
Но из одного и тогоже набора ключей можно построить разные деревья поиска, какпоказано на Рис. 3.В приведенном примере на Рис. 3 оба дерева построены из одногои того же набора ключей, но высота первого дерева больше, поэтому время выполнения операций над ним будет больше. Например, при поиске узла с ключом 6 в случае (а) требуется просмотреть все шесть узлов, а в случае (б) только три узла: 3->5->6. Второе дерево лучше сбалансировано, чем первое. В этом случаехорошо видно преимущество двоичного дерева поиска над обычным двоичным деревом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
