2010/09/15 13:06:54

Матричное дерево

Матричное дерево - структура поиска данных, самобалансирующееся двоичное дерево с удвоенной скоростью поиска

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

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

Кроме ключа, каждый элемент содержит некоторое информационное значение, сопоставленное ключу и фактически являющееся предметом поиска, а также левый и правый указатели на элементы-потомки. Для упрощения алгоритмов операций над двоичным деревом в состав элемента может дополнительно включаться указатель на элемент-предок.

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

Такое упорядоченное расположение ключей в двоичном дереве позволяет осуществлять их эффективный поиск. Время поиска определяется количеством шагов от корня до элемента с искомым ключом и описывается логарифмической зависимостью O (log n), где n – число вершин двоичного дерева.28 мая министр цифрового развития Максут Шадаев выступит на TAdviser SummIT 8.5 т В целях сохранения эффективности поиска в процессе изменения состава элементов в двоичном дереве необходимо поддерживать сбалансированность левого и правого поддеревьев так, чтобы их высоты (количество вершин) не отличались между собой более чем на единицу.

Балансировка двоичного дерева производится перестановкой элементов в его составе. Время перестановки элементов определяется высотой двоичного дерева.

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

Для сокращения времени перестановки элементов двоичного дерева условие его сбалансированности смягчают так, чтобы высоты левого и правого поддеревьев могли отличаться между собой не более, чем в два раза. При этом время поиска сохраняется на уровне O (log n).

Известны два вида так называемых самобалансирующихся двоичных деревьев, удовлетворяющих этому условию:

АВЛ-дерево, предложенное Г.М.Адельсоном-Вельским и Е.М.Ландисом [1];
красно-черное дерево, предложенное Р.Бауером [2].

Для реализации алгоритмов балансировки в состав элементов этих деревьев введены дополнительные показатели: разность высот левого и правого поддеревьев (АВЛ-дерево) и цвет элемента (красно-черное дерево).

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

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

Кроме того, матричное дерево разделяется в корневом указателе на четное и нечетное поддеревья, каждое из которых состоит из элементов, связанных в виде двоичного дерева поиска. Четное поддерево включает элементы с четными ключами, нечетное – элементы с нечетными ключами. Каждый элемент матричного дерева содержит ключ, информационное значение, правый и левый указатели на элементы-потомки.

Уровни матричного дерева номеруются от листьев к корню, позиции элементов на одном уровне номеруются слева направо. Ключ элемента nxy имеет индексы x и y, где x – уровень элемента относительно листьев дерева и y – позиция элемента относительно первого элемента на уровне.

Матричное дерево обладает следующими характерными свойствами.

1. Ключ каждого элемента можно разложить на два сомножителя

для четного поддерева
n = 2x * z в случае начала номерации ключей с 1
n + 2 = 2x * z в случае начала номерации ключей с 0
где n – ключ элемента, х - уровень, на котором расположен элемент, z - сомножитель
для нечетного поддерева
n + 1 = 2x * z

2. Позиция элемента на уровне равна

y = (z + 1)/2

3. Количество элементов, расположенных под общей вершиной, равно

k = 2m , где m – разность по модулю уровней элементов и общей

вершины

4. Позиция последнего элемента на уровне, расположенного под общей вершиной, равна

yi+k-1 = yвершины * 2m

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

nвершины = (ni + ni+k-1)/2

6. Если первый элемент имеет общую вершину со вторым элементом, то эта вершина является вышележащей общей вершиной для общей вершины второго элемента с третьим элементом.

Степень сбалансированности матричного дерева зависит от вида последовательности, в которой были отсортированы ключи перед добавлением элементов в матричное дерево.

Способ балансировки матричного дерева показан на примере добавления/удаления элементов со случайной последовательностью ключей.

Алгоритм добавления/удаления элементов из состава матричного дерева основан на определении общей вершины для двух элементов – добавляемого/удаляемого элемента и ранее включенного/сохраняемого элемента. Вычислительная сложность алгоритма определяется количеством элементов, участвующих в перестановках, в число которых входят:

- элемент, ранее включенный или сохраняющийся в дереве;
- элемент, добавляемый или удаляемый из дерева;
- элемент, являющийся общей вершиной для первых двух элементов и также добавляемый/удаляемый из дерева;
- элемент, ранее включенный или сохраняющийся в дереве, к которому присоединяется или от которого отсоединяется общая вершина.

Алгоритм добавления/удаления элементов из состава матричного дерева состоит из следующих действий.

Этап 1.

Пусть первый элемент в рассматриваемом примере имеет ключ 24. В дальнейшем этот элемент будем обозначать «24».

Определяем уровень и позицию элемента «24»:

24 = 23 * 3, где
уровень – 3, степень основания 2
позиция – 2, частное от деления (3+1)/2

В связи с отсутствием других элементов элемент «24» включается в четное поддерево в качестве корня. Адрес элемента записывается в корневой указатель.

Этап 2.

Второй элемент имеет ключ 6. Определяем уровень и позицию элемента «6»:

6 = 21 * 3, где
уровень – 1, степень основания 2
позиция – 2, частное от деления (3+1)/2

Проверяем элемент «24» на соответствие критериям общей вершины для элемента «6». Разность по модулю уровней элементов «24» и «6» равна 2. В случае, если элемент «24» является общей вершиной, количество элементов под ним на уровне 1 равно основанию 2, возведенному в степень, равную разнице уровней: 4 = 22

Позиция последнего элемента под общей вершиной на уровне 1 равна позиции элемента «24», умноженной на основание 2 в степени, равной разнице уровней: 8 = 2 * 22

