2

BTreeの挿入メソッドを実装しようとしています。私のBTreeクラスは、ルートBNodeへのポインターを保持しています。挿入メソッドには、内部メソッドと外部メソッドの両方があります。内部のものはまだ再発していませんが、ルートが渡されて2回目の挿入の値を保持するのに問題があります。スコーピングの問題かもしれないと思いますが、正確にはわかりません。主に、メソッドをテストするために2つの値を挿入しようとしましたが、2番目の挿入では、root == nullと見なされ、最初のキー値が上書きされるようです。なぜこれが起こるかもしれない人はいますか？

これが私の関数です：

    template<typename T, int M>
    class BTree{
    private:


        returnStatus _insert( BNode<T, M>* r, const T& val, BNode<T, M>*& dptr, T& dkv );
        returnStatus shuffle_insert( BNode<T, M>* r, const T& val );
        returnStatus split_insert( BNode<T, M>* r, const T& val, BNode<T, M>*& dptr, T& dkv );
        bool isNodeLeaf( BNode<T, M>* node );
        int _getNodeIndex( BNode<T, M>* r, const T& val );

        returnStatus _find( BNode<T, M>* r, const T& val );
        returnStatus _remove( BNode<T, M>* r, const T& val, BNode<T, M>* & dptr, T& dkv );
        void _traverse( BNode<T, M>* r );

    public:
        BNode<T, M>* root;
        int size;

        BTree();
        void insert( const T& val );
        returnStatus find( const T& val );
        void remove( const T& val );
        void traverse();
        ~BTree();

    };
    template<typename T, int M>
    BTree<T, M>::BTree()
    {
    root = NULL;
    size = 0;
        }
        template<typename T, int M>
    returnStatus BTree<T, M>::_insert( BNode<T, M>* r, const T& val, BNode<T, M>*& dptr, T& dkv )
    {
    if( r == NULL ){
        dptr = NULL;
        dkv = val;
        r = new BNode<T, M>;
        r->keys[0] = val;
        size++; 
        r->keyCount++;

        return unsuccessful;
    }else{
        returnStatus contains = find(val);

        if( contains == duplicate ){
            return duplicate;
        }else{

            if( r->keyCount < M-1 ){
                returnStatus hold = shuffle_insert(r, val);
                return hold;
            }else{
                cout<<"need to split"<<endl;
                //split_insert
            }
        }
    }
}
template<typename T, int M>
returnStatus BTree<T, M>::shuffle_insert( BNode<T, M>* r, const T& val )
{
    if(r->keyCount == M-1 ) return unsuccessful;

    int index = _getNodeIndex(r, val);

    for(int i = r->keyCount; i>index; i--){
        r->keys[i+1] = r->keys[i];
    }
    r->keys[index] = val;
    r->keyCount++;
}
template<typename T, int M>
returnStatus BTree<T, M>::split_insert( BNode<T, M>* r, const T& val, BNode<T, M>*& dptr, T& dkv )
{



}
template<typename T, int M>
bool BTree<T, M>::isNodeLeaf( BNode<T, M>* node )
{
    for( int i = 0; i< M-1; i++ ){
        if( node->ptr[i] != NULL ){
            return false;
        }
    }
    return true;
}
template<typename T, int M>
returnStatus BTree<T, M>::_find( BNode<T, M>* r, const T& val )
{
    for( int i = 0; i<M; i++ ){
        if( r->ptr[i] != NULL ){
            _find( r->ptr[i], val);
        }
    }
    for( int i =0; i<r->keyCount; i++ ){
        if( r->keys[i] == val ) return duplicate;
    }
    return unsuccessful;
}
template<typename T, int M>
int BTree<T, M>::_getNodeIndex( BNode<T, M>* r, const T& val )
{
    for( int i = 0; i < r->keyCount; i++){
        if( val < r->keys[i] ){
            return i;
        }
    }
    return -1;
}

    template<typename T, int M>
void BTree<T, M>::insert( const T& val )
{
    int set = 0;
    BNode<T, M>* myNode = new BNode<T, M>();                        //May not be correct way to instantiate Reference to pointer
    returnStatus status = _insert( root, val, myNode, set);

    if( status == successful ){
        return;
    }else if( status == unsuccessful ){


    }else if( status == duplicate ){
        cout<<val<<" has already been inserted."<<endl;
    }

}
template<typename T, int M>
returnStatus BTree<T, M>::find( const T& val )
{
    returnStatus stat = _find(root, val);
    return stat;
}
template<typename T, int M>
void BTree<T, M>::remove( const T& val )
{

}
template<typename T, int M>
void BTree<T, M>::traverse()
{
    _traverse(root);
}
template<typename T, int M>
BTree<T, M>::~BTree()
{



}
4

1 に答える 1

0

次のBツリーへの挿入方法は、Bツリーへの挿入に関する疑問を明確にするのに役立つと思います。

public void insert (Comparable object)
{
if(isEmpty ())
{
    if(parent==NULL)
    {
        attachSubtree (0, new BTree(getM ()));
        key[1]=object;
        attachSubtree (1, new BTree(getM ()));
        count=1;
    }
    else
        parent.insertPair(object, new BTree (getM ()));
}

else
{
    int index = findIndex (object);
    if(index !=0 && object.isEQ (key [index])) throw new IllegalArgumentException ("duplicate key");
        subtree [index].insert(object);
}
}

これは、 「Javaのオブジェクト指向デザインパターンを使用したデータ構造とアルゴリズム」という本から抜粋したもの です。

于 2012-12-05T08:58:44.680 に答える