Быстрый поиск

Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

=====153

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

В этой главе обсуждаются методы, которые можно использовать для балансировки деревьев, даже если узлы удаляются и добавляются с течением времени. Балансировка дерева позволяет ему оставаться при этом достаточно эффективным.

Глава начинается с описания того, что понимается под несбалансированным деревом и демонстрации ухудшения производительности для несбалансированных деревьев. Затем в ней обсуждаются АВЛ‑деревья, высота левого и правого поддеревьев в каждом узле которых отличается не больше, чем на единицу. Сохраняя это свойство АВЛ‑деревьев, можно поддерживать такое дерево сбалансированным.

Затем в главе описываются Б‑деревья и Б+деревья, в которых все листья имеют одинаковую глубину. Если число ветвей, выходящих из каждого узла находится в определенных пределах, такие деревья остаются сбалансированными. Б‑деревья и Б+деревья обычно используются при программировании баз данных. Последняя программа, описанная в этой главе, использует Б+дерево для реализации простой, но достаточно мощной базы данных.

Сбалансированность дерева

Как упоминалось в 6 главе, форма упорядоченного дерева зависит от порядка вставки в него новых узлов. На рис. 7.1 показано два различных дерева, созданных при добавлении одних и тех же элементов в разном порядке.

Высокие и тонкие деревья, такие как левое дерево на рис. 7.1, могут иметь глубину порядка O(N). Вставка или поиск элемента в таком несбалансированном дереве может занимать порядка O(N) шагов. Даже если новые элементы вставляются в дерево в случайном порядке, в среднем они дадут дерево с глубиной N / 2, что также порядка O(N).

Предположим, что строится упорядоченное двоичное дерево, содержащее 1000 узлов. Если дерево сбалансировано, то высота дерева будет порядка log2(1000), или примерно равна 10. Вставка нового элемента в дерево займет всего 10 шагов. Если дерево высокое и тонкое, оно может иметь высоту 1000. В этом случае, вставка элемента в конец дерева займет 1000 шагов.

======155

@Рис. 7.1. Деревья, построенные в различном порядке

Предположим теперь, что мы хотим добавить к дереву еще 1000 узлов. Если дерево остается сбалансированным, то все 1000 узлов поместятся на следующем уровне дерева. При этом для вставки новых элементов потребуется около 10 * 1000 = 10.000 шагов. Если дерево было не сбалансировано и остается таким в процессе роста, то при вставке каждого нового элемента оно будет становиться все выше. Вставка элементов при этом потребует порядка 1000 + 1001 + … +2000 = 1,5 миллиона шагов.

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

АВЛ‑деревья

АВЛ‑деревья (AVL trees) были названы в честь русских математиков Адельсона‑Вельского и Лэндиса, которые их изобрели. Для каждого узла АВЛ‑дерева, высота левого и правого поддеревьев отличается не больше, чем на единицу. На рис. 7.2 показано несколько АВЛ‑деревьев.

Хотя АВЛ‑дерево может быть несколько выше, чем полное дерево с тем же числом узлов, оно также имеет высоту порядка O(log(N)). Это означает, что поиск узла в АВЛ‑дереве занимает время порядка O(log(N)), что достаточно быстро. Не столь очевидно, что можно вставить или удалить элемент из АВЛ‑дерева за время порядка O(log(N)), сохраняя при этом порядок дерева.

======156

@Рис. 7.2. АВЛ‑деревья

Процедура, которая вставляет в дерево новый узел, рекурсивно спускается вниз по дереву, чтобы найти местоположение узла. После вставки элемента, происходят возвраты из рекурсивных вызовов процедуры и обратный проход вверх по дереву. При каждом возврате из процедуры, она проверяет, сохраняется ли все еще свойство АВЛ‑деревьев на верхнем уровне. Этот тип обратной рекурсии, когда процедура выполняет важные действия при выходе из цепочки рекурсивных вызовов, называется восходящей (bottom‑up) рекурсией.

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

Например, дерево слева на рис. 7.3 является сбалансированным АВЛ‑деревом. Если добавить к дереву новый узел E, то получится среднее дерево на рисунке. Затем выполняется проход вверх по дереву от нового узла E. В самом узле E дерево сбалансировано, так как оба его поддерева пустые и имеют одинаковую высоту 0.

