7

Рис. 2.17: Несбалансированное дерево, порожденное последовательным присоединением элементов от 1 до 7.

которые мы строим, были сбалансированы? Даже если мы начинаем со сбалансированного дерева, добавление элементов при помощи adjoin-set может дать несбалансированный результат. Поскольку позиция нового добавляемого элемента зависит от того, как этот элемент соотносится с объектами, уже содержащимися в множестве, мы имеем право ожидать, что, если мы будем добавлять элементы «случайным образом», в среднем дерево будет получаться сбалансированным. Однако такой гарантии у нас нет. Например, если мы начнем с пустого множества и будем добавлять по очереди числа от 1 до 7, то получится весьма несбалансированное дерево, показанное на рисунке 2.17. В этом дереве все левые поддеревья пусты, так что нет никакого преимущества по сравнению с простым упорядоченным списком. Одним из способов решения этой проблемы было бы определение операции, которая переводит произвольное дерево в сбалансированное с теми же элементами. Тогда мы сможем проводить преобразование через каждые несколько операций adjoin-set, чтобы поддерживать множество в сбалансированном виде. Есть и другие способы решения этой задачи. Большая часть из них связана с разработкой новых структур данных, для которых и поиск, и вставка могут производиться за 0(logn) шагов.40

Упражнение 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)

40 Примерами таких структур могут служить b-деревья (B-trees) и красно-черные деревья (red-black trees). Существует обширная литература по структурам данных, посвященная этой задаче. См. Cormen, Leiserson, and Rivest 1990.

(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 ()))

a.Для всякого ли дерева эти процедуры дают одинаковый результат? Если нет, то как их результаты различаются? Какой результат дают эти две процедуры для деревьев с рисунка 2.16?

b.Одинаков ли порядок роста этих процедур по отношению к числу шагов, требуемых для преобразования сбалансированного дерева с 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 l) 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 l)))) (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))))))))

a.Дайте краткое описание, как можно более ясно объясняющее работу partial-tree. Нарисуйте дерево, которое partial-tree строит из списка (l 3 5 7 9 ll)

b.Каков порядок роста по отношению к числу шагов, которые требуются процедуре list->tree для преобразования дерева из n элементов?

Упражнение 2.65.

Используя результаты упражнений 2.63 и 2.64, постройте реализации union-set и intersection-set порядка 0(n) для множеств, реализованных как (сбалансированные) бинарные деревья.41

41 Упражнениями 2.63-2.65 мы обязаны Полу Хилфингеру.

Множества и поиск информации

Мы рассмотрели способы представления множеств при помощи списков и увидели, как выбор представления для объектов данных может сильно влиять на производительность программ, использующих эти данные. Еще одной причиной нашего внимания к множествам было то, что описанные здесь методы снова и снова возникают в приложениях, связанных с поиском данных.

Рассмотрим базу данных, содержащую большое количество записей, например, сведения о кадрах какой-нибудь компании или о транзакциях в торговой системе. Как правило, системы управления данными много времени проводят, занимаясь поиском и модификацией данных в записях; следовательно, им нужны эффективные методы доступа к записям. Для этого часть каждой записи выделяется как идентифицирующий ключ (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)))))

Конечно, существуют лучшие способы представить большие множества, чем в виде неупорядоченных списков. Системы доступа к информации, в которых необходим «произвольный доступ» к записям, как правило, реализуются с помощью методов, основанных на деревьях, вроде вышеописанной системы с бинарными деревьями. При разработке таких систем методология абстракции данных оказывается весьма полезной. Проектировщик может создать исходную реализацию с помощью простого, прямолинейного представления вроде неупорядоченных списков. Для окончательной версии это не подходит, но такой вариант можно использовать как «поспешную и небрежную» реализацию базы данных, на которой тестируется остальная часть системы. Позже представление данных можно изменить и сделать более изощренным. Если доступ к базе данных происходит в терминах абстрактных селекторов и конструкторов, такое изменение представления данных не потребует никаких модификаций в остальной системе.

Упражнение 2.66.

Реализуйте процедуру lookup для случая, когда множество записей организовано в виде бинарного дерева, отсортированного по числовым значениям ключей.