Слайд 2Цель работы
Разработка структуры:
-минимальные затраты памяти;
-быстрый поиск;
-приоритезированный доступ.
Реализация структуры.
Анализ эффективности.
Визуализация.
![Цель работы Разработка структуры: -минимальные затраты памяти; -быстрый поиск; -приоритезированный доступ. Реализация структуры. Анализ эффективности. Визуализация.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-1.jpg)
Слайд 3Балансировка двоичных деревьев поиска
По высоте
По весу
По количеству узлов
![Балансировка двоичных деревьев поиска По высоте По весу По количеству узлов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-2.jpg)
Слайд 4Декартово дерево (Treap)
Декартово дерево - хранит пары (X,Y) в виде бинарного дерева
![Декартово дерево (Treap) Декартово дерево - хранит пары (X,Y) в виде бинарного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-3.jpg)
таким образом, что оно является деревом поиска по X и кучей по Y.
Слайд 5Структура данных TKOL
Разработанная структура, названная TKOL – двоичное дерево поиска, балансируемое по
![Структура данных TKOL Разработанная структура, названная TKOL – двоичное дерево поиска, балансируемое](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-4.jpg)
весу.
Малое вращение
А) Структура дерева до вращения
Б) Структура дерева после вращения
Критерий вращения:
,
где Pi – вес i-го узла или поддерева.
Слайд 6Теоретический анализ
Количество переходов по дереву до случайного элемента составляет
,
где:
- вес
![Теоретический анализ Количество переходов по дереву до случайного элемента составляет , где:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-5.jpg)
левого поддерева;
- вес всего дерева;
- количество узлов в левом поддереве;
- суммарное количество узлов дерева.
Слайд 8Средневзвешенный путь
,
где Pi — собственный вес узла;
d — длина пути от
![Средневзвешенный путь , где Pi — собственный вес узла; d — длина](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-7.jpg)
корня до узла, увеличенная на единицу.
Слайд 9Сравнение эффективности структуры TKOL и несбалансированного BST
![Сравнение эффективности структуры TKOL и несбалансированного BST](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1157110/slide-8.jpg)