Вставить узел в дерево - Racket

Question

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

(define-struct (Some T) 
    ([value : T])) 

(define-type (Option T) 
    (U 'None (Some T))) 

(define-type BST (U 'E Nd)) 

(define-struct Nd 
    ([root : Integer] 
    [lsub : BST] 
    [rsub : BST])) 

(: insert : Integer BST -> BST) 
;; insert an item into a tree 
;; note: do not insert duplicate items 
(define (insert n x) 
    (match x 
    ('E 'E) 
    ((Nd ro ls rs) 
    (cond 
     ((= (size x) 1) (Nd ro (Nd n 'E 'E) 'E)) 
     (else 
     (Nd ro ls rs)))))) 

Вставка - это вставка, которая вставляет узел в дерево.

Ниже команда, которую Я дам:

(insert 10 (Nd 1 (Nd 2 (Nd 4 'E 'E) (Nd 5 'E 'E)) (Nd 3 (Nd 6 'E 'E) (Nd 7 'E 'E)))) 

И он должен вставить десять в дерево. Тем не менее, я учусь самостоятельно дома, и у меня нет идеи, что делать. Пожалуйста помоги. Спасибо огромное!

Answer 1

Вам не хватает рекурсии, и ваш базовый случай ошибочен.

Вставка в пустое дерево создает дерево с одним узлом.

Вставки в непустой BST имеет три случая:

• Если элемент такое же, как в этом узле, возвращающего дерево без изменений
• Если элемент меньше, чем этот узел, вставьте левое поддерево
• в противном случае, вставьте в правом поддереве

Что-то вроде

(define (insert n x) 
    (match x 
    ('E (Nd n 'E 'E)) 
    ((Nd ro ls rs) 
    (cond 
     ((= n ro) x) 
     ((< n ro) (Nd ro (insert n ls) rs)) 
     (else  (Nd ro ls (insert n rs))))))) 

Дерево, которое вы хотите вставить, не является BST, поэтому это не сработает.

Ваше дерево имеет следующую структуру:

1 
    /\ 
2 3 
/\ /\ 
4 5 6 7 

дерево поиска с теми элементами будет выглядеть следующим образом:

4 
    /\ 
2 6 
/\ /\ 
1 3 5 7 

, который

(Nd 4 (Nd 2 (Nd 1 'E 'E) (Nd 3 'E 'E)) (Nd 6 (Nd 5 'E 'E) (Nd 7 'E 'E)))