2-3-4ツリーの最小値を見つける

Question

最初にオフ、この質問は宿題ではありません。私は現在、Robert Laforeによって本「データ構造とアルゴリズム第2版」を読んでいます。第10章では、約2-3-4の木について学び、その木の最小値を見つける方法を書くように求められました。

概念の観点から、最小値がどこにあるかを理解しています。それは葉の中のほとんどのデータ項目です。

プログラミングの観点からは、このデータ項目を見つける方法を実装する方法について少し混乱しています。ノードが葉であるかどうかを判断できるブール値があります。だから私が最初に何をしたのはこれでした：

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

.

これは何をしていますか（少なくとも私がそれをするべきなものは、ルートノードから始めるCurnodeを作成されます。その後、curnode.getminを格納する最小値を作成します。getmin（）は、インデックスの配列の値を取得します0（最低値を保持する必要があります）。その後、現在のノードが葉ではないが、最小点から次の子を横切るべきです。現在のノードが葉であると、それは最小値を返すべきです。< / P>

これはうまくいきません。誰もがこれを実装する方法についてのアイデアを持っていますか？ヒントや提案、あるいは他のもの？

編集：各クラスとそれらがどのように対話するかを見るために、ここではそれぞれの別々のクラスへのリンクがあります。 My Tree234クラス

に最小値メソッドを入れる

ノード、 tree234 、およびプログラムが実行されている場合、 tree234app

Answer 1

最初に、早く助けを早く、 sscce < / a>それは私達にあなたのプログラム全体の最小限の実装を与えます - 私たち自身のIDEにC / PをC / Pでき、何が起こっているのかを見ることができるもの。このコードのビットのみを見ると、なぜ「これが機能しないのか」がなぜなのかわかりません。

秒、あなたは「これが機能していない」という意味で詳述する必要があります - すなわちそれがしていることやそうしていないことを正確に教えてください。あなたの代わりにあなたの代わりにしているのですが、なぜそれがそれがそうする理由のある程度の確実性であなたに言うことができます。

しかし、1つのことはジャンプアウトしています。最初に作成した同じmin値を返します。言い換えれば、あなたの反復ルーチンはあなたがそれを望むものを正確にしているかもしれませんが、それの結果として戻り値には何もしていません。

私はあなたが何かをする必要があると思う：

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

.

私が作った唯一の変更はRETURNステートメントの上に回線を挿入していたことに注意してください。これは、minをツリー内の左端の要素に接続されている最小値に再割り当てします。

Answer 2

より効率的には、ノード内の項目が常に2-3-4ツリーで昇順でソートされているため、getNextChild(curNode, min)を呼び出す必要がないことに注意してください。Min宣言も開始時に必要ではありません。だからあなたのプログラムはこのようなものかもしれません：

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}

.