Разработка и реализация алгоритма создания и балансировки двоичного дерева поиска со взвешенными узлами

Цель работы
Разработка структуры:
-минимальные затраты памяти;
-быстрый поиск;
-приоритезированный доступ.
Реализация структуры.
Анализ эффективности.
Визуализация.

Балансировка двоичных деревьев поиска
По высоте
По весу
По количеству узлов

Декартово дерево (Treap)
Декартово дерево - хранит пары (X,Y) в виде бинарного дерева таким образом, что оно является деревом поиска по X и кучей по Y.

Структура данных TKOL
Разработанная структура, названная TKOL – двоичное дерево поиска, балансируемое по весу.
Малое вращение
А) Структура дерева до вращения
Б) Структура дерева после вращения
Критерий вращения:
,
где Pi – вес i-го узла или поддерева.

Теоретический анализ
Количество переходов по дереву до случайного элемента составляет
,
где:
- вес левого поддерева;
- вес всего дерева;
- количество узлов в левом поддереве;
- суммарное количество узлов дерева.

Теоретический анализ

Средневзвешенный путь
,
где Pi — собственный вес узла;
d — длина пути от корня до узла, увеличенная на единицу.

Сравнение эффективности структуры TKOL и несбалансированного BST