О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 3
Текст из файла (страница 3)
Если бы дерево на Рис. 3(б) не было деревом поиска, то при поиске узла с ключом 6 надо было бы просмотреть от 4 до 6 узлов, в зависимости от порядка обхода дерева. А вдереве поиска при поиске узла движение происходит только вниз,поэтому количество шагов ограничено высотой дерева. Чем больше узлов в дереве, тем более очевидно преимущество дерева поиска над обычным двоичным деревом при условии, что дерево поиска хорошо сбалансировано.Как построить дерево поиска минимальной высоты? Если наборключей известен заранее, то его надо упорядочить.
Корнем поддерева становится узел с ключом, значение которого – медиана этогонабора. Для упорядоченного набора, содержащего нечетное количество ключей, – это ключ, находящийся ровно в середине набора.Для набора 1,2,3,4,5,6 из примера на Рис. 3, который содержитчетное количество ключей, в качестве медианы может быть вы14бран ключ как со значением 3, так и со значением 4.
Для определенности выберем 3. Узел с этим ключом будет корнем дерева.Далее, ключи, меньшие 3, попадут в левое поддерево, а ключи,большие 3, попадут в правое поддерево. Для построения левого иправого поддеревьев проделываем ту же процедуру на соответствующих наборах ключей. И так до тех пор, пока все ключи небудут включены в дерево. На Рис. 3(б) для каждого узла указаннабор ключей, для которых строится дерево с корнем в этом узле,и выделена медиана этого набора, которая и попадает в корень.Дерево, изображенное на Рис.
3(б) является идеально сбалансированным, то есть, для каждого его узла количество узлов в левом иправом поддеревьях различается не более, чем на 1. Такое деревоможно построить для любого набора ключей. Достаточно заметить, что при выборе медианы на каждом шагу при построениидерева набор ключей разбивается на две части, и количество ключей в них может различаться не более, чем на 1.121234563341256152(а)24456646(б)Рис.
3. Разные деревья поиска, построенные из одногои того же набора ключейПолный набор ключей не всегда известен заранее. Если ключи поступают по очереди, то построение дерева поиска будет зависетьот порядка их поступления. Если, например, ключи будут поступать в порядке 1,2,3,4,5,6, то получится дерево, изображенное наРис.
3(а). Высота такого дерева максимальна для этого набора15ключей, следовательно, и время выполнения операций над нимтакже будет максимальным. Поэтому при добавлении очередногоузла, возможно, дерево понадобится перестраивать, чтобы уменьшить его высоту, сохраняя тот же набор узлов. Идеальную балансировку поддерживать сложно. Если при добавлении очередногоузла количество узлов в левом и правом поддеревьях какого-либоузла дерева станет различаться более, чем на 1, то дерево не будетявляться идеально сбалансированным, и его надо будет перестраивать, чтобы восстановить свойства идеально сбалансированногодерева поиска.
Поэтому обычно требования к сбалансированностидерева менее строгие.В настоящем пособии рассматриваются три основных вида сбалансированных деревьев поиска: АВЛ-деревья, красно-черные деревья и самоперестраивающиеся деревья (splay-деревья). ДляАВЛ-деревьев сбалансированность определяется разностью высотправого и левого поддеревьев любого узла. Если эта разность помодулю не превышает 1, то дерево считается сбалансированным.Данное условие проверяется после каждого добавления или удаления узла, и определен минимальный набор операций перестройкидерева, который приводит к восстановлению свойства сбалансированности, если оно оказалось нарушено.
В красно-черных деревьяхкаждый узел имеет дополнительное свойство – цвет, красный иличерный. На дерево наложены ограничения по расположению и количеству узлов в зависимости от цвета, и определен набор операций перестройки дерева в случае нарушения этих ограничений после добавления или удаления узла. Если АВЛ-деревья накладывают достаточно строгие условия на сбалансированность, и придобавлении узлов дерево достаточно часто приходится перестраивать, то в красно-черном дереве у каждого узла высоты левого иправого поддеревьев могут отличаться не более, чем в два раза.
И,наконец, третий вид рассматриваемых сбалансированных деревьевпоиска – самоперестраивающиеся деревья. В отличие от двухпредыдущих видов, у этих деревьев нет никаких ограничений нарасположение узлов, а сбалансированность в среднем достигаетсяза счет того, что каждый раз перед выполнением операции над уз16лом этот узел перемещается в корень дерева. Но есть вероятностьтого, что дерево может оказаться не сбалансированным, как,например, на Рис. 3(а).3. АВЛ-деревьяАВЛ-деревом называется такое дерево поиска, в котором для любого его узла высоты левого и правого поддеревьев отличаются неболее, чем на 1. Эта структура данных разработана советскимиучеными Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем в 1962 году.
Аббревиатура АВЛ соответствует первым буквам фамилий этих ученых. ПервоначальноАВЛ-деревья были придуманы для организации перебора в шахматных программах. Советская шахматная программа «Каисса»стала первым официальным чемпионом мира в 1974 году.В каждом узле АВЛ-дерева, помимо ключа, данных и указателейна левое и правое поддеревья (левого и правого сыновей), хранится показатель баланса – разность высот правого и левого поддеревьев.
В некоторых реализациях этот показатель может вычисляться отдельно в процессе обработки дерева тогда, когда это необходимо.Cstruct AVLNode{key_type key;struct AVLNode *left;struct AVLNode *right;struct AVLNode *parent;int balance; // показатель баланса};17PascaltypeAVLTree = ^AVLNode;AVLNode = recordkey: key_type;left: AVLTree;right: AVLTree;parent: AVLTree;balance: integer;end;На Рис. 4(а) приведен пример АВЛ-дерева. Таким образом, получается, что в АВЛ-дереве показатель баланса balance для каждогоузла, включая корень, по модулю не превосходит 1. На Рис.
4(б)приведен пример дерева, которое не является АВЛ-деревом, поскольку в одном из узлов баланс нарушен, т.е. |balance|>1. Здесь идалее для АВЛ-деревьев будем указывать в узле значение показателя баланса.-10-2-10+1+1+1000X(а)(б)Рис. 4. (а) пример АВЛ-дерева; (б) пример дерева, не являющегосяАВЛ-деревом: в узле X сбалансированность нарушена3.1 Вставка узла в АВЛ-деревоРассмотрим, что происходит с АВЛ-деревом при добавлении нового узла.
Сначала узел добавляется в дерево с помощью стандартного алгоритма вставки в двоичное дерево поиска. Показателибаланса в ряде узлов при этом изменятся, и сбалансированностьможет нарушиться. Сбалансированность считается нарушенной,если показатель баланса по модулю превысил 1 в одном или нескольких узлах.При добавлении нового узла разбалансировка может произойтисразу в нескольких узлах, но все они будут лежать на пути от этогодобавленного узла к корню, как показано на Рис.
5.Тем не менее, перестраивать будем поддерево с корнем в том изэтих узлов, который является ближайшим к добавленному. В примере на Рис. 5 этот узел обведен кружком. Общее правило для всехдобавляемых узлов, приводящих к разбалансировке: чтобы найти18корень поддерева, которое понадобится перестраивать, надо подниматься вверх по дереву от вновь добавленного узла до тех пор,пока не найдется первый узел, в котором нарушена сбалансированность. Назовем его опорным узлом. Таким образом, искать этотузел надо, поднимаясь наверх, а не спускаясь вниз от корня.
Послетого как опорный узел будет найден, будет проведена процедураперестройки поддерева с корнем в этом узле с целью восстановления его сбалансированности. Остальная часть дерева останется впрежнем виде. При этом все дерево также станет сбалансированным — показатель баланса не будет превышать 1 по модулю вовсех узлах дерева. После демонстрации процедуры балансировкивам будет предложено обосновать этот факт самостоятельно.-2-20+10XРис. 5.
Добавление узла X в АВЛ-дерево привелок разбалансировке в двух узлах. Но перестраивать будем толькоподдерево с корнем в выделенном узлеВ зависимости от того, в какое поддерево опорного узла был добавлен новый узел, рассматривается четыре случая, которые можно разбить на две пары симметричных друг другу случаев.
В каждом из них баланс восстанавливается с помощью одного или двухповоротов. На Рисунках 6–9 опорный узел обведен кружком.Вновь добавленный узел обозначен буквой X.1. Добавление в левое поддерево левого сына опорного узла.Необходимо произвести правый поворот (R): опорный узел (B)поворачивается направо относительно своего левого сына (A).19B-2A -1A0hBT30hh+1T1T2T1hT2XT3XРис.
6. Добавление узла в левое поддерево левого сына опорногоузла и балансировка – правый поворотСитуация, требующая правого поворота после добавления новогоузла, схематично изображена на Рис. 6(а). Поддеревья Т1, Т2 и Т3могут быть пустыми, но они обязательно должны иметь одинаковую высоту. Тогда до добавления узла X у опорного узла B высоталевого поддерева будет на 1 больше, чем высота правого поддерева, а после добавления Х баланс нарушится именно в В, а не в А.После поворота направо (по часовой стрелке) вокруг узла A узел Bвместе с поддеревом T3 опустится на два уровня вниз относительно узла A. Самый нижний узел поддерева Т3 окажется на одномуровне с узлом X. Так как поддерево с корнем в B станет новымправым сыном A, его бывший правый сын T2 перейдет к B. Высота Т2 равна высоте Т3, поэтому и в B, и в A показатель балансастанет равен 0.TREE-ROTATE-R(T, x)/* На вход подается дерево T и опорный узел x. */1 y ← left[x]/* В строках 2–4 присоединяем T2 к x слева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
