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

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

Файл:Matr tree.png

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

Матричное дерево (англ. matrix tree) – это одно из самобалансирующихся двоичных деревьев поиска, обеспечивающих логарифмический рост высоты дерева от числа узлов.

Матричное дерево состоит из корневого указателя, четного и нечетного поддеревьев, каждое из которых в свою очередь состоит из левого и правого двоичных поддеревьев.

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

Узлы располагаются на уровнях и в позициях, определенных численным значением ключа, в связи с этим вставка и удаление узлов производятся без вращения левого и правого двоичных поддеревьев ^[1].

Свойства

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

для четного поддерева

n = 2^x * z (в случае нумерации ключей, начиная с 1) n + 2 = 2^x * z (в случае нумерации ключей, начиная с 0),

где n – ключ узла, х - уровень, на котором расположен узел, z - сомножитель

для нечетного поддерева

n + 1 = 2^x * z

2. Позиция узла на уровне равна y = (z + 1) / 2

3. Количество узлов, расположенных под общей вершиной, равно k = 2^m, где m – разность по модулю уровней узлов и общей вершины.

4. Позиция последнего узла на уровне, расположенного под общей вершиной, равна y_{i + k − 1} = y_vershiny * 2^m

5. Ключ общей вершины равен среднему арифметическому ключей первого и последнего узлов, расположенных под общей вершиной n_vershiny = (n_i + n_{i + k − 1}) / 2

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

Работа с матричными деревьями

Алгоритм добавления или удаления узла из состава матричного дерева основан на определении общей вершины для добавляемого (удаляемого) узла и ранее включенного (сохраняемого) узла.

Добавление нового узла начинается с определения характеристики четности/нечетности ключа, уровня и позиции узла в соответствии со свойствами 1 и 2 матричного дерева. После этого в составе четного или нечетного поддерева производится поиск соседнего, ранее включенного узла.

В соответствии со свойствами 3, 4, 5 и 6 матричного дерева определяется общая вершина для нового и соседнего узлов. Если общая вершина совпадает с одним из ранее включенных узлов новый узел присоединяется к нему. В противном случае в состав матричного дерева включается дополнительный узел, являющийся общей вершиной для нового и соседнего узлов.

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

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

Сравнение с другими сбалансированными деревьями

Высота дерева

Степень сбалансированности матричного дерева зависит от вида последовательности, в которой ключи находились перед добавлением в дерево. При возрастающей/убывающей ключей последовательности с шагом, равным 1, сбалансированность матричного дерева достигает уровня сбалансированности АВЛ-дерева. При случайной последовательности ключей сбалансированность матричного дерева соответствует уровню сбалансированности красно-черного дерева. При возрастающей/убывающей последовательности ключей вида 2ⁿ матричное дерево вырождается в линейный список.

Поиск

Эффективность поиска в матричном дереве зависит от распределения характеристики четности/нечетности ключей. При равномерном распределении характеристики поиск производится в половине от общего числа узлов за время O(logn / 2), что является лучшим показателем среди всех сбалансированных деревьев. В случае одностороннего распределения характеристики поиск производится в общем числе узлов за время O(logn). Корневой указатель не влияет на сравнительную эффективность поиска в матричном дереве, поскольку входит в состав любого сбалансированного дерева.

Вставка

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

Удаление

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

Память

Узел матричного дерева не содержит дополнительной информации в отличие от узлов АВЛ-дерева (разность высот двоичных поддеревьев) и красно-черного дерева (цвет узла).

Литература

А.Е.Васильев. Матричные деревья поиска // Естественные и технические науки. ISSN 1684-2626. 2010. № 1(45). С.31-37

См. также

Сбалансированные (самобалансирующиеся) деревья:

• АВЛ-дерево
• Красно-черное дерево
• Идеально сбалансированное дерево
• Расширяющееся дерево

Ссылки

• Алгоритм построения матричных деревьев

Источники

1. ↑ Структура поиска метаданных базы данных