Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

i was trying to implement a Btree .

my first question is what will be happened if i inset a new item which is equel to root item or other leaf node item within Btree.

second question is what is the difference between using the reference pointer(just like in function declartion (node*& tree, int newitem) and pass Treelist pointer directly to insert function? i think there is no difference between them.

Code: Select all
`#include <iostream>using namespace std;struct node{   int item;   node* left;   node* right;};class Btree{   public :      Btree():Treelist(NULL){}      ~Btree();      void insertItem(int newitem);      void del(int item);      void insert(node*& tree,int item);// can i pass Treelist pointer directly into insertfuction for example void insert(node* , int )   private:      node* Treelist; // root pointer      bool isempty() {return (Treelist==NULL);}         };void Btree::insertItem (int newitem){      insert(Treelist,newitem); // assign root poiner to point at new node.}void Btree::insert (node*& tree, int newitem) // using recursive to insert new item into Btree{      if(tree==NULL) // base case of insert function    {      tree = new node;      tree->left = NULL;      tree->right = NULL;      tree->item = newitem;         }   else if (newitem > tree->item )  // if newitem is bigger than upper level node, it will be assigned to right side of Btree.    {      insert(tree->right , newitem);         }   else if( newitem < tree->item) // vice versa. recall insert function assign    {      insert(tree->left , newitem);   }   else if(newitem == tree->item)// what gonna be happened , if newitem equel to root item?    ;   }`

thanks
hehe_x_men

Posts: 11
Joined: Wed Jan 04, 2006 9:43 am
Location: ShenYang, CHN

I think usually with a B-tree (or most any other tree), the data it holds is a set containing no duplicates. Or if you needed to store duplicates, you'd have to modify your structure to count how many times a certain value had been added.

Jimbo

Posts: 601
Joined: Thu Sep 25, 2003 6:48 pm
Location: Seattle

It depends only on the way you implement it. According to Cormen's book equal values are stored to the left. (answer for your 1-st question)
frea

Posts: 75
Joined: Wed Nov 24, 2004 9:21 am