C++

Forum

 
AVL deletion when node has no children or 2 children

trevormoon (45)
Hey guys I'm working on my deletion function for my AVL tree and cannot seem to figure out how to make it work correctly. I think my main issue lies in my implementation when a node either has 2 or 0 children. Any tips on what I'm doing wrong would be greatly appreciated.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
 template <class Record>
Error_code AVL_tree<Record>::avl_delete(Binary_node<Record>* &sub_root,
           const Record &old_data, bool &shorter)
{
  Error_code result = success;
        cout << sub_root->data << " and " << old_data << " and " << shorter <<endl;
        if (sub_root == NULL) { // root is empty.
              result = not_present;
              shorter = false;
              cout<<"sub_root = false";
        }

        else if (old_data > sub_root->data){

                cout << "DEBUG:olddata greater" << endl;
                return avl_delete(sub_root->right, old_data, shorter);
        }
        else if (old_data < sub_root->data){
                cout << "DEBUG:old data lessthan" << endl;
                return avl_delete(sub_root->left, old_data, shorter);
        }

         else if(sub_root->data == old_data){
                cout << "DEBUG:deleted root" << endl;
                Binary_node<Record> *temp_node = sub_root;

                   if(sub_root->right == NULL & sub_root->left == NULL){
                     shorter = true;
                    }


               else if(sub_root->right == NULL){
                        sub_root = sub_root->left;
                        shorter = true;
                        delete temp_node;
                }
                else if(sub_root->left == NULL){
                        sub_root = sub_root->right;
                        shorter = true;
                        delete temp_node;
                }
                else{//two children are present

                         Binary_node<Record> *pre_node = sub_root->left;
               while(pre_node->right != NULL){
                  pre_node = pre_node->right;
               }
               sub_root->data = pre_node->data;
                 cout<<"prenode data" <<pre_node->data<< "  " << "subroot data" << sub_root->data<<endl;
                 cout<<"prenode->left " << pre_node->left<<endl;
                 delete pre_node;
                 sub_root->left = pre_node->left;
                   shorter = true;
  //                  avl_delete(sub_root->left, sub_root->data,shorter);

                 //    sub_root->data = avl_delete(sub_root->right, old_data, shorter);
                 cout<<"sub root is1  " <<sub_root->data <<endl;
                }
        }

         if (shorter == true){
                 cout<<"sub root is " <<sub_root->data <<endl;
                cout << "else shorter true" << endl;
                cout <<"subroot balance is " << sub_root->get_balance()<<endl;
                switch (sub_root->get_balance()) {
                        case equal_height:
                                sub_root->set_balance(right_higher);
                                shorter = false;
                                delete sub_root;
                                break;
                        case left_higher:
                                sub_root->set_balance(equal_height);
                                break;
                        case right_higher:
                                switch (sub_root->right->get_balance()) {
                                        case equal_height:
                                                rotate_left(sub_root);
                                                sub_root->set_balance(left_higher);
                                                sub_root->left->set_balance(right_higher);
                                                shorter = false;
                                                break;
                                        case right_higher:
                                                rotate_left(sub_root);
                                                sub_root->set_balance(equal_height);
                                                sub_root->left->set_balance(equal_height);
                                                break;
                                        case left_higher:
                                                rotate_left(sub_root);
                                                rotate_right(sub_root->right);
                                                sub_root->set_balance(equal_height);
                                                break;
                                }
                }
        }
    return result;
}


Topic archived. No new replies allowed.