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

Сентябрь 4, 2022

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

Содержание

2. Цель работы Разработка структуры: -минимальные затраты памяти; -быстрый поиск; -приоритезированный доступ. Реализация структуры. Анализ эффективности. Визуализация.
3. Балансировка двоичных деревьев поиска По высоте По весу По количеству узлов
4. Декартово дерево (Treap) Декартово дерево - хранит пары (X,Y) в виде бинарного дерева таким образом, что
5. Структура данных TKOL Разработанная структура, названная TKOL – двоичное дерево поиска, балансируемое по весу. Малое вращение
6. Теоретический анализ Количество переходов по дереву до случайного элемента составляет , где: - вес левого поддерева;
7. Теоретический анализ
8. Средневзвешенный путь , где Pi — собственный вес узла; d — длина пути от корня до
9. Сравнение эффективности структуры TKOL и несбалансированного BST
11. Скачать презентацию

Слайд 2

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

Слайд 3

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

Слайд 4

Декартово дерево (Treap)
Декартово дерево - хранит пары (X,Y) в виде бинарного

дерева таким образом, что оно является деревом поиска по X и кучей по Y.

Слайд 5

Структура данных TKOL
Разработанная структура, названная TKOL – двоичное дерево поиска, балансируемое

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

Слайд 6

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

вес левого поддерева;
- вес всего дерева;
- количество узлов в левом поддереве;
- суммарное количество узлов дерева.

Слайд 7

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

Слайд 8

Средневзвешенный путь

,
где Pi — собственный вес узла;
d — длина пути

от корня до узла, увеличенная на единицу.

Слайд 9

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