Сколько шагов мы на этом выигрываем? В худшем случае, объект, который мы ищем, может быть наибольшим в множестве, так что число шагов то же, что и для неупорядоченного представления. С другой стороны, если мы ищем элементы разных размеров, можно ожидать, что иногда мы сможем останавливаться близко к началу списка, а иногда нам все же потребуется просмотреть большую его часть. В среднем мы можем ожидать, что потребуется просмотреть около половины элементов множества. Таким образом, среднее число требуемых шагов будет примерно n/2. Это все еще рост порядка 0(n), но это экономит нам в среднем половину числа шагов по сравнению с предыдущей реализацией.

Более впечатляющее ускорение мы получаем в intersection-set. При неупорядоченном представлении эта операция требовала 0(n2) шагов, поскольку мы производили полный поиск в set2 для каждого элемента setl. Однако при упорядоченном представлении мы можем воспользоваться более разумным методом. Начнем со сравнения первых элементов двух множеств, xl и x2. Если xl равно x2, мы получаем один элемент пересечения, а остальные элементы пересечения мы можем получить, пересекая оставшиеся элементы списков-множеств. Допустим, однако, что xl меньше, чем x2. Поскольку x2 - наименьший элемент set2, мы можем немедленно заключить, что xl больше нигде в set2 не может встретиться и, следовательно, не принадлежит пересечению. Следовательно пересечение двух множеств равно пересечению set2 с cdr от setl. Подобным образом, если x2 меньше, чем xl, то пересечение множеств получается путем пересечения setl с cdr от set2. Вот процедура:

(define (intersection-set setl set2)

(if (or (null? setl) (null? set2))

()

(let ((xl (car setl)) (x2 (car set2))) (cond ((= xl x2)

(cons xl

(intersection-set (cdr setl)

(cdr set2))))

((< xl x2)

(intersection-set (cdr setl) set2)) ((< x2 xl)

(intersection-set setl (cdr set2)))))))

Чтобы оценить число шагов, необходимое для этого процесса, заметим, что на каждом шагу мы сводим задачу нахождения пересечения к вычислению пересечения меньших множеств - убирая первый элемент либо из setl, либо из set2, либо из обоих. Таким образом, число требуемых шагов не больше суммы размеров setl и set2, а не их произведения, как при неупорядоченном представлении. Это рост 0(n), а не 0(n2) - заметное ускорение, даже для множеств небольшого размера.

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

Напишите реализацию adjoin-set для упорядоченного представления. По аналогии с element-of-set? покажите, как использовать упорядочение, чтобы получить процедуру, которая в среднем требует только половину того числа шагов, которое требуется при неупорядоченном представлении.

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

Дайте представление порядка @(п) для операции union-set с представлением в виде

735

11

Рис. 2.16: Различные бинарные деревья, представляющие множество {1,3, 5,7, 9,11}.

упорядоченных списков.

Множества как бинарные деревья

Можно добиться еще лучших результатов, чем при представлении в виде упорядоченных списков, если расположить элементы множества в виде дерева. Каждая вершина дерева содержит один элемент множества, называемый «входом» этой вершины, и указатели (возможно, пустые) на две другие вершины. «Левый» указатель указывает на элементы, меньшие, чем тот, который содержится в вершине, а «правый» на элементы, большие, чем тот, который содержится в вершине. На рисунке 2.16 показано несколько вариантов представления множества {1, 3, 5, 7, 9, 11} в виде дерева. Одно и то же множество может быть представлено в виде дерева несколькими различными способами. Единственное, чего мы требуем от правильного представления - это чтобы все элементы левого поддерева были меньше, чем вход вершины, а элементы правого поддерева больше.

Преимущество древовидного представления следующее: Предположим, мы хотим проверить, содержится ли в множестве число x. Начнем с того, что сравним x со входом начальной вершины. Если x меньше его, то мы уже знаем, что достаточно просмотреть только левое поддерево; если x больше, достаточно просмотреть правое поддерево. Если дерево «сбалансировано», то каждое из поддеревьев будет по размеру примерно вполовину меньше. Таким образом, за один шаг мы свели задачу поиска в дереве размера n к задаче поиска в дереве размера n/2. Поскольку размер дерева уменьшается вдвое на каждом шаге, следует ожидать, что число шагов, требуемых для поиска в дереве размера n, растет как 0(logn).38 Для больших множеств это будет заметным ускорением по сравнению с предыдущими реализациями.

Деревья мы можем представлять при помощи списков. Каждая вершина будет списком из трех элементов: вход вершины, левое поддерево и правое под-

38Уменьшение размера задачи вдвое на каждом шагу является определяющей характеристикой логарифмического роста, как мы видели на примере алгоритма быстрого возведения в степень в разделе 1.2.4 и метода половинного деления в разделе 1.3.3.

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

39

представление при помощи следующих процедур:39

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right) (list entry left right))

Теперь можно написать процедуру element-of-set? с использованием вышеописанной стратегии:

(define (element-of-set? x set) (cond ((null? set) false)

((= x (entry set)) true) ((< x (entry set))

(element-of-set? x (left-branch set))) ((> x (entry set)) (element-of-set? x (right-branch set)))))

Добавление элемента к множеству реализуется похожим образом и также требует 0(log n) шагов. Чтобы добавить объект 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 мы можем рассматривать как способ изолировать абстракцию «бинарное дерево» от конкретного способа, которым мы желаем представить такое дерево в виде списковой структуры.