The Tree

This is a discussion on The Tree within the C++ Programming forums, part of the General Programming Boards category; THough this algorithm is done by me using C++ i posted it here since it was an algorithm question and ...

  1. #1
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    The Tree

    THough this algorithm is done by me using C++ i posted it here since it was an algorithm question and not a language one..


    I have built a b-Tree.. the code is as below.. The B-Tee(not Binary tree) works fine when i enter the following numbers 20,40,10,30,15,35,7,26,18 but when i enter the next number 22, somehow the tree gets all screwed up..... I even worked out this in my book.. logically nothing wrog should happen it should insert fine..

    The tree is of order 1(for building purpose)

    till i enter 22 the following tree is built

    Code:
                                  |20|   |  |  
                                  | ,  |   |  |    |
                                   ,               '
                                 ,                      '
                            ,                             '
                       |10|   |  |                       |35|   |  |  
                       |    |   |  |   |                   |    |   |  |   | 
                       ,             '                          '            '
                     ,                '                         '              '
                    ,                    '                      '                  '
                   |7  |   |  |       |15|18|  |         |26|30|  |    |40|  |  |
    but after entering the next number 22 the tree is not stable.i.e it has the values placed in the wrong nodes... I am even making sure that if a split results in an overfull node the split continues...



    my prog code is.. I know my prog style is bad.. But i am desperate to find the above mentioned bug in my code...


    Code:
    # include <iostream.h>
    # include <conio.h>
    # include <process.h>
    
    # define SUCCESS 1
    # define FAIL 0
    
    class btree
    	{
    		private:
    			struct tree
    				{
    				int val[3];
    				struct btree::tree *node[4];
    				struct btree::tree *parent;
    				int num;
    				};
    
    			struct btree::tree *root;
    			struct btree::tree *tins;
    
    
    
    			btree::tree* init(btree::tree*);
    			display(struct btree::tree*);
    			put(int,btree::tree*);
    			btree::tree* sort(btree::tree*);
    			btree::tree* getnode(int,btree::tree*);
    			btree::tree* getnode(int);
    			duplicate(int,struct btree::tree*);
    			dupe(int);
    
    
    
    		public:
    			btree();
    			disp();
    			insert(int);
    			split(btree::tree*);
    
    
    
    	};
    
    
    btree::insert(int num)
    {
    if(dupe(num)==FAIL)
    return FAIL;
    tins=getnode(num);
    put(num,tins);
    tins=NULL;
    return SUCCESS;
    }
    
    btree::disp()
    {
    return display(root);
    }
    
    
    btree::dupe(int num)
    {
    return duplicate(num,root);
    }
    
    btree::tree* btree::getnode(int num)
    {
     return getnode(num,root);
    }
    
    
    btree::tree* btree::getnode(int num,btree::tree* temp)
    {
    for(int i=0;i<temp->num;i++)
    {
    if(temp->val[i]>num)
    {
     if(temp->node[i]!=NULL)
     return getnode(num,temp->node[i]);
     else
     return temp;
    
    }
    
    }
    
    if(temp->node[3]!=NULL)
    return getnode(num,temp->node[3]);
    
    return temp;
    }
    
    
    btree::tree* btree::sort(btree::tree *temp)
    {
    if(temp==NULL)
    return FAIL;
    int tn=0;
    struct btree::tree *tt=NULL;
    
    for(int i=0;i<temp->num;i++)
    {
     for(int j=i+1;j<temp->num;j++)
     {
     if(temp->val[i]>temp->val[j])
     {
     tn=temp->val[i];
     tt=temp->node[i];
    
     temp->val[i]=temp->val[j];
     temp->node[i]=temp->node[j];
    
     temp->val[j]=tn;
     temp->node[j]=tt;
     tt=NULL;
     }
    
     }
    }
    
    return temp;
    }
    
    btree::split(btree::tree *temp)
    {
    temp=sort(temp);
    if(temp->num<3)
    return SUCCESS;
    
    if(temp->parent==NULL)
    {
    struct btree::tree* thead=NULL;
    struct btree::tree* tsplit=NULL;
    thead=init(thead);
    tsplit=init(tsplit);
    
    thead->val[0]=temp->val[1];
    thead->node[0]=temp;
    thead->node[3]=tsplit;
    thead->parent=NULL;
    thead->num=1;
    thead=sort(thead);
    root=thead;
    
    
    tsplit->val[0]=temp->val[2];
    tsplit->node[0]=temp->node[2];
    tsplit->num=1;
    
    tsplit->node[3]=temp->node[3];
    tsplit->parent=thead;
    
    tsplit=sort(tsplit);
    
    temp->val[1]=NULL;
    temp->num--;
    
    temp->val[2]=NULL;
    temp->num--;
    
    temp->node[3]=temp->node[1];
    temp->node[1]=NULL;
    temp->node[2]=NULL;
    temp->parent=thead;
    
    
    return SUCCESS;
    }
    else
    {
    temp=sort(temp);
    struct btree::tree* tsplit=NULL;
    tsplit=init(tsplit);
    
    tsplit->val[0]=temp->val[2];
    tsplit->num++;
    
    if(temp->node[2]!=NULL)
    tsplit->node[0]=temp->node[2];
    
    tsplit->parent=temp->parent;
    
    if(temp->node[3]!=NULL)
    tsplit->node[3]=temp->node[3];
    
    for(int i=0;i<4;i++)
    {
     if(temp->parent->node[i]==temp)
     {
     temp->parent->node[i]=tsplit;
     break;
     }
    }
    
    temp->parent->val[temp->parent->num]=temp->val[1];
    temp->parent->node[temp->parent->num]=temp;
    temp->parent->num++;
    
    sort(temp->parent);
    
    temp->node[3]=temp->node[1];
    temp->num=1;
    temp->val[1]=NULL;
    temp->val[2]=NULL;
    temp->node[1]=NULL;
    temp->node[2]=NULL;
    sort(temp->parent);
    
    if(tsplit->parent->num>2)
    return split(temp->parent);
    
    
    return SUCCESS;
    }
    
    
    
    
    }
    
    btree::put(int num,btree::tree *temp)
    {
    if(temp->num<3)
    {
    temp->val[temp->num]=num;
    temp->num++;
    temp=sort(temp);
    
    if(temp->num>=3)
    split(temp);
    
    return SUCCESS;
    }
    return FAIL;
    }
    
    
    btree::display(btree::tree *temp)
    {
    cout<<"\n";
    for(int i=0;i<temp->num;i++)
    {
     cout<<temp->val[i]<<" ";
    }
    
    for(i=0;i<4;i++)
    {
    if(temp->node[i]!=NULL)
    display(temp->node[i]);
    }
    
    
    return SUCCESS;
    }
    
    
    
    btree::duplicate(int num,btree::tree *temp)
    {
    
    for(int i=0;i<3;i++)
    {
     if(temp->val[i]==num)
     return FAIL;
    }
    
    for(i=0;i<4;i++)
    {
    if(temp->node[i]!=NULL)
    {
    if(duplicate(num,temp->node[i])==FAIL)
    return FAIL;
    }
    }
    
    
    
    return SUCCESS;
    }
    
    
    
    btree::btree()
    {
    root=NULL;
    root=init(root);
    }
    
    btree::tree* btree::init(btree::tree* temp)
    {
    temp=new btree::tree;
    temp->num=0;
    temp->parent=NULL;
    for(int i=0;i<4;i++)
    {
    temp->node[i]=NULL;
    if(i<3)
    temp->val[i]=NULL;
    }
    
    return temp;
    }
    
    
    
    
    /*
    int main()
    {
    clrscr();
    btree b;
    b.disp();
    
    
    return 0;
    } */
    
    
    
    int main()
    {
    int option=100;
    btree b;
    int num;
    while(option!=3)
    {
    clrscr();
    cout<<"\nM E N U";
    cout<<"\n_______";
    cout<<"\n\n\n1) Insert into B-Tree";
    cout<<"\n\n2) Display B-Tree";
    cout<<"\n\n3) Exit";
    cout<<"\n\n\nOption > ";
    cin>>option;
    clrscr();
    if(option==2)
    {
    b.disp();
    getch();
    }
    
    if(option==1)
    {
     cout<<"\nEnter the number to be inserted > ";
     cin>>num;
     if(b.insert(num)==FAIL)
     cout<<"\nDuplicate entry...";
     else
     cout<<"\nInserted...";
     getch();
    }
    
    
    
    
    }
    
    
    return 0;
    }

    Thanx in advance

  2. #2
    5|-|1+|-|34|) ober's Avatar
    Join Date
    Aug 2001
    Posts
    4,429
    Algorithm or code question, I still don't think this is a GD question.

  3. #3
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    Thou shalt not posteth code in GD.

  4. #4
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Well.. found the problem.. It was a silly problem where i did not update the parent pointer when a node split.. Now i am planing to generalize this class and make in an M orde B Tree..

    Bye

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21