1

スキームで二分探索木からノードを削除しようとしていますが、コードの削除部分に問題があります。スキームで新しいツリーを作成せずにノード値を削除するにはどうすればよいですか? 

(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
4

1 に答える 1

3

ノードをインプレースで削除するには、ツリーが変更可能である必要があります。つまり、ノードの値、右側のサブツリー、または左側のサブツリーのいずれかを新しい値でインプレースで変更できるということです。

トラバースしながら新しいツリーを作成する方が簡単ですが、それでも、いくつかの実装上の選択を行う必要があります。ソリューションのスケッチを次に示します。

(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
                <???>)))))

興味深いケースは でマークされてい<???>ます。いくつかのオプションがあり、1 つを選択して実装するのはあなた次第です。たとえば、並べ替えられたツリー (ここではそうだと思います) では、左側のサブツリーから最大の要素を選択し、再帰的に削除してから移動することができます。

ノードを削除した後もツリーのバランスを維持する必要がある場合 (使用中のバランス定義に従って)、アルゴリズムはよりトリッキーであることに注意してください。ツリーのバランスが取れていないと仮定しています。

于 2013-10-17T14:43:02.807 に答える