2-3-4ツリーの最小値を見つける
-
20-12-2019 - |
質問
最初にオフ、この質問は宿題ではありません。私は現在、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
解決
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
をツリー内の左端の要素に接続されている最小値に再割り当てします。
他のヒント
より効率的には、ノード内の項目が常に2-3-4ツリーで昇順でソートされているため、getNextChild(curNode, min)
を呼び出す必要がないことに注意してください。Min宣言も開始時に必要ではありません。だからあなたのプログラムはこのようなものかもしれません:
public long minValue() {
Node curNode = root;
while (!curNode.isLeaf()) {
curNode = curNode.getChild(0);
}
return curNode.getMin();
}
.