Главная » Java, Структуры данных и алгоритмы » (а,Ь)-деревья

0

Для уменьшения воздействий различия времени доступа к внутренней и внешней памяти при поиске представим словарь с помощью многопроходного поискового дерева (раздел 9.3). При этом перейдем от структуры (2,4)-дерева к более универсальной структуре, известной как (я,6)-деревЬ.

Такое (я,6)-дерево представляет собой многопроходное поисковое дерево, в котором каждый узел имеет от а до b дочерних элементов и хранит от а-1 до b-1 объектов. Алгоритмы поиска, ввода и удаления элементов в (я,6)-дереве получим непосредственной модификацией соответствующих алгоритмов (2,4)-дерева. Преимущество (я,6)-дерева состоит в гибкой поисковой структуре, где размер узлов й время выполнения различных словарных операций зависит от параметров aw Ь. При соответствую^ щей установке этих параметров с учетом размеров дисковых блоков \ можно создать структуру данных и добиться с ее помощью наилучшей производительности при работе с внешней памятью.

(а,Ь)-дерево, в котором а и b — целые числа, причем 2 < а < (Ь + 1)/2, является многопроходным поисковым деревом Г со следующими ограничениями:

•          свойство размера: каждый составной узел имеет как минимум а дочерних элементов, если он не является корнем, и максимум b дочерних элементов;

•     свойство глубины: все простые узлы имеют одинаковую глубину.

Утверждение 9.8. Высота (а,Ь)-дерева, хранящего п объектов, составляет Щlog п / log b) и 0(log п / log а).

Согласно свойствам размера и глубины, количество простых узлов п" дерева Г составляет минимум 2аи~1 и максимум bh. Согласно утверждению 9.3, п" = п + 1. Таким образом,

Таблица 9.5. Временные характеристики методов словаря, реализованного (a,b)-j\z- ревом. Показаны только основные методы. Количество элементов в словаре обозначено и, занимаемое место составляет 0(п)

Временные характеристики, приведенные в табл. 9.5, основываются на следующем:

[1] (я,6)-дерево Г, реализованное с помощью структуры данных, описанной в разделе 9.3, и вторичная структура данных узла дерева Т поддерживают поиск за/(b) времени и операции деления и слияния за g(b) времени, где f(b) и g(b) — некоторые функции, при этом затраты времени сводятся к 0(1), учитывая только дисковые передачи;

•          высота (я,6)-дерева, хранящего п элементов, равна 0(log п)/(log а), согласно утверждению 9.8;

•          операция поиска обращается к 0(log п)/(log а) узлам на пути от корня до простого узла и занимает f(b) времени на каждый узел;

•                      передача занимает f(b) времени;

•          операция деления или слияния занимает g(b) времени и создает для вновь полученных узлов вторичную структуру размером 0(b);

•          операция ввода или удаления элемента обращается к 0(log n)/(log а) узлам на пути от корня до простого узла и занимает g(b) времени на каждый узел.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии