Решение упражнения 2.65 из SICP

13 February, 2008 (22:04) | Решения упражнений

Процедуры tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам возможность свободно преобразовывать множества, представленные упорядоченными списками и (сбалансированными) бинарными деревьями, из одного представления в другое за линейное (Θ(n)) число операций.

Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для этого просто переведем исходные множества в списочное представление, воспользуемся старыми операциями и переведем результат в “деревянное” представление.

Вот как можно записать реализации операций объединения и пересечения множеств, представленных бинарными деревьями, воспользовавшись этой идеей:

(define (union-set-tree set1 set2) 
  (list->tree (union-set (tree->list set1)          
                         (tree->list set2))))
(define (intersection-set-tree set1 set2) 
  (list->tree (intersection-set (tree->list set1)          
                                (tree->list set2))))

Я дал процедурам новые имена, чтобы не было путаницы со старыми процедурами, определенными для списочного представления. Поскольку все преобразования из одной форму в другую и обратно, а также старые операции над списочными представлениями имели порядок роста Θ(n), новые операции также имеют порядок роста Θ(n).

Write a comment