Make a map using a splay tree

In my data structures and algorithms class, we were introduced to the splay tree, a BST with the additional property that recently accessed elements are quick to access (because they stay at the top of the tree until a different element is accessed).

I know that std::map uses a BST; I heard it's a Red-Black Tree.

Anyway, I thought I'd implement my own map using the splay tree idea, and I'd like to know what people think of my implementation. Does it look efficient? Is it readable?

```
#ifndef SplayTree_ms_map_h
#define SplayTree_ms_map_h

#include
#include
#include

namespace ms {
template
class map {
protected:
class Node {
public:
Node *llink = NULL;
Node *rlink = NULL;
Node *parent = NULL;
KeyType key;
ValueType value;

void left_rotate() {
assert(parent != NULL);
assert(parent->rlink = this);

Node *t2 = llink;
Node *p = parent;
Node *gp = p->parent;

if (gp != NULL) {
if (gp->llink == parent) {
gp->llink = this;
}
else {
assert(gp->rlink = parent);
gp->rlink = this;
}
parent = gp;
}
else {
parent = NULL;
}

p->rlink = t2;
if (t2 != NULL) {
p->rlink->parent = p;
}
llink = p;
llink->parent = this;
}

void right_rotate() {
assert(parent != NULL);
assert(parent->llink = this);

Node *t2 = rlink;
Node *p = parent;
Node *gp = p->parent;

if (gp != NULL) {
if (gp->llink == parent) {
gp->llink = this;
}
else {
assert(gp->rlink = parent);
gp->rlink = this;
}

It would be better to separate the class interface declaration from the implementation. The declaration would serve as a nice overview of the class's functionality, and it's the recommended practice anyway, for information hiding.
This is especially important when you also have inner classes,
and member variables declared in unusual order (between methods),
like root.

I suggest to use K, V as the template parameter names instead of KeyType, ValueType. K, V are commonly used and understood as key-value types. When I see KeyType without the declaration, my first thought is that it's a typedef. But it's actually a template type parameter, which is different. It's confusing.

llink and rlink are not so good names. By that logic you should suffix all pointers with link. I suggest to rename to left and right, that would be perfectly understandable, and more readable.

I would also rename left_rotate and right_rotate to rotate_left and rotate_right. It seems more straightforward, and sound more like actions.

Declare variables closer to where they are actually used.
In this code:

Node *t2 = llink;
Node *p  = parent;
Node *gp = p->parent;

if (gp != NULL) {
    if (gp->llink == parent) {
        gp->llink = this;
    }
    else {
        assert(gp->rlink = parent);
        gp->rlink = this;
    }
    parent = gp;
}
else {
    parent = NULL;
}

p->rlink = t2;
if (t2 != NULL) {
    p->rlink->parent = p;
}
llink = p;
llink->parent = this;

The declaration and assignment of t2 is too far from where t2 is actually used, which seriously hurts readability. It would be better this way:

Node *p  = parent;
Node *gp = p->parent;

if (gp != NULL) {
    if (gp->llink == parent) {
        gp->llink = this;
    }
    else {
        assert(gp->rlink = parent);
        gp->rlink = this;
    }
    parent = gp;
}
else {
    parent = NULL;
}

Node *t2 = llink;
p->rlink = t2;
if (t2 != NULL) {
    p->rlink->parent = p;
}
llink = p;
llink->parent = this;

Not only it's more readable what is t2, now it's clear that it's actually pointless: you could use llink directly without t2.
Btw, I took a closer look at t2 because of its poor name.
I was wondering what it does, because its didn't explain anything.
If you had tried to give a more meaningful name to it in the beginning,
something that describes well its purpose,
you probably would have realized yourself early on that it has no purpose.

The variable p, being a single letter, is also confusing.
At first look I thought its declaration can be moved down just like t2,
I had to look closer to realize that it's important to store the original value of parent in it.
If it was named origParent or oldParent,
this would have been much harder to overlook.

StackExchange Code Review Q#69227, answer score: 3