Web avltree.narod.ru
Email avltree@narod.ru

Сбалансированные деревья

Java апплет, иллюстрирующий операции с бинарными поисковыми и сбалансированными (АВЛ) деревьями.

Открыть Java апплет в отдельном окне

Возможности этого Java апплета:

Компактная упаковка вершин дерева по ширине.
Автоматическая подгонка размера вершин дерева к их содержимому (попробуйте ввести, например, трехзначное число).
Два режима для дерева: сбалансированное (AVL) и простое бинарное поисковое (BST).
Изменение размеров апплета (используйте кнопку выше, чтобы открыть его в отдельном окне).
Пустое поле ввода означает случайную генерацию ключа в диапазоне 0..99.
Перемещение дерева нажатой клавишей мыши.

Теория.

По определению дерево является сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

Это определение дали В 1962 г. советские математики Адельсон-Вельский и Ландис. Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).

Операции, выполняемые над сбалансированным деревом:

1) вставить новый элемент;

2) удалить заданный элемент;

3) поиск заданного элемента.

При использовании деревьев, соответствующих этому определению, обеспечивается простая процедура балансировки притом, что средняя длина поиска составляет O(log n), т.е. практически не отличается от длины поиска в идеально сбалансированных деревьях. Как доказали Адельсон-Вельский и Ландис, АВЛ-дерево никогда не превышает по глубине аналогичное сбалансированное дерево больше, чем на 45%.

Литература по сбалансированным (АВЛ) деревьям.

Сайт управляется системой uCoz