Cтраница 4
Хорошим способом производить такие локальные изменения являются вращения, обсуждаемые в разд. Эти результаты также означают, что если файл статический и если все записи требуют одинакового объема памяти, то последовательно распределенная таблица обладает весьма подходящими свойствами: она может быть построена сортировкой ( 0 ( п log л) - операция); не требует расхода памяти на указатели; допускает бинарный поиск, соответствующий полному бинарному дереву, которое почти так же хорошо, как оптимальное дерево для большинства практических случаев. [46]
На рис. 18.13 внизу показана обработка строк от коротких к длинным. Разница между этими двумя слияниями не столь значительна, как между первым сбалансированным слиянием и оптимальным деревом. Возможности оптимального слияния показаны на рис. 18.14. При десяти строках в оптимальном дереве перемещений данных на 15 процентов меньше, чем в сбалансированном. Таким образом, на последнем просмотре необходимо сохранить максимальную степень - это решающий фактор в использовании преимущества длины строк. [47]
Наконец, рассмотрим те деревья решений, которые используют монету 0 в корне. Для первого сравнения набор исходов будет ( 1 7, 1), в связи с чем все алгоритмы, начинающиеся таким способом, для нас непригодны; набор же исходов ( 3, 3, 3) приводит к оптимальному дереву, показанному на рис. 1.6. Аналогичным образом устанавливается, что для оптимального дерева сравнения в первом от корня ярусе определяются единственным образом. Отсюда мы заключаем, что для задачи о четырех монетах фактически существует только одно оптимальное дерево. [48]
При любом методе, основанном на приближении оптимального дерева, размер всех строк должен быть известен. Недавно Фрэйзер и Уонг предложили увеличивать размер строк, используя дисковую память и расширение выбора с замещением. Смысл такого увеличения строк состоит в том, что программа может преднамеренно строить наборы строк разной длины. Возможность управлять изменением размера строк может, следовательно, обеспечить оптимизацию времени слияния за счет более эффективного построения оптимального дерева. Если строятся строки определенного размера, то их можно распределять оптимальным путем, а именно, так, чтобы короткие строки были доступны прежде всего. [49]
На практике не всегда все так удачно складывается. Например, если есть только 14 записей, то высота одной из ветвей будет равна трем. Другими словами, допускаются только две длины ветви. Оптимальное дерево требует много усилий для построения и - ведения. [50]
Один из способов ответить н а этот вопрос - провести эксперименты на ЭВМ, при которых порождается много последовательностей весов, строить деревья в соответствии с разными алгоритмами и собирать статистические данные о результатах. В некоторых исследованиях такого рода, опубликованных в печати, утверждается, что при эвристических алгоритмах, основанных на объединении принципов сбалансированных деревьев и монотонных деревьев, среднее время поиска отличается лишь на несколько процентов от оптимального. Имеет смысл дать интуитивное объяснение этого явления, поскольку оно возникает во многих комбинаторных задачах. Представим себе пространство всех деревьев, построенных по данной последовательности весов и рассмотрим взвешенную длину пути как функцию деревьев этого пространства. Следовательно, легко найти хорошее дерево, но трудно найти оптимальное, поскольку оптимальное дерево мало отличается от других близких деревьев в его окрестности. [51]
В некоторой древовидной структуре опытным путем измеряется частота обращения к каждому из элементов. Для втого с любым из элементов связан счетчик обращений. По прошествии определенного времени дерево реорганизуется, для этого оно просматривается и с помощью программы 4.4 строится новое дерево, в которое ключи включаются в порядке убывания счетчиков частот обращения. Напишите программы, выполняющие такую реорганизацию. Будет ли средняя длина пути в новом дереве равна, больше или даже значительно больше длины пути в оптимальном дереве. [52]