Problem with my deletion function in binary tree

Netaro (1)
Ok, so, I've decided to write a binary tree. As for now, it's an unbalanced binary tree, the simplest one. Adding elements works (keys cannot appear more than once), writing them in order works. Deleting them does not.

For example, consider adding 10 (root), then 20, 30, 40, 50 (all of them - right sons. Deleting root itself works. and 20 becomes root. SO, i guess there's no error there. However, let's delete 50, then 40, then 30, then 20... Uuups, it won't delete 20, and trying to delete it again will result in a double-deletion error. Or it won't delete a piece with two sons. Sometimes it works, sometimes it doesn't. And sometimes it will delete something completely different!

The deletion function of a controller class (BinaryTreeController) looks like this (it's a standard algorithm that finds a node to delete by key, checks number of sons, if none, parent outgoing node <- NULL, if one, parent outgoing node <- the only son of a node, if two, it finds a minimal of right son, sets it as key, and deletes the minimal value.

It works well on handy pen&paper debugging tool. It doesn't work on my PC (one scenario when it doesn't work is shown above) :(

The code itself - 

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
void BinaryTreeController::deleteValue(int valueToDelete){
       
        binaryTreeNode* nodeToDelete = NULL;
        root->find(valueToDelete,&nodeToDelete);
       
        if(nodeToDelete == NULL){
                return;
        }
        //WYGLADA NA TO ZE DZIALA
       
        if(nodeToDelete == root){
                int numOfChildren = root->countChildren();
                if(numOfChildren == 0){
                        delete root;
                        root = NULL;
                        return;
                }
                else if(numOfChildren == 1){
                        root = root->returnOnlyChild();
                        nodeToDelete->clearConnections();
                        delete nodeToDelete;
                        return;
                }
                else if(numOfChildren == 2){
                        binaryTreeNode* minimalNode = root->right->min();
                        //root->right->min(&minimalNode);
                        if(minimalNode != NULL){
                                root->key = minimalNode->key;
                                int numOfMinimalNodeChildren = minimalNode->countChildren();
                                if(numOfMinimalNodeChildren == 0){
                                        if(minimalNode == minimalNode->parent->left){
                                                minimalNode->parent->left = NULL;
                                        }
                                        else {
                                                minimalNode->parent->right = NULL;
                                        }
                                        minimalNode->clearConnections();
                                        delete minimalNode;
                                        return;
                                }
                                else{
                                        if(minimalNode == minimalNode->parent->left){
                                                minimalNode->parent->left = minimalNode->returnOnlyChild();
                                        }
                                        else {
                                                minimalNode->parent->right = minimalNode->returnOnlyChild();
                                        }
                                        minimalNode->clearConnections();
                                        delete minimalNode;
                                        return;
                                }
                        }
                }
        }
        //MOZE NIE DZIALAC
        else if(nodeToDelete != root){
                int numOfChildren = nodeToDelete->countChildren();
                if(numOfChildren == 0){
                        if(nodeToDelete == nodeToDelete->parent->left){
                                nodeToDelete->parent->left = NULL;
                        }
                        else{
                                nodeToDelete->parent->right = NULL;
                        }
                        nodeToDelete->clearConnections();
                        delete nodeToDelete;
                        return;
                }
                else if(numOfChildren == 1){
                        if(nodeToDelete == nodeToDelete->parent->left){
                                nodeToDelete->parent->left = nodeToDelete->returnOnlyChild();
                        }
                        else{
                                nodeToDelete->parent->right = nodeToDelete->returnOnlyChild();
                        }
                        nodeToDelete->clearConnections();
                        delete nodeToDelete;
                        return;
                }
                else if(numOfChildren == 2){
                        binaryTreeNode* minimalNode = nodeToDelete->right->min();
                        if(minimalNode != NULL){
                                nodeToDelete->key = minimalNode->key;
                                int numOfMinimalNodeChildren = minimalNode->countChildren();
                                if(numOfMinimalNodeChildren == 0){
                                        if(minimalNode == minimalNode->parent->left){
                                                minimalNode->parent->left = NULL;
                                        }
                                        else {
                                                minimalNode->parent->right = NULL;
                                        }
                                        minimalNode->clearConnections();
                                        delete minimalNode;
                                        return;
                                }
                                else if(numOfMinimalNodeChildren == 1){
                                        if(minimalNode == minimalNode->parent->left){
                                                minimalNode->parent->left = minimalNode->returnOnlyChild();
                                        }
                                        else {
                                                minimalNode->parent->right = minimalNode->returnOnlyChild();
                                        }
                                        minimalNode->clearConnections();
                                        delete minimalNode;
                                        return;
                                }
                                else{
                                        minimalNode->clearConnections();
                                        delete minimalNode;
                                }
                        }
                }
        }

}


The code of that project is there -> http://pastebin.com/JNjb9WPV. First, you give number of commands, then , for example 'a 10' inserts 10 into tree, 'w' writes all in order, then 'd 10' should (in theory) delete key 10.

I'll be very grateful for any kind of help.
Last edited on
Topic archived. No new replies allowed.