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

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

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

Получим следующую процедуру:

(define (lookup given-key set-of-records) 
  (cond ((null? set-of-records) false) 
        ((= given-key (key (entry set-of-records))) 
         (entry set-of-records)) 
        ((< given-key (key (entry set-of-records))) 
         (lookup given-key (left-branch set-of-records))) 
        ((> given-key (key (entry set-of-records))) 
         (lookup given-key (right-branch set-of-records)))))

Последнее условие в cond можно заменить на else.

Write a comment