A bug in AVL tree deletion !!! Help pls !!

swizzy (1)
Watz wrong with this avl tree deletion code ??

A node with a single child alone gets deleted..

But then for other nodes the program stops working and terminates abruptly as such..

i.e. abnormal termination as error report while such nodes are entered to be deleted..

Cud someone help me out ??

Cudn find out wy such error reports are popped !!

Here is my c++ code for avl deletion.. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
void remove(const comparable & x,avlnode* & r)
        {
                   if(r==NULL)
                              cout<<"\nNo element !!!";
                   else if(x<r->element)
                   {
                              remove(x,r->left);
                              if(avlheight(r->right)-avlheight(r->left)>1)
                                     if(avlheight(r->right->right)>=avlheight(r->right->left))
                                                 rotatewithright(r);
                                     else
                                                 doublewithright(r);
                   }
                   else if(x>r->element)
                   {
                              remove(x,r->right);
                              if(avlheight(r->left)-avlheight(r->right)>1)
                                     if(avlheight(r->left->left)>=avlheight(r->left->right))
                                                 rotatewithleft(r);
                                     else
                                                 doublewithleft(r);
                   }
                   else if(r->left!=NULL&&r->right!=NULL)
                   {
                        r->element=findmin(r->right)->element;
                        remove(r->element,r->right);
                   }
                   else
                   {
                       avlnode *oldnode=r;
                       r=(r->left!=NULL)?r->left:r->right;
                       delete oldnode;
                   }
                   r->height=max(avlheight(r->left),avlheight(r->right))+1;
              }
diedrexler (33)
Pasting a fairly complicated function without providing the data structure definition on which it operates would not help anyone in aiding you. What i would suggest is that you set a breakpoint within the function implementation and carefully step through it whilst keeping a watch on the avlnode to see what happens after each and every step.

NB: a faster way to help you will be to get Boost(or any C++ test package) and write a couple of test cases to ensure that each and every function you will eventually be using on the tree meets the desired functionality. It might be that your remove function is correct, but another function involved in building the tree messes up the internal pointer assignments.
Topic archived. No new replies allowed.