Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 37
Текст из файла (страница 37)
Чтобы добавить объект x, мы сравниваем его с входом вершины иопределяем, должны ли мы добавить x к левой или правой ветви, а добавив x к соответствующей ветви, мы соединяем результат с изначальным входом и второй ветвью.Если x равен входу, мы просто возвращаем вершину. Если нам требуется добавить x кпустому дереву, мы порождаем дерево, которое содержит x на входе и пустые левое иправое поддеревья. Вот процедура:(define (adjoin-set x set)(cond ((null? set) (make-tree x ’() ’()))((= x (entry set)) set)((< x (entry set))(make-tree (entry set)(adjoin-set x (left-branch set))(right-branch set)))((> x (entry set))(make-tree (entry set)(left-branch set)(adjoin-set x (right-branch set))))))39 Мы представляем множества при помощи деревьев, а деревья при помощи списков — получается абстракция данных на основе другой абстракции данных.
Процедуры entry, left-branch, right-branch иmake-tree мы можем рассматривать как способ изолировать абстракцию «бинарное дерево» от конкретногоспособа, которым мы желаем представить такое дерево в виде списковой структуры.Глава 2. Построение абстракций с помощью данных1601234567Рис. 2.17. Несбалансированное дерево, порожденное последовательным присоединениемэлементов от 1 до 7.Утверждение, что поиск в дереве можно осуществить за логарифмическоечисло шагов, основывается на предположении, что дерево «сбалансировано»,то есть что левое и правое его поддеревья содержат приблизительно одинаковоечислоэлементов,такчтокаждоеподдеревосодержитприблизительнополовину элементов своего родителя.
Но как нам добиться того, чтобы тедеревья, которые мы строим, были сбалансированы? Даже если мы начинаем сосбалансированного дерева, добавление элементов при помощи adjoin-set может датьнесбалансированный результат. Поскольку позиция нового добавляемого элемента зависит от того, как этот элемент соотносится с объектами, уже содержащимися вмножестве, мы имеем право ожидать, что если мы будем добавлять элементы «случайным образом», в среднем дерево будет получаться сбалансированным.Однако такой гарантии у нас нет.
Например, если мы начнем с пустогомножества и будем добавлять по очереди числа от 1 до 7, то получится весьманесбалансированное дерево, показанное на рисунке 2.17. В этом дереве вселевые поддеревья пусты, так что нет никакого преимущества по сравнению спростым упорядоченным списком. Одним из способов решения этой проблемы было быопределение операции, которая переводит произвольное дерево в сбалансированное с теми же элементами. Тогда мы сможем проводить преобразование через каждые несколькоопераций adjoin-set, чтобы поддерживать множество в сбалансированном виде.
Естьи другие способы решения этой задачи. Большая часть из них связана с разработкой новых структур данных, для которых и поиск, и вставка могут производиться за Θ(log n)шагов40 .40 Примерами таких структур могут служить B-деревья (B-trees) и красно-черные деревья (red-black trees).Существует обширная литература по структурам данных, посвященная этой задаче. См. Cormen, Leiserson,and Rivest 1990.2.3. Символьные данные161Упражнение 2.63.Каждая из следующих двух процедур преобразует дерево в список.(define (tree->list-1 tree)(if (null? tree)’()(append (tree->list-1 (left-branch tree))(cons (entry tree)(tree->list-1 (right-branch tree))))))(define (tree->list-2 tree)(define (copy-to-list tree result-list)(if (null? tree)result-list(copy-to-list (left-branch tree)(cons (entry tree)(copy-to-list (right-branch tree)result-list)))))(copy-to-list tree ’()))а.
Для всякого ли дерева эти процедуры дают одинаковый результат? Если нет, то как ихрезультаты различаются? Какой результат дают эти две процедуры для деревьев с рисунка 2.16?б. Одинаков ли порядок роста этих процедур по отношению к числу шагов, требуемых дляпреобразования сбалансированного дерева с n элементами в список? Если нет, которая из нихрастет медленнее?Упражнение 2.64.Следующая процедура list->tree преобразует упорядоченный список в сбалансированное бинарное дерево. Вспомогательная процедура partial-tree принимает в качестве аргументов целое число n и список по крайней мере из n элементов, и строит сбалансированное дерево из первыхn элементов дерева.
Результат, который возвращает partial-tree, — это пара (построенная через cons), car которой есть построенное дерево, а cdr — список элементов, не включенных вдерево.(define (list->tree elements)(car (partial-tree elements (length elements))))(define (partial-tree elts n)(if (= n 0)(cons ’() elts)(let ((left-size (quotient (- n 1) 2)))(let ((left-result (partial-tree elts left-size)))(let ((left-tree (car left-result))(non-left-elts (cdr left-result))(right-size (- n (+ left-size 1))))(let ((this-entry (car non-left-elts))(right-result (partial-tree (cdr non-left-elts)right-size)))(let ((right-tree (car right-result))(remaining-elts (cdr right-result)))(cons (make-tree this-entry left-tree right-tree)remaining-elts))))))))Глава 2.
Построение абстракций с помощью данных162а. Дайте краткое описание, как можно более ясно объясняющее работу partialtree. Нарисуйте дерево, которое partial-tree строит из списка (1 3 5 7 9 11)б. Каков порядок роста по отношению к числу шагов, которые требуются процедуреlist->tree для преобразования дерева из n элементов?Упражнение 2.65.Используя результаты упражнений 2.63 и 2.64, постройте реализации union-set и intersection-set порядка Θ(n) для множеств, реализованных как (сбалансированные) бинарные деревья41 .Множества и поиск информацииМы рассмотрели способы представления множеств при помощи списков и увидели,как выбор представления для объектов данных может сильно влиять на производительность программ, использующих эти данные. Еще одной причиной нашего внимания кмножествам было то, что описанные здесь методы снова и снова возникают в приложениях, связанных с поиском данных.Рассмотрим базу данных, содержащую большое количество записей, например, сведения о кадрах какой-нибудь компании или о транзакциях в торговой системе.
Какправило, системы управления данными много времени проводят, занимаясь поиском имодификацией данных в записях; следовательно, им нужны эффективные методы доступа к записям. Для этого часть каждой записи выделяется как идентифицирующий ключ(key). Ключом может служить что угодно, что однозначно определяет запись. В случаезаписей о кадрах это может быть номер карточки сотрудника.
Для торговой системыэто может быть номер транзакции. Каков бы ни был ключ, когда мы определяем запись в виде структуры данных, нам нужно указать процедуру выборки ключа, котораявозвращает ключ, связанный с данной записью.Пусть мы представляем базу данных как множество записей. Чтобы получить записьс данным ключом, мы используем процедуру lookup, которая принимает как аргументыключ и базу данных и возвращает запись, содержащую указанный ключ, либо ложь,если такой записи нет.
Lookup реализуется почти так же, как element-of-set?.Например, если множество записей реализуется как неупорядоченный список, мы моглибы написать(define (lookup given-key set-of-records)(cond ((null? set-of-records) false)((equal? given-key (key (car set-of-records)))(car set-of-records))(else (lookup given-key (cdr set-of-records)))))Конечно, существуют лучшие способы представить большие множества, чем в виденеупорядоченных списков. Системы доступа к информации, в которых необходим «произвольный доступ» к записям, как правило, реализуются с помощью методов, основанныхна деревьях, вроде вышеописанной системы с бинарными деревьями. При разработке таких систем методология абстракции данных оказывается весьма полезной.
Проектировщик может создать исходную реализацию с помощью простого, прямолинейного представления вроде неупорядоченных списков. Для окончательной версии это не подходит,41 Упражнениями2.63–2.65 мы обязаны Полу Хилфингеру.2.3. Символьные данные163но такой вариант можно использовать как «поспешную и небрежную» реализацию базыданных, на которой тестируется остальная часть системы. Позже представление данныхможно изменить и сделать более изощренным. Если доступ к базе данных происходитв терминах абстрактных селекторов и конструкторов, такое изменение представленияданных не потребует никаких модификаций в остальной системе.Упражнение 2.66.Реализуйте процедуру lookup для случая, когда множество записей организовано в виде бинарного дерева, отсортированного по числовым значениям ключей.2.3.4. Пример: деревья кодирования по ХаффмануЭтот раздел дает возможность попрактиковаться в использовании списковых структур и абстракции данных для работы с множествами и деревьями.
Они применяютсяк методам представления данных как последовательностей из единиц и нулей (битов).Например, стандартный код ASCII, который используется для представления текста вкомпьютерах, кодирует каждый символ как последовательность из семи бит. Семь битпозволяют нам обозначить 27 , то есть 128 различных символов.
В общем случае, еслинам требуется различать n символов, нам потребуется log2 n бит для каждого символа.Если все наши сообщения составлены из восьми символов A, B, C, D, E, F, G, и H, мыможем использовать код с тремя битами для каждого символа, напримерAB000001CD010011EF100101GH110111С таким кодом, сообщениеBACADAEAFABBAAAGAHкодируется как строка из 54 бит001000010000011000100000101000001001000000000110000111Такие коды, как ASCII и наш код от A до H, известны под названием кодов с фиксированной длиной, поскольку каждый символ сообщения они представляют с помощьюодного и того же числа битов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
