Вставка узла в B-дерево

Я пытаюсь реализовать метод вставки для BTree. Мой класс BTree содержит указатель на корневой BNode. Метод вставки имеет как внутренний, так и внешний метод. Внутренний еще не рекурсивен, но у меня возникли проблемы с передачей корня в качестве значения для второй вставки. Я думаю, что это может быть проблемой, но я не уверен, что именно. В основном я попытался вставить 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()
{}