Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Сбалансированные деревья. Основные определения и операции
Количество сравнений при поиске по бинарному дереву поиска колеблется от 
до n/2 в худшем. Хотелось бы иметь алгоритм эффективного поиска, вставки и удаления элементов, который сохранял бы дерево в некотором сбалансированном состоянии.
Глубина бинарного дерева – максимальный уровень его листьев.
Баланс некоторого узла – высота его левого поддерева минус высота его правого поддерева.
Сбалансированное бинарное дерево – у которого абсолютное значение баланса каждого узла меньше или равно 1 (допустимый баланс (-1), 0, 1).
Дано некоторое сбалансированное дерево. Необходимо добавить новый элемент. В результате дерево либо сбалансированное, либо не сбалансированное (если вставляемый узел является левым потомком некоторого узла, которое ранее имело баланс =1, либо правым потомком некоторого узла, баланс которого был =(-1)). Если после включения элемента баланс был нарушен, нужно найти самый нижний разбалансированный узел.
Повороты.
Алгоритм «Левый поворот».
1. Work2=Work1→PRP
2. Work1→PRP= Work2→PLP
3. Work2→PLP= Work1
 |  |
При любом повороте значение указателя на корень поддерева так же должно изменяться, чтобы указывать на новый корень (указатель Work2). При любом из поворотов дерево остается бинарным деревом поиска. Следовательно для получения сбалансированного дерева можно выполнять любое число левых или правых поворотов.
При левом повороте: указатель Work1(вершина 20), Work2 (вершина 30).
 |
Рассмотрим поддерево, имеющее корень в самом младшем предке, которое стал не сбалансированным в результате добавления некоторого узла. Пусть баланс поддерева до добавления был равен 1 (для (-1) тот же алгоритм, все симметрично.)
Узел А – не сбалансированный узел. Т.к. баланс этого узла был =1, то его левое поддерево не пусто. Узел В - левый потомок. Т.к. узел А является самым младшим предком, который стал не сбалансированным, то узел В должен иметь баланс =0. Узел В должен иметь до вставки левое и правое поддеревья равной высоты n (возможно поддеревья пустые).Т.к. баланс узла А был равен 1, то правое поддерево A(D3) имеет высоту n.
Рассмотрим два случая.
 |
Случай 1. Добавляемый узел вставляем в левое поддерево узла В(рис.1), изменяя баланс узла В на 1, а узла А на 2. Для дерева на рис.1 выполним правый поворот. Дерево на рис.2 –дерево бинарного поиска, сбалансированное.
 |
Случай 2. Дерево на рис.1. Добавляемый узел вставляем в правое поддерево узла В. Пусть узел С будет потомком узла В. Имеется 3 варианта: узел С является вставляемым узлом (тогда у него левое и правое поддерево пустое); когда добавляемый узел включается в левое или правое поддерево узла С.
 |  | ||
Для балансировки дерева на рис.3 необходимы 2 поворота: левый поворот поддерева с корнем в узле В и правый поворот поддерева с корнем в узле А.
Алгоритм вставки с балансировкой.
Каждый узел дерева должен иметь четыре поля: информационное, два указателя на левое и правое поддерево, поле показателя сбалансированности вершины. Процесс добавления вершины:
1. пройти по пути дерева поиска и убедиться, что ключа в дереве нет;
2. включить новую вершину:
3. отступая по пути поиска проверять в каждой вершине показатель сбалансированности, если необходимо, то выполнить балансировку.
 |  | ||
Пример. Вставляем вершину 75. Вершины, входящие в путь поиска:100, 50, 70, 80.
Алгоритм исключение элемента из сбалансированного дерева.
1. Поиск удаляемого элемента
2. Исключение элемента
3. Балансировка.
Если включение одного ключа может привести самое большее к одному повороту (разбалансирована 0 или 1 вершина), то исключение может потребовать балансировки во всех вершинах вдоль пути поиска.
| Название поворота | Баланс вершины А | Баланс вершины В | Рисунок |
| LL | 1 или 0 | ||
| RR | -2 | -1 или 0 | |
| LR | -1 | ||
| RL | -2 |
Date: 2015-09-05; view: 445; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |