B-Tree Remove Function
<p>Here is the question.I have some problems with the remove()when I solve question b).Even if I just loop 50 times, the error always happen.Could you help me check my remove function?Thank you very much?!!!
    ![enter image description here][1]</p>

<pre><code>  [1]: http://i.stack.imgur.com/N4wEm.png

#include &lt;iostream&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;


using namespace std;

const int MAX = 4 ;
const int MIN = 2 ;
struct treenode
{
    int count ;
    int value[MAX + 1] ;
    treenode *child[MAX + 1] ;
} ;
class mytree
{
    private :
        treenode *root ;
    public :
        mytree( ) ;
        // insert funtion group
        void add ( int value ) ;
        int set_value ( int value, treenode *m, int *p, treenode **n ) ;
        static treenode * search ( int value, treenode *root, int *position ) ;
        static int searchnode ( int value, treenode *m, int *position ) ;
        void fullnode ( int value, treenode *n, treenode *m, int k ) ;
        void split ( int value, treenode *n, treenode *m,int k, int *y, treenode **newnode ) ;
        // show function group
        void show( );
        static void display ( treenode *root ) ;        
        // delete function group
        void remove ( int value ) ;
        int removehelp ( int value, treenode *root ) ;
        void clear ( treenode *root, int k ) ;
        void copy_successful ( treenode *root, int i ) ;
        void restore ( treenode *root, int i ) ;
        void rightshift ( int k ) ;
        void leftshift ( int k ) ;
        void merge ( int k ) ;
        static void removetree ( treenode *root ) ;
        ~mytree( ) ;
        // search funcion group
        bool search( int value )
        {
            int position = 0;
            cout &lt;&lt; "searching for: " &lt;&lt; value &lt;&lt; endl;
            return search( value, root, &amp;position ) != NULL;
        }
} ;

