問題タブ [tree-balancing]

HW の割り当てとして、BinarySearchTree クラスに一連のメソッドを追加するように依頼されました。私が持っている 2 つのメソッドは、balance と InsertTree です (InsertNode という名前にするべきだったと思います)。教科書の著者は、メソッドがどのように見えるべきかの疑似コードを提供しました。どちらの方法も相互に機能します。balance は、不均衡なツリーを取り、各要素を配列に挿入することになっています。InsertTree は、配列から要素を取得し、それらを新しく形成されたツリーに戻すことになっていると思います。

BST クラス自体はかなり大きいので、投稿するのは得策ではないと思います。ただし、ソース コードは、サンプル マテリアルの下にあります。参照中のコードは ch07.trees パッケージにあります。

これは、これまでの著者の擬似コードの私の解釈です。

すべてのメソッドが T 型のジェネリックであるため、ArrayList を使用する必要があります。私のドライバー クラスでは、要素 [A、B、C、D、E、F] の不均衡なセットを追加するだけで、インデックスはインクリメントしたことを正しく示します。しかし、新しいツリーが InsertTree( 0, index - 1) を呼び出すと、次のようになります。

163tree.InsertTree(0, index -1);行目と18​​0行目はtree.add(array.get(mid));

問題は中間点に関係しているようですが、何が問題なのかわかりません。私は ArrayLists を使用する専門家ではないため、これを解決するための助けをいただければ幸いです。

編集：

問題は解決したと思います。作成した配列をメソッドの外側ではなく、balance メソッドに戻し、その配列を InsertTree メソッドの引数に追加しました。次に、すべての条件付き出力を this.tree.add から this.add に変更する必要がありました。また、NullPointerException を取得する前に、BinarySearchTree ツリーをバランスの取れたメソッドに戻しました。

私の方法が意図したとおりに機能するかどうかは、まだ判断されていません。

セルフ バランシング ツリーからノードを削除しようとすると、特にメモリ リークが発生します (挿入操作のみの場合と同様に、リークはありません)。削除操作と挿入操作が完了した後、関数を呼び出してツリーを破棄しましたが、まだメモリ リークが発生しています。関数自体は正常に動作しているようです (ツリーの事前注文トラバーサルを出力した後、それは正しいです)。これは私の削除機能がどのように見えるかです:

そして、私の破棄/解放機能:

削除しようとしているノードのメモリを解放する方法がわかりません。そのため、メモリ リークが発生します。(destroytree で) 解放されているルートを出力すると、常に削除されたノードが欠落しているため、メモリ リークが発生していると思います。私の唯一の問題は、私が書いた deletenode 関数では、このメモリを解放する場所がわからないことです。助けていただければ幸いです。また、ノードを挿入するときはもちろん、挿入ノードで malloc します。