DrRacketバイナリ検索ツリーのルートを削除する

Question

ご注意ください！ - >私は直接的なコード例は探していませんが、私の推論の穏やかなマッサージを探しています...

私は、バイナリ検索ツリーのルートを削除する関数を書くように求められました： i）ツリーを右に回転 ii）右のサブツリーのルートを削除する（元のbstルート） iii）bstを新しいルート（元のツリーの左側）で再構築し、適切な再配置そのノードの子の...ここで私が持っているものです。

(define (rm-root my-bst) 
     (list (key (rot-r my-bst)) 
      (left (rot-r my-bst)) 
      (append (right (right (rot-r my-bst))) 
        (left (right (rot-r my-bst)))))) 

すべての偉大されており、それは子供たちに木を再構築しないことのために期待ルートノードに「昇格」されたノードの名前。誰でも私がそれをどうやって実装すべきか考えてもらえるか？私は、Bstをリストとして定義し、関数rot-rはbstを右に回転させることを言及する必要があります。ありがとうございました。

Answer 1

質問がされてから12日後にこれが役立つかどうかはわかりませんが、ここには入ります。

私は、データ構造が左と右がツリー（または空であるが、これはこれとは無関係）である形式（左のリストキー）であると推測しています。そうでない場合は、それを明確にする必要があります。

あなたのコードの1つの問題は、あなたが右に持っている2つのリストを直接追加したくないということです。それらのうちの1つのキーと、次に左右のキーを使用してリストを作成したいとします。私はこれを正しく読んでいる場合、左の関数はツリーを返す必要がありますので、正常に動作するはずです。

もし私があなたのことが間違っている主な可能性があると思われるなら、私はrot-rの実装をチェックします。