Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Основные определения
|
|
Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале дерево является разумно сбалансированным и имеет высоту порядка 
. Однако при некоторых данных дерево может быть вырожденным. Тогда его высота будет O (n), и доступ к данным существенно замедлится.
Дерево является сбалансированным тогда, и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 (не путать с идеально сбалансированными деревьями, когда для каждого узла дерева количество узлов в левом и правом поддеревьях отличается не более чем на 1).
Сбалансированные деревья еще называют AVL -деревьями (по фамилиям изобретателей: Адельсон-Вельский, Ландис).
Бинарное дерево поиска 
| AVL -дерево 
|
3.5.2. Узлы AVL -дерева
AVL -деревья имеют представление, похожее на бинарные деревья поиска. Все операции идентичны, за исключением операций вставки и удаления из дерева.
Для сохранения информации об соотношении высот левого и правого поддеревьев в определение типа узла включается поле - показатель сбалансированности, которое содержит разность высот правого и левого поддеревьев:
struct AVLTREE{
int dann;
int balance;
TREE *pleft;
TREE *pright; };
Если balance ==-1, то узел «перевешивает влево», т.к. высота левого поддерева больше, чем высота правого поддерева. При положительном balance узел «перевешивает вправо». Сбалансированный по высоте узел имеет balance ==0. В AVL -дереве показатель сбалансированности должен быть в диапазоне [-1, 1].
|
|