Вставка значения в двоичное дерево поиска по схеме

Question

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

bst-element ссылается на другую функцию. У меня есть проверка, существует ли значение в дереве, так как дерево не должно иметь дубликатов.

(define (bst-insert item bst-tree) 
    (cond ((bst-element? item bst-tree)bst-tree) 
     ((null? bst-tree) ???) 
     ((< item (bst-value bst-tree))(bst-insert item (bst-left bst-tree))) 
     ((> item (bst-value bst-tree))(bst-insert item (bst-right bst-tree))))) 

Answer 1

Если вы хотите, чтобы вставить значение в дереве в функциональном стиле, то есть без побочных эффектов, вы не можете предположить, что есть что-то делать только, когда вы достигнете лист, в котором вы должны вставьте новое значение. Скорее, вы должны rebuild дерево, пока вы его посещаете, так что в итоге результатом будет новое дерево с вставкой элемента в нужное положение.

Поскольку вы не показываете, как реализуются дерево, я полагаю, что пустое дерево представляются как '(), и что существует функция (make-bst item left right) построить дерево с определенным item, а left поддерева и right поддерева , В этих предположениях, здесь возможное решение:

(define (bst-insert item bst-tree) 
    (cond ((null? bst-tree) (make-bst item '() '())) 
     ((= (bst-value bst-tree) item) bst-tree) 
     ((< item (bst-value bst-tree)) 
     (make-bst (bst-value bst-tree) 
        (bst-insert item (bst-left bst-tree)) 
        (bst-right bst-tree))) 
     (else (make-bst (bst-value bst-tree) 
         (bst-left bst-tree) 
         (bst-insert item (bst-right bst-tree)))))) 

Обратите внимание, что проверка, если элемент уже присутствует делается внутри этой функции, без необходимости дублирования работы с другой функцией.