스키마에서 노드 삭제

Question

스키마의 이진 검색 트리에서 노드를 삭제하려고하는데 코드의 일부를 제거하는 데 문제가 있습니다. 스키마에서 새 트리를 만들지 않고 노드 값을 삭제하려면 어떻게해야합니까? 값 오른쪽 하위 트리 또는 노드의 왼쪽 서브 트리 중 하나가 새 값으로 현재 위치에서 변경 될 수 있음 : 의미 -

(define (delete-node v T) 
    (cond ((null? T) '()) 
    ((< v (value T)) 
    (delete-node v (left T))) 
    ((> v (value T)) 
    (delete-node v (right T))) 
    (else 
     (cond ((and (null? (right T))(not (null? (left T)))) '()) 
      ;promote the (left T) to the node 
      ;repeat 
      ((and (null? (left T))(not (null? (right T)))) '()) 
      ;promote the (right T) to the node           
      ;repeat 

Answer 1

현재 위치에서 노드를 삭제를 들어, 나무는 변경 가능해야합니다.

트래버스 중에 새 트리를 만드는 것이 더 쉽지만 구현 옵션을 몇 가지 선택해야합니다. 여기에 솔루션의 스케치입니다 :

(define (delete-node v T) 
    (cond ((null? T) '()) 
     ((< v (value T)) 
     ; see how we build the new tree 
     (make-node (value T) 
        (delete-node v (left T)) 
        (right T))) 
     ((> v (value T)) 
     ; see how we build the new tree 
     (make-node (value T) 
        (left T) 
        (delete-node v (right T)))) 
     (else 
     (cond ((and (null? (right T)) (and (null? (left T)))) 
       ; this case was missing 
       '()) 
       ((and (null? (right T)) (not (null? (left T)))) 
       (left tree)) 
       ((and (null? (left T)) (not (null? (right T)))) 
       (right tree)) 
       (else 
       ; implementation detail: if both subtrees of the 
       ; node to be deleted are non-null, who should take 
       ; the place of the deleted node? the new subtree 
       ; must preserve the order property of the tree 
       <???>))))) 

흥미로운 사건이 <???>로 표시되어 있습니다. 몇 가지 옵션이 있습니다. 선택하고 구현하는 것은 사용자의 몫입니다. 예를 들어, 정렬 된 트리 (여기서 가정 한 것으로 가정)에서 왼쪽 하위 트리에서 가장 큰 요소를 선택하고 위치로 이동하기 전에 재귀 적으로 삭제할 수 있습니다.

사용중인 균형 정의에 따라 노드를 삭제 한 후에 트리가 밸런스으로 남아 있어야하는 경우 알고리즘이 까다 롭습니다. 트리가 균형을 이루지 않는다고 가정합니다.