Позиция первого элемента под общей вершиной равна позиции последнего элемента, уменьшенной на количество элементов под общей вершиной и увеличенной на 1: 5 = 8 – 4 + 1

Позиция элемента «6», равная 2, не входит в интервал позиций элементов от 5 до 8, для которых элемент «24» является общей вершиной. В связи с этим продолжаем поиск общей вершины для элементов «6» и «24».

Расширяем интервал позиций элементов, в состав которого входит позиция элемента «24», в направлении элемента «6». Расширение производится пошагово путем удваивания количества элементов в интервале.

На первом шаге количество элементов в интервале увеличивается до 8. Позиция первого элемента в этом интервале равна: 1 = 8 – 8 + 1

Следовательно, позиция элемента «6» входит в этот интервал.

Определяем ключи первого и последнего элементов в этом интервале

Ключ первого элемента: 2 = 21 * (2*1 - 1)

Ключ последнего элемента: 30 = 21 * (2*8 - 1)

Ключ общей вершины равен среднему арифметическому ключей первого и последнего элементов в интервале: 16 = (2 + 30)/2

Элемент «16» становится корнем четного поддерева, к которому крепятся листья «6» и «24». В корневом указателе соответственно изменяется адрес корня четного поддерева.

Этап 3.

Третий элемент имеет ключ 12.

Определяем уровень и позицию элемента «12»:

12 = 22 * 3
уровень – 2, степень основания 2
позиция – 2, частное от деления (3+1)/2

Осуществляем поиск в дереве элемента, с которым может быть связан элемент «12».

Таким элементом является «6».

Разность уровней этих элементов по модулю равна 1. При этом элемент «12» находится на более высоком уровне.

Количество элементов, для которых элемент «12» является общей вершиной, на уровне 1 равно двум. Интервал их позиций – 3 и 4. Позиция элемента «6» не входит в этот интервал.

Расширяем интервал в сторону элемента «6» путем удваивания количества элементов.

Новый интервал состоит из элементов с позициями от 1 до 4.

Ключи первого и последнего элементов интервала равны соответственно 2 и 14. Ключ общей вершины равен 8.

Элементы «6» и «12» связываются с общей вершиной «8», которая в свою очередь связывается с корнем «16».

Этап 4.

Четвертый элемент имеет ключ 2.

Определяем уровень и позицию элемента «2»: 2 = 21 * 1

уровень – 1, степень основания 2
позиция – 1, частное от деления (1+1)/2

Осуществляем поиск в дереве элемента, с которым может быть связан элемент «2».

Таким элементом является «6».

Разность уровней этих элементов по модулю равна 0.

В связи с этим начинаем расширять интервал позиций элементов, находящихся на уровне 1, в направлении слева направо.

Расширение интервала осуществляется с самой первой позиции элементов, расположенных на данном уровне, пошагово с удвоением количества позиций на каждом шаге.

На первом шаге количество позиций элементов удваивается с 1 до 2.

На каждом шаге полученный интервал проверяется на вхождение элемента «2».

Элемент «2» входит в интервал, полученный на первом шаге.

В связи с этим начинаем расширять интервал в направлении справа налево.

Расширение интервала начинается с самой последней позиции ранее рассчитанного интервала пошагово с удвоением количества позиций элементов на каждом шаге.

На первом шаге первоначальное количество позиций элементов удваивается с 1 до 2. На каждом шаге полученный интервал проверяется на вхождение элемента «2».

Элемент «2» входит в интервал, полученный на первом шаге.

Первый элемент первого интервала имеет позицию 1, последний элемент второго интервала имеет позицию 2. Ключи элементов равны соответственно 2 и 6. Следовательно, ключ общей вершины равен 4. Элементы «2» и «6» связываются с общей вершиной «4», которая в свою очередь связывается с вершиной «8».

Удаление элементов из состава матричного дерева осуществляется в обратном порядке.

Анализ структуры и способа балансировки матричного дерева позволяет сделать выводы об эффективности его применения по сравнению с АВЛ-деревом или красно-черным деревом.

1. Время поиска в матричном дереве определяется видом последовательности, в которой были отсортированы ключи элементов перед добавлением их в состав дерева.

При случайной последовательности поиск производится в половине от общего числа элементов. Время поиска составляет O (log n/2) [3], где n/2 – количество элементов, ключи которых совпадают с ключом поиска по значению характеристики четности/нечетности.

При включении в состав случайной последовательности ключей с одинаковой характеристикой четности/нечетности поиск производится в общем числе элементов. Время поиска составляет O(log n). При возрастающей/убывающей последовательности вида 2n четное и нечетное поддеревья вырождаются в линейные списки элементов с временем поиска O (n).

2. Количество элементов матричного дерева, участвующих в перестановках при добавлении или удалении элементов, не превышает четырех. Соответственно, время выполнения этих операций для матричного дерева не превышает O (log 4).

3. Полный обход всех элементов или поиск элемента с наименьшим/наибольшим ключом в матричном дереве осуществляется за время O (log n) из-за необходимости повторять эти операции в четном и нечетном поддеревьях.

4. Матричное дерево занимает меньший объем памяти вычислительной установки из-за отсутствия в составе элементов дополнительных показателей разности высот левого и правого поддеревьев или цвета элемента.

Указанные выводы позволяют определить область применения матричных деревьев – во всех случаях рекомендованного использования самобалансирующихся двоичных деревьев поиска, за исключением деревьев, элементы которых содержат ключи, отсортированные в возрастающей/убывающей последовательности вида 2n.