0

私は、割り当てのさまざまな段階に分割されたいくつかの異なる操作をサポートすることになっている 2 ～ 3 個の検索ツリーを作成する割り当てを受けました。ステージ 1 では、操作 get、put、および size をサポートすることになっています。私は現在 get 操作を実装しようとしていますが、行き詰まっており、続行する方法に頭を悩ませることができないため、自分が書いたすべてのコードに疑問を呈しており、他の誰かの入力が必要だと感じています.

2 ～ 3 個の検索ツリーを作成する方法を調べてみましたが、意味をなさない、または必要な機能を実行していないコードが大量に見つかりました。ゼロからの自己、そして今ここにいます。

私のノードクラス

package kth.id2010.lab.lab04;

public class Node {
    boolean isLeaf = false; 
    int numberOfKeys;
    String[] keys = new String[2]; //each node can contain up to 2 keys
    int[] values = new int[2]; //every key contains 2 values
    Node[] subtrees = new Node[3]; //every node can contain pointers to 3 different nodes




    Node(Node n) {
        n.numberOfKeys = 0;
        n.isLeaf = true;
    }

}

マイツリー作成教室

package kth.id2010.lab.lab04;

public class Tree {

    Node root; // root node of the tree
    int n; // number of elements in the tree

    private Tree(){
        root = new Node(root);
        n = 0;       
    }
    //Return the values of the key if we find it
    public int[] get(String key){
        //if the root has no subtrees check if it contain the right key
        if(this.root.subtrees.length == 0){
            if(this.root.keys[0] == key){
                return(this.root.keys[0].values);
            }
            else if(this.root.keys[1] == key){
                return(this.root.keys[1].values);
            }
        }
        //if noot in root, check its subtree nodes
        //and here I can't get my head around how to traverse down the tree
        else{
            for(int i = 0; i < this.root.subtrees.length; i++){
                for(int j = 0; j < this.root.subtrees[i].keys.length; j++){
                    if(this.root.subtrees[i].keys[j] == key){
                        return(this.root.subtrees[i].keys[j].values);
                    }
                }
            } 
        }
        return null;
    }
}

私が自分で言えることは、values[]各キーにバインドする方法を見つける必要があるということですが、その方法がわかりません。寝不足か、この考え方にとらわれているのかもしれません。

4

1 に答える 1

2

values[] を各キーにバインドする

HashMapそれが目的なので、そのマッピングを行うために a を使用する方が理にかなっているかもしれません。さらに、2 つのキーがあり、各キーに 2 つの値がある場合、値は 2 つではなく 4 つになります ;)

一般に、ツリー構造の get メソッドはほとんどの場合、再帰的に実装できます。getこれは、疑似コードでの 2-3 ツリーのアルゴリズムの非常に一般的な実装です。

V get<K, V>(Node<K, V> node, K key)
{
    if(node.is_leaf())
    {
        return node.keys.get(key); // This will either return the value, or null if the key isn't in the leaf and thus not in the tree
    }
    if(key < node.left_key)
    {
        return get(node.left_child, key); // If our key goes to the left, go left recursively
    }
    else if(node.two_node && key <= node.right_key)
    {
        return get(node.center_child, key) // If we have two keys, and we're less than the second one, we go down the center recursively
    }
    else
    {
        return get(node.right_child, key); // If we've gotten here, we know we're going right, go down that path recursively
    }
}

これにより、正しい方向に進むことができます。2 ～ 3 個のツリーの挿入/削除はもう少し複雑ですが、少なくともこれで、どのように考えるかが理解できるはずです。ヒント; クラスNodeは二重にリンクする必要があります。つまり、各ノード/リーフはその親ノードとその子を参照する必要があり、ルートは単に親が であるノードですnull。

于 2014-10-08T17:16:26.387 に答える