By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,501 Members | 1,266 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,501 IT Pros & Developers. It's quick & easy.

simple question about B tree

P: n/a
Hi I am relearning datastructure... but got kinda stuck in a basic
delete node operation. what it does is to delete the first node it
finds when the item is equal the input item. the end result is that the
node is deleted and the b-tree is still kept as b-tree. CAn someone
critique on my implementation?
Any suggestion for improvement? Thanks

The code I have as follows:

#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isleafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
//Helper functions
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
//Helper functions
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isLeafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}

int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
int Btree::removeNode(Node* cur, int item){
int ret=0;

if(!cur) { ret =0;}
else {
if(cur->value == item) {
/*get rid of node*/
// if there is a left child
// keep promoting the left child up as long as it has one.
if (isLeafNode(cur)){ delete cur;} // if I am leaf node delete
myself
else {
// do I have a left node? yes promote,
// get rid of the last one in chain
while (cur->left)
{
swap(cur,cur->left);
cur=cur->left;
}
while (cur->right) {
swap(cur,cur->right);
cur=cur->right;
}
//should be leaf node pointed by cur
if(isLeafNode(cur)){delete cur;}
// no promote right node
// get rid of the last one in chain

}
}
else{
//if item < cur->value, tell left to do the deletion,
// else tell right
if (item<cur->value)
removeNode(cur->left,item);
else
removeNode(cur->right,item);

}
}
return ret;
}

Nov 28 '06 #1
Share this Question
Share on Google+
3 Replies


P: n/a

as*********@gmail.com wrote:
Hi I am relearning datastructure... but got kinda stuck in a basic
delete node operation. what it does is to delete the first node it
finds when the item is equal the input item. the end result is that the
node is deleted and the b-tree is still kept as b-tree. CAn someone
critique on my implementation?
Any suggestion for improvement? Thanks

The code I have as follows:

#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isleafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
//Helper functions
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
//Helper functions
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isLeafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}

int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
int Btree::removeNode(Node* cur, int item){
int ret=0;

if(!cur) { ret =0;}
else {
if(cur->value == item) {
/*get rid of node*/
// if there is a left child
// keep promoting the left child up as long as it has one.
if (isLeafNode(cur)){ delete cur;} // if I am leaf node delete
myself
else {
// do I have a left node? yes promote,
// get rid of the last one in chain
while (cur->left)
{
swap(cur,cur->left);
cur=cur->left;
}
while (cur->right) {
swap(cur,cur->right);
cur=cur->right;
}
//should be leaf node pointed by cur
if(isLeafNode(cur)){delete cur;}
// no promote right node
// get rid of the last one in chain

}
}
else{
//if item < cur->value, tell left to do the deletion,
// else tell right
if (item<cur->value)
removeNode(cur->left,item);
else
removeNode(cur->right,item);

}
}
return ret;
I havent stepped through the code to really see whether it works or not
but the first thing that struck me is where are you maintaining the
order of the B-tree ?

Let's assume you have a b-tree with order 3 and the intermediate nodes
have only 2 keys and you delete one of them ...then how to do you
maintian the order.
your implementation looks more like a binary tree with the adjustment
made only for swapping keys at the same level...but not across levels.
}
Nov 28 '06 #2

P: n/a
I was thinking that since BTree is already sorted. So instead of doing
the pointer manipulation, I could just do the following:
--- if the item is in a leaf node - delete the node. and then I am done
-- if the item is in a node that has 2 children, I swap the value fo
the left child (which is always smaller then the parent node --which
has the *value* I want to delete, and keep pushing it down until it
hits the leftmost leafnode. then I delete the leftmost leaf node.
-- if there is no left node but right node, then I push the *value" I
want to delete down until it is leaft node then I delete.
The core is that because deleting the leaf node is easy. so in order to
fill the hole, I need to push down the value down the path until it
hits the leaf node. And I also assume that th b-tree is already sorted.

do u think it will work? can u give some the implementation? thanks

am******@gmail.com wrote:
as*********@gmail.com wrote:
Hi I am relearning datastructure... but got kinda stuck in a basic
delete node operation. what it does is to delete the first node it
finds when the item is equal the input item. the end result is that the
node is deleted and the b-tree is still kept as b-tree. CAn someone
critique on my implementation?
Any suggestion for improvement? Thanks

The code I have as follows:

#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isleafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
//Helper functions
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
//Helper functions
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
#include <iostream>
using namespace std;
class Btree;

class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};

class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isLeafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}

int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
int Btree::removeNode(Node* cur, int item){
int ret=0;

if(!cur) { ret =0;}
else {
if(cur->value == item) {
/*get rid of node*/
// if there is a left child
// keep promoting the left child up as long as it has one.
if (isLeafNode(cur)){ delete cur;} // if I am leaf node delete
myself
else {
// do I have a left node? yes promote,
// get rid of the last one in chain
while (cur->left)
{
swap(cur,cur->left);
cur=cur->left;
}
while (cur->right) {
swap(cur,cur->right);
cur=cur->right;
}
//should be leaf node pointed by cur
if(isLeafNode(cur)){delete cur;}
// no promote right node
// get rid of the last one in chain

}
}
else{
//if item < cur->value, tell left to do the deletion,
// else tell right
if (item<cur->value)
removeNode(cur->left,item);
else
removeNode(cur->right,item);

}
}
return ret;

I havent stepped through the code to really see whether it works or not
but the first thing that struck me is where are you maintaining the
order of the B-tree ?

Let's assume you have a b-tree with order 3 and the intermediate nodes
have only 2 keys and you delete one of them ...then how to do you
maintian the order.
your implementation looks more like a binary tree with the adjustment
made only for swapping keys at the same level...but not across levels.
}
Nov 28 '06 #3

P: n/a
as*********@gmail.com wrote:
I was thinking that since BTree is already sorted.


Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or the group FAQ list:
<http://www.parashift.com/c++-faq-lite/how-to-post.html>
Nov 28 '06 #4

This discussion thread is closed

Replies have been disabled for this discussion.