simple question about B tree

Discussion in 'C++' started by asianmuscle@gmail.com, Nov 28, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Guest

    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, 2006
    #2
    1. Advertising

  3. Guest

    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

    wrote:
    > 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, 2006
    #3
  4. Default User Guest

    Re: simple question about B tree (TPA)

    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>
    Default User, Nov 28, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    2
    Views:
    1,582
    Roedy Green
    Aug 16, 2005
  2. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    0
    Views:
    419
    Ramkumar Menon
    Aug 16, 2005
  3. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    1
    Views:
    436
    Andrew Thompson
    Aug 16, 2005
  4. Joris Gillis
    Replies:
    2
    Views:
    1,520
    Joris Gillis
    Jun 16, 2006
  5. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,087
Loading...

Share This Page