2
我想實現一個BTree的插入方法。我的BTree類包含一個指向根節點的指針。插入方法具有內部和外部方法。內部的一個還沒有遞歸，但我無法讓第二次插入的根傳入。我認爲這可能是一個範圍問題，但我不確定它到底是什麼。主要我試圖插入2個值來測試該方法，但似乎在第二次插入它仍然認爲root == null並覆蓋第一個鍵值。有誰會爲什麼會發生這種情況？插入一個節點到B樹
這裏是我的功能：
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()
{
}