pointers out of control..

[DrJones]

I am trying to implement these rotation described
https://github.com/jonnyhsy/splay-tree/blob/master/splay.cpp
using this struct and class.

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*);
void zig(splay_node*);
string path;
};

but for some reason i get mixed up with the pointers, and don't seem to able to do it correctly, so what am i doing wrong.


My implementation
splay_node* temp = pointer;
pointer = temp->right;
temp->right = temp->parent;

Problem is root.. it get doesn't get changed, and even when i overwrite it.

[helios]

You're not updating the parent pointer of each node during the rotation, so you end up with a messed up graph that doesn't respect the assumptions
IF node->right != null THEN node->right->parent == node
IF node->left != null THEN node->left->parent == node

[DrJones]

makes sense but how would a full rotation look for you, and what do you do if it is root ??

are comparing or assigning?

pointer points to the value which has to become the new root.

[helios]

That's for you to figure out.

[DrJones]

ok.. I hope you might of some assistance

I tried implementation zig like this, and tried testing for an splay tree 5->4->3, in which i find(3) and therefor has to splay it to the root using zigzig.

i've implemented like this

splay_node* splay_tree::zig(splay_node*pointer->parent)
{
    splay_node* temp = pointer->left;
    pointer->left = temp->right;
    if (pointer->left != NULL) {
        pointer->left->parent = temp;

    }
    
    temp->right = pointer;
    temp->parent = pointer->parent;
    
    if (pointer->parent == NULL)
    {
        pointer->parent = temp;
        root = temp;
        root->parent = NULL;
    }
    else
    {
        pointer->parent = temp;
        temp->parent->left = temp;

    }
    
    
    cout <<"root is: " << root->value << endl;
    cout << endl;
    return temp;
    
}

but for some reason is the node 4 missing when the splaying is done, i've tried fixing with if's but it becomes more and more an hardcoded solution rather than general solution.. Could anyone help with a solution to keep node containing value 4 in the splay tree??

[helios]

It'd probably be a lot easier if you just get rid of the pointer to the parent.

[DrJones]

but that's usually a party of the splay tree.. it has to know it's parent..

[helios]

The code in the link you posted earlier seems to do quite alright without the parent.