C++

Forum

 
Why is this happening??

DrJones (156)
I am trying to code a splay tree, for which i try to map the path from node to tree root. the problem is though that the mapping sequence gets called multiple times depending on which level the node is in => from what i can see by debugging.

So if the node is in heigh level 2 => the path function will printout the path and insert the node twice at the same location.

I have no idea why it is doing so, so i was hoping some of you might have an answer.


This is the code and the execution.

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
#include <iostream>
#include <string>
using namespace std;

//----------------------------------------------------------------//

struct splay_node{
    int value;
    splay_node* left;
    splay_node* right;
    splay_node* parent;
};

class splay_tree{
public:
    splay_tree(int);
    splay_node *a;
    splay_node *root;
    void insert(int);
    void display(splay_node*);
private:
    void insertp(splay_node*, int);
    void splayingp(splay_node*,int);
};

splay_tree::splay_tree(int i) : a(new splay_node)
{
    a = new splay_node;
    a->value = i;
    a->left = NULL;
    a->right = NULL;
    a->parent = NULL;
    root = a;
    cout << "Splay tree created root being " << root->value << endl;
    
}

void splay_tree::insert(int i)
{
    
    insertp(root, i);
    
}
void splay_tree::insertp(splay_node *pointer,int i)
{
    if (i < pointer->value) {
        if (pointer->left != NULL) {
            insertp(pointer->left, i);
        }else
        {
            a = new splay_node;
            a->value = i;
            pointer->left = a;
            a->left = NULL;
            a->right = NULL;
            a->parent = pointer;
            
        }
        
    }
    else if (i>pointer->value){
        if (pointer->right != NULL) {
            insertp(pointer->right, i);
        }
        else
        {
            a = new splay_node;
            a->value = i;
            pointer->right = a;
            a->left = NULL;
            a->right = NULL;
            a->parent = pointer;

        }
    }
    else
    {
        cout << "Value " << i << " Is already in the tree" << endl;
    }
    
    cout << "value " << i << " has been inserted" << endl;
    splayingp(a,i);
}

void splay_tree::display(splay_node *root){
    
    if(root != NULL)
    {
        
        display(root->left);
        cout << root -> value << " " ;
        display(root -> right);

    }
    
}


void splay_tree::splayingp(splay_node *pointer, int value)
{

    int level = 0;
    string path;
    
    while (pointer->parent != NULL) {
        if (pointer->parent != NULL) {
            level++;
            if (pointer->parent -> left == pointer) {
                path.push_back('L');
            }
            if (pointer->parent->right == pointer) {
                path.push_back('R');
            }
        }
        pointer = pointer->parent;
    }

    cout << "level: " << level << endl;
    cout << path << endl;

 }

int main(int argc, const char * argv[]){

    
    splay_tree splayed(5);
    cout << endl;
    splayed.insert(3);
    cout << endl;
    splayed.insert(4);
    cout << endl;
    splayed.insert(2);
    cout << endl;
    splayed.insert(1);
    splayed.display(splayed.root);
    
    cout << endl;
    cout << splayed.root->left->right->parent->value << endl;
 
    
    return 0;
}


And the output


Splay tree created root being 5

value 3 has been inserted
level: 1
L

value 4 has been inserted
level: 2
RL
value 4 has been inserted
level: 2
RL

value 2 has been inserted
level: 2
LL
value 2 has been inserted
level: 2
LL

value 1 has been inserted
level: 3
LLL
value 1 has been inserted
level: 3
LLL
value 1 has been inserted
level: 3
LLL
1 2 3 4 5 
3
Program ended with exit code: 0
Last edited on
helios (17575)
You probably want a return after the recursive calls to insertp().
DrJones (156)
but this is a void function.. so i don't see the reason for a return?
Or Am i misunderstanding something?
Last edited on
helios (17575)
Follow the code. What will happen after the recursive call returns?
DrJones (156)
I tried follow the code using the debugger in Xcode, and it seem to jump back to the else statement without any reason..

I really don't see the problem.

Last edited on
helios (17575)
When a function returns, its caller continues executing the code that immediately follows the call. When the deepest recursive insertp() returns, the control flow will not resume in insert(), it will resume in insertp() and continue executing that function.
For example, a sample run might be

Call to insertp() (first call)
Line 46
Line 47
Line 48
Call to insertp() (second call)
Line 46
Line 61
Line 76
Line 81
Line 82
Call to splayingp()
(Omitted)
splayingp() returns
Execution of insertp() (second call) resumes
Line 83
insertp() (second call) returns
Execution of insertp() (first call) resumes
Line 49
Line 81
Line 82
Call to splayingp()
(Omitted)
splayingp() returns
Execution of insertp() (first call) resumes
insertp() (first call) returns

You need a return statement after the recursive calls to avoid calling splayingp() repeatedly.
DrJones (156)
So what kind of return are you thinking about..
helios (17575)
For example,
1
2
3
4
5
6
 
void fact(int n, int &result){
    if (n < 2)
        return;
    result *= n;
    fact(n - 1, result);
}
DrJones (156)
Even if I return it still does the same thing.

You want me to return before i recall the function or after?

-Edit
Got it! -> after the recursive call (duh!)

Last edited on
Topic archived. No new replies allowed.