SICP по-русски

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом.

Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом по левой части списка, а правое – аналогично по правой части списка.

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

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

Хочу отметить, что по построению дерево получается сбалансированным (так как поддеревья строятся из примерно равных половин списка).

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