Процедура узла вставки двоичного дерева не работает должным образом (схема)

Question

Я реализовал функцию для вставки узлов в двоичное дерево.
Узел дерева представляет собой список вида (left-node key right-node).
(insert tree n) - это моя функция узла вставки, где дерево - это список узлов дерева в двоичном дереве поиска, и я хочу добавить значение ключа n в качестве нового узла.

Итак, (insert '(((() 4 ()) 5 (() 2 ())) 6 ()) 7) дает вывод как
(((() 4 ()) 5 (() 2 ())) 6 (() 7 ())).

Теперь я хочу сделать что-то вроде этого:
1 . Определите список значений. (define (f) (list '1 `2 `3 `4 `5 ))
2 . Просмотрите список и введите значения по одному в дереве, начиная с пустого дерева.

Итак, когда я попытался выполнить шаг 2, я сделал следующее:

(define x ()) ;; Tree x is initially empty
(insert x 2)  ;; This prints (() 2 ())
(insert x 1)  ;; This prints (() 1 ()). I want it to be ((() 1 ()) 2 ()).
(insert x 3)  ;; This prints (() 3 ()). I want it to be ((() 1 ()) 2 (() 3 ())).

Вот где я застрял.
Я предоставляю свою функцию вставки ниже.

(define (left tree) (list-ref tree 0))
(define (value tree) (list-ref tree 1))
(define (right tree) (list-ref tree 2))

(define (insert tree n)
  (cond
    [( null? tree ) ( list () n () )]
    [(< n (cadr tree)) (list (insert (car tree) n) (cadr tree) (caddr tree))] 
    [(> n (cadr tree)) (list (car tree) (cadr tree) (insert (caddr tree) n))] 
    [else tree] 
  )
)

Может кто-нибудь подсказать, как мне достичь желаемых результатов?

Answer 1

Ваш код имеет три проблемы.Обратите внимание, что в следующем коде я немного груб по поводу кода: я просто тупой, потому что пишу быстро, и я не пытаюсь быть грубым с вами лично!

Вы не определили все необходимые абстракции

Вам нужна как минимум функция, которая создает узлы дерева, функция, которая проверяет нулевое дерево, и объект, который представляет нулевые деревья.Вот более полный набор абстракций:

(define null-tree '())

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (list left key right))

(define (left tree)
  (list-ref tree 0))

(define (value tree)
  (list-ref tree 1))

(define (right tree)
  (list-ref tree 2))

Ваша insert функция не использует абстракции

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

(define (insert tree n)
  (cond
    [(tree-null? tree)
     (make-tree-node null-tree n null-tree)]
    [(< n (value tree))
     (make-tree-node (insert (left tree) n)
                     (value tree)
                     (right tree))]
    [(> n (value tree))
     (make-tree-node (left tree)
                     (value tree)
                     (insert (right tree) n))]
    [else tree]))

Вы не поняли, что insert - это функция

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

Таким образом, чтобы добавить, например, последовательность элементоввам нужно построить последовательность деревьев с insert, в которые добавлены эти элементы:

(define (insert-elements tree elts)
  (if (null? elts)
      tree
      (insert-elements (insert tree (first elts)) (rest elts))))

Сейчас:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'(((() 0 ()) 1 (() 2 (() 3 (() 4 ())))) 7 (((() 20 ()) 48 ()) 202 ()))

---

Зачем использовать абстракции

Если я изменю абстракции для деревьев:

(define null-tree '/)

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (vector left key right))

(define (left tree)
  (vector-ref tree 0))

(define (value tree)
  (vector-ref tree 1))

(define (right tree)
  (vector-ref tree 2))

Тогда я смогу использовать точно такую ​​же функцию с этим новым типом дерева:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'#(#(#(/ 0 /) 1 #(/ 2 #(/ 3 #(/ 4 /)))) 7 #(#(#(/ 20 /) 48 /) 202 /))