В узле D дерево также сбалансировано, так как его левое поддерево пустое, и имеет поэтому высоту 0. Правое поддерево содержит единственный узел E, и поэтому его высота равна 1. Высоты поддеревьев отличаются не больше, чем на единицу, поэтому дерево сбалансировано в узле D.

В узле C дерево уже не сбалансировано. Левое поддерево узла C имеет высоту 0, а правое — высоту 2. Эти поддеревья можно сбалансировать, как показано на рис. 7.3 справа, при этом узел C заменяется узлом D. Теперь поддерево с корнем в узле D содержит узлы C, D и E, и имеет высоту 2. Заметьте, что высота поддерева с корнем в узле C, которое ранее находилось в этом месте, также была равна 2 до вставки нового узла. Так как высота поддерева не изменилась, то дерево также окажется сбалансированным во всех узлах выше D.

Вращения АВЛ‑деревьев

При вставке узла в АВЛ‑дерево, в зависимости от того, в какую часть дерева добавляется узел, существует четыре варианта балансировки. Эти способы называются правым и левым вращением, и вращением влево‑вправо и вправо‑влево, и обозначаются R, L, LR и RL.

Предположим, что в АВЛ‑дерево вставляется новый узел, и теперь дерево становится несбалансированным в узле X, как показано на рис. 7.4. На рисунке изображены только узел X и два его дочерних узла, а остальные части дерева обозначены треугольниками, так как их не требуется рассматривать подробно.

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

Правое вращение

Вначале предположим, что новый узел вставляется в поддерево R на рис. 7.4. В этом случае не нужно изменять два правых поддерева узла X, поэтому их можно объединить, изобразив одним треугольником, как показано на рис. 7.5. Новый узел вставляется в дерево T1, при этом поддерево TA с корнем в узле A становится не менее, чем на два уровня выше, чем поддерево T3.

На самом деле, поскольку до вставки нового узла дерево было АВЛ‑деревом, то TA должно было быть выше поддерева T3 не больше, чем на один уровень. После вставки одного узла TA должно быть выше поддерева T3 ровно на два уровня.

Также известно, что поддерево T1 выше поддерева T2 не больше, чем на один уровень. Иначе узел X не был бы самым нижним узлом с несбалансированными поддеревьями. Если бы T1 было на два уровня выше, чем T2, то дерево было бы несбалансированным в узле A.

@Рис. 7.4. Анализ несбалансированного АВЛ‑дерева

========158

@Рис. 7.5. Вставка нового узла в поддерево R

В этом случае, можно переупорядочить узлы при помощи правого вращения (right rotation), как показано на рис. 7.6. Это вращение называется правым, так как узлы A и X как бы вращаются вправо.

Заметим, что это вращение сохраняет порядок «меньше» расположения узлов дерева. При симметричном обходе любого из таких деревьев обращение ко всем поддеревьям и узлам дерева происходит в порядке T1, A, T2, X, T3. Поскольку симметричный обход обоих деревьев происходит одинаково, то и порядок расположения элементов в них будет одинаковым.

Важно также заметить, что высота поддерева, с которым мы работаем, остается неизменной. Перед тем, как был вставлен новый узел, высота поддерева была равна высоте поддерева T2 плюс 2. После вставки узла и выполнения правого вращения, высота поддерева также остается равной высоте поддерева T2 плюс 2. Все части дерева, лежащие ниже узла X при этом также остаются сбалансированными, поэтому не требуется продолжать балансировку дерева дальше.

Левое вращение

Левое вращение (left rotation) выполняется аналогично правому. Оно используется, если новый узел вставляется в поддерево L, показанное на рис. 7.4. На рис. 7.7 показано АВЛ‑дерево до и после левого вращения.

@Рис. 7.6. Правое вращение

========159

@Рис. 7.7. До и после левого вращения

Вращение влево‑вправо

Если узел вставляется в поддерево LR, показанное на рис. 7.4, нужно рассмотреть еще один нижележащий уровень. На рис. 7.8. показано дерево, в котором новый узел вставляется в левую часть T2 поддерева LR. Так же легко можно вставить узел в правое поддерево T3. В обоих случаях, поддеревья TA и TC останутся АВЛ‑поддеревьями, но поддерево TX уже не будет таковым.

Страницы: 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