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

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

Процедуры tree->list-1 и tree->list-2 создают отсортированный список элементов в дереве (фактически, они производят обход дерева в глубину слева направо и собирают значения entry каждого узла дерева в список). Таким образом они делают одно и то же. Разница между ними в том, что tree->list-1 записана в форме, порождающей рекурсивный процесс, а tree->list-2 порождает итеративный процесс.

Поскольку все деревья на рисунке 2.16 содержат представление одного и того же множества, а стало быть содержат одни и те же элементы, обе процедура для каждого из этих деревьев будут выдавать список элементов множества в порядке возрастания: (1 3 5 7 9 11).

Несмотря на то, что процедуры делают одно и то же и похожи по используемым конструкциям, порядки их роста различны.

Второй вариант для каждого узла дерева выполняет константное число операций и вызывает себя для обоих поддеревьев. Следовательно, порядок его роста – Θ(n), где n – число элементов множества (узлов дерева).

Первый же вариант на каждом шаге рекурсии (для каждого узла дерева) вызывает процедуру append, которая на самом деле не выполняется за константное время, а требует числа шагов порядка количества элементов в поддереве. Будем предполагать, что дерево сбалансировано, то есть в поддеревьях каждого узла примерно поровну элементов. Пусть некоторое дерево содержит n элементов. Тогда поддеревья его корневого элемента содержат по n/2 элементов. Процедура tree->list-1 на корневом элементе потребует n/2 шагов для append и запустится на каждом из поддеревьев. На каждом из них (их два) аналогичным образом потребуется по n/4 шагов для append, то есть суммарно опять n/2. И так далее. То есть, спускаясь на один уровень по дереву от корня к листовым элементам, мы выполняем для всех вершин на этом уровне в сумме около n/2 шагов. Уровней в сбалансированном бинароном дереве, с которым мы имеем дело, примерно двоичный логарифм от числа элементов. Таким образом нам потребуется примерно n/2 * log2n, следовательно порядок роста – Θ(n log n).

Как вывод, есть смысл пользоваться вторым вариантом реализации, поскольку он порождает итеративный процесс и имеет меньший порядок роста.

Comments

Pingback from SICP по-русски » Решение упражнения 2.65 из SICP
Date: February 13, 2008, 10:16 pm

[…] tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам […]

Comment from nobody
Date: July 12, 2008, 1:46 pm

        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))

По-моему, это чистой воды рекурсия, а не итерация, так как для вычисления внешнего (copy-to-list (left-branch tree)… нужно сначала вычислить её третий аргумент, который является вызовом этой же процедуры: (copy-to-list (right-branch tree)…

Comment from thror
Date: December 28, 2008, 11:37 pm

Действительно. Процесс порождаемый второй функцией так же является рекурсивным. Чтобы убедиться в этом достаточно проделать несколько шагов вычислительного процесса следуя аппликативному порядку вычисления аргументов.

Существуют правильные бинарные деревья поиска, для которых полученные списки не будут отсортированы. Например

(3 (2 () ()) (7 (1 () ()) (11 () ())))

Далее, существуют реализации, в которых аппенд выполняется за О(1). Стандарт об этом ничего не говорит. Так что различие в трудоемкости может и отсутствовать.

Comment from thror
Date: May 1, 2009, 9:48 am

приношу свои извинения. Конечно же полученные списки будут будут отсортированы. Для любого правильного бинарного дерева поиска это будет так.
— thror

Comment from anton0xf
Date: August 25, 2009, 3:55 pm

thror: существуют реализации, в которых аппенд выполняется за О(1).
что-то я не могу придумать не одного способа это сделать, не портя исходные списки(

Comment from Максим
Date: December 13, 2014, 4:36 pm

Скажите, а разве второй вариант не является обходом справа-налево? Процедура оставляет на потом в переменной tree левое поддерево, и вычисляет второй операнд copy-to-list, который является рекурсивным вызовом этой же процедуры, то есть проделывает то же самое для поддеревьев правого поддерева. Таким образом сначала сортируются все правые поддеревья, а потом к ним приклеиваем по очереди entry, left-branch, entry, left-branch…
Кстати, не знаю нарочно ли, в книге ошибка в обеих процедурах – отсутствует проверка является ли дерево в аргументе листом (то есть в случае нашей интерпретации просто числом, не заключенным в список), соответственно мы не можем взять car,cadr и прочие от простого числа. Нужно переписать всё в cond и после проверки на пустой список добавить проверку – ((number? tree) (list tree)).

Comment from Irv
Date: January 7, 2017, 10:33 am

ошибку с проверкой то, является ли дерево листом можно убрать на уровне представления деревьев

(define (make-tree entry left right) (list entry left right))
(define (entry tree)
  (if (pair? tree)
      (car tree)
      tree))
(define (left tree)
  (if (and (pair? tree) (pair? (cdr tree)))
      (cadr tree)
      '()))
(define (right tree)
  (if (and (pair? tree) (pair? (cdr tree)) (pair? (cddr tree)))
      (caddr tree)
      '()))

деревья можно определять так

(define t1 '(7 (3 1 5) (9 () 11)))
(define t2 '(3 1 (7 5 (9 () 11))))
(define t3 '(5 (3 1) (9 7 11)))

Write a comment