mytree :: mytree( )
{
    root = NULL ;
}
void mytree :: add ( int value )
{
    int i ;
    treenode *n, *m ;
    int flag ;
    flag = set_value ( value, root, &amp;i, &amp;n ) ;
    if ( flag )
    {
        m = new treenode ;
        m -&gt; count = 1 ;
        m -&gt; value[1] = i ;
        m -&gt; child[0] = root ;
        m -&gt; child[1] = n ;
        root = m ;
    }
}
int mytree :: set_value ( int value, treenode *m, int *p, treenode **n )
{
    int k ;
    if ( m == NULL )
    {
        *p = value ;
        *n = NULL ;
        return 1 ;
    }
    else
    {
        if ( searchnode ( value, m, &amp;k ) )
            cout &lt;&lt; endl &lt;&lt; "point has already existed." &lt;&lt; endl ;
        if ( set_value ( value, m -&gt; child[k], p, n ) )
        {
            if ( m -&gt; count &lt; MAX )
            {
                fullnode ( *p, *n, m, k ) ;
                return 0 ;
            }
            else
            {
                split ( *p, *n, m, k, p, n ) ;
                return 1 ;
            }
        }
        return 0 ;
    }
}
treenode * mytree :: search ( int value, treenode *root, int *position )
{
    if ( root == NULL )
        return NULL ;
    else
    {
        if ( searchnode ( value, root, position ) )
            return root ;
        else
            return search ( value, root -&gt; child[*position], position ) ;
    }
}
int mytree :: searchnode ( int value, treenode *m, int *position )
{
    if ( value &lt; m -&gt; value[1] )
    {
        *position = 0 ;
        return 0 ;
    }
    else
    {
        *position = m -&gt; count ;
        while ( ( value &lt; m -&gt; value[*position] ) &amp;&amp; *position &gt; 1 )
            ( *position )-- ;
        if ( value == m -&gt; value[*position] )
            return 1 ;
        else
            return 0 ;
    }
}
void mytree :: fullnode ( int value, treenode *n, treenode *m, int k )
{
    int i ;
    for ( i = m -&gt; count ; i &gt; k ; i-- )
    {
        m -&gt; value[i + 1] = m -&gt; value[i] ;
        m -&gt; child[i + 1] = m -&gt; child[i] ;
    }
    m -&gt; value[k + 1] = value ;
    m -&gt; child[k + 1] = n ;
    m -&gt; count++ ;
}
void mytree :: split ( int value, treenode *n, treenode *m,
        int k, int *y, treenode **newnode )
{
    int i, mid ;

    if ( k &lt;= MIN )
        mid = MIN ;
    else
        mid = MIN + 1 ;

    *newnode = new treenode ;

    for ( i = mid + 1 ; i &lt;= MAX ; i++ )
    {
        ( *newnode ) -&gt; value[i - mid] = m -&gt; value[i] ;
        ( *newnode ) -&gt; child[i - mid] = m -&gt; child[i] ;
    }

    ( *newnode ) -&gt; count = MAX - mid ;
    m -&gt; count = mid ;

    if ( k &lt;= MIN )
        fullnode ( value, n, m, k ) ;
    else
        fullnode ( value, n, *newnode, k - mid ) ;

    *y = m -&gt; value[m -&gt; count] ;
    ( *newnode ) -&gt; child[0] = m -&gt; child[m -&gt; count] ;
    m -&gt; count-- ;
}
void mytree :: remove ( int value )
{
    treenode * temp ;

    if ( ! removehelp ( value, root ) )
        cout &lt;&lt; endl &lt;&lt; "point" &lt;&lt; value &lt;&lt; " not found." ;
    else
    {
        if ( root -&gt; count == 0 )
        {
            temp = root ;
            root = root -&gt; child[0] ;
            delete temp ;
        }
    }
}
int mytree :: removehelp ( int value, treenode *root )
{
    int i ;
    int flag ;

    if ( root == NULL )
        return 0 ;
    else
    {
        flag = searchnode ( value, root, &amp;i ) ;
        if ( flag )
        {
            if ( root -&gt; child[i - 1] )
            {
                copy_successful ( root, i ) ;
                flag = removehelp ( root -&gt; value[i], root -&gt; child[i] ) ;
                if ( !flag )
                    cout &lt;&lt; endl &lt;&lt; "point " &lt;&lt; value &lt;&lt; " not found." ;
            }
            else
                clear ( root, i ) ;
        }
        else
            flag = removehelp ( value, root -&gt; child[i] ) ;
        if ( root -&gt; child[i] != NULL )
        {
            if ( root -&gt; child[i] -&gt; count &lt; MIN )
                restore ( root, i ) ;
        }
        return flag ;
    }
}
void mytree :: clear ( treenode *root, int k )
{
    int i ;
    for ( i = k + 1 ; i &lt;= root -&gt; count ; i++ )
    {
        root -&gt; value[i - 1] = root -&gt; value[i] ;
        root -&gt; child[i - 1] = root -&gt; child[i] ;
    }
    root -&gt; count-- ;
}
void mytree :: copy_successful ( treenode *root, int i )
{
    treenode *temp = root -&gt; child[i] ;

    while ( temp -&gt; child[0] )
        temp = temp -&gt; child[0] ;

    root -&gt; value[i] = temp -&gt; value[1] ;
}
void mytree :: restore ( treenode *root, int i )
{
    if ( i == 0 )
    {
        if ( root -&gt; child [1] -&gt; count &gt; MIN )
            leftshift ( 1 ) ;
        else
            merge ( 1 ) ;
    }
    else
    {
        if ( i == root -&gt; count )
        {
            if ( root -&gt; child[i - 1] -&gt; count &gt; MIN )
                rightshift ( i ) ;
            else
                merge ( i ) ;
        }
        else
        {
            if ( root -&gt; child[i - 1] -&gt; count &gt; MIN )
                rightshift ( i ) ;
            else
            {
                if ( root -&gt; child[i + 1] -&gt; count &gt; MIN )
                    leftshift ( i + 1 ) ;
                else
                    merge ( i ) ;
            }
        }
    }
}
void mytree :: rightshift ( int k )
{
    int i ;
    treenode *temp ;

    temp = root -&gt; child[k] ;

    for ( i = temp-&gt;count ; i &gt; 0 ; i-- )
    {
        temp -&gt; value[i + 1] = temp -&gt; value[i] ;
        temp -&gt; child[i + 1] = temp -&gt; child[i] ;
    }

    temp -&gt; child[1] = temp -&gt; child[0] ;
    temp -&gt; count++ ;
    temp -&gt; value[1] = root -&gt; value[k] ;
    temp = root -&gt; child[k - 1] ;
    root -&gt; value[k] = temp -&gt; value[temp -&gt; count] ;
    root -&gt; child[k] -&gt; child [0] = temp -&gt; child[temp -&gt; count] ;
    temp -&gt; count-- ;
}
void mytree :: leftshift ( int k )
{
    treenode *temp ;

    temp = root -&gt; child[k - 1] ;
    temp -&gt; count++ ;
    temp -&gt; value[temp -&gt; count] = root -&gt; value[k] ;
    temp -&gt; child[temp -&gt; count] = root -&gt; child[k] -&gt; child[0] ;
    temp = root -&gt; child[k] ;
    root -&gt; value[k] = temp -&gt; value[1] ;
    temp -&gt; child[0] = temp -&gt; child[1] ;
    temp -&gt; count-- ;
    for ( int i = 1 ; i &lt;= temp -&gt; count ; i++ )
    {
        temp -&gt; value[i] = temp -&gt; value[i + 1] ;
        temp -&gt; child[i] = temp -&gt; child[i + 1] ;
    }
}
void mytree :: merge ( int k )
{
    treenode *temp1, *temp2 ;
    temp1 = root -&gt; child[k] ;
    temp2 = root -&gt; child[k - 1] ;
    temp2 -&gt; count++ ;
    temp2 -&gt; value[temp2 -&gt; count] = root -&gt; value[k] ;
    temp2 -&gt; child[temp2 -&gt; count] = root -&gt; child[0] ;
    for ( int i = 1 ; i &lt;= temp1 -&gt; count ; i++ )
    {
        temp2 -&gt; count++ ;
        temp2 -&gt; value[temp2 -&gt; count] = temp1 -&gt; value[i] ;
        temp2 -&gt; child[temp2 -&gt; count] = temp1 -&gt; child[i] ;
    }
    for ( int i = k ; i &lt; root -&gt; count ; i++ )
    {
        root -&gt; value[i] = root -&gt; value[i + 1] ;
        root -&gt; child[i] = root -&gt; child[i + 1] ;
    }
    root -&gt; count-- ;
    delete temp1 ;
}
void mytree :: show( )
{
    display ( root ) ;
}
void mytree :: display ( treenode *root )
{

    if ( root != NULL )
    {
        for ( int i = 0 ; i &lt; root -&gt; count ; i++ )
        {
            display ( root -&gt; child[i] ) ;
            std::cout &lt;&lt; root -&gt; value[i + 1] &lt;&lt; "\t" ;
        }
    }
}
void mytree :: removetree ( treenode *root )
{
    if ( root != NULL )
    {
        for ( int i = 0 ; i &lt; root -&gt; count ; i++ )
        {
            removetree ( root -&gt; child[i] ) ;
            delete ( root -&gt; child[i] ) ;
        }
    }
}

mytree :: ~mytree( )
{
    removetree ( root ) ;
}

void main( )
{
    mytree b ;
    srand(time(NULL));
    int arr[100000];
    for(int i=0;i!=100;i++)
    {
        arr[i]=rand()%1000+1;
        b.add(arr[i]);
    }
        cout &lt;&lt; "B-tree of order 5:" &lt;&lt; endl ;
        b.show();

    for(int j=0;j!=50;j++)
    b.remove(rand()%10+1);
    cout &lt;&lt; "\n\nB-tree after deletion of values:" &lt;&lt; endl ;
    b.show();
    cout&lt;&lt;endl;
    for(int k=0;k!=10;k++)
    {
        arr[k]=rand()%1000+1;
        if(b.search(arr[k]))
            cout&lt;&lt;arr[k]&lt;&lt;"in the btree"&lt;&lt;endl;
        else
            cout&lt;&lt;arr[k]&lt;&lt;"is not in the btree"&lt;&lt;endl;
        continue;
    }

    cout&lt;&lt;endl;
    system("pause");

}
</code></pre>
