# C++ Splay Tree implementation

I am coding a Splay Tree class in C++. I am looking for code review.

Currently, my Splay Tree class has search and rotate function.

I feel that I'm doing things overcomplicated.

#include <iostream>
#include <string>
#include <fstream>
#include <regex>

using namespace std;

class TreeNode
{
public:
int key;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
TreeNode(int key) {
this->key = key;
}
};

class SplayTree
{
public:
SplayTree() {
// This is temporary, will refactor later
root = newNode(10);
root->right = newNode(15);
root->right->right = newNode(16);
root->right->right->right = newNode(20);
root->right->right->right->right = newNode(21);
root->right->right->right->right->right = newNode(22);
};
~SplayTree() {};
TreeNode* newNode(int key)
{
TreeNode* Node = new TreeNode(key);
return (Node);
}

TreeNode* rightRotate(TreeNode* x)
{
TreeNode* y = x->left;
x->left = y->right;
y->right = x;
return y;
}

TreeNode* leftRotate(TreeNode* x)
{
TreeNode* y = x->right;
x->right = y->left;
y->left = x;
return y;
}

void splay(int key)
{
if (this->root == nullptr) return;

this->root = splaySub(this->root, key);

// Odd edge
if (this->root->key != key)
this->root = (key < this->root->key) ? rightRotate(this->root) : leftRotate(this->root);
}

void search(int key)
{
splay(key);
}

void preOrder() {
preOrder(this->root);
}

private:
void preOrder(TreeNode* root)
{
if (root != nullptr)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

TreeNode* splaySub(TreeNode* root, int key) {
if (root->key == key) return root;

// Code deal with root->left
if (key < root->key) {
// Not found. Return last accessed node. Do as if we looked for current node's key
if (root->left == nullptr) {
key = root->key; // Modifies the outer-scoped variable
return root;
}

root->left = splaySub(root->left, key);

// Check if return path is odd
if (root->left->key == key) return root;

// Apply a double rotation, top-down:
root = (key < root->key) ? rightRotate(root) : leftRotate(root);
return root = (key < root->key) ? rightRotate(root) : leftRotate(root);
}
// Code deal with root->right
else {
if (root->right == nullptr) {
key = root->key;
return root;
}

root->right = splaySub(root->right, key);

if (root->right->key == key) return root;

root = (key < root->key) ? rightRotate(root) : leftRotate(root);
return root = (key < root->key) ? rightRotate(root) : leftRotate(root);
}
}

TreeNode* root = nullptr;
};

int main()
{
SplayTree Tree = SplayTree();

Tree.search(20);
Tree.preOrder();

return 0;
}

• key = root->key; // Modifies the outer-scoped variable does it?! Oct 14, 2021 at 2:01
• (I think the assignment to a parameter only has a chance to modify an outside-function value only if that parameter was passed by/as a reference. (Then again, I didn't code C++ in anger for two decades.)) Oct 14, 2021 at 7:43
• I do in on purpose Oct 14, 2021 at 7:45

I "feel" symmetries could be leveraged using references.

// to do: doc comment, decent variable names, access, const correctness
TreeNode* rotate(TreeNode* x, TreeNode *&y, TreeNode *&y_child)
{
const TreeNode* r = y;
y = y_child;
y_child = x;
return r;
}

TreeNode* rightRotate(TreeNode* x)
{
return rotate(x, x->left, x->left->right);
}

TreeNode* leftRotate(TreeNode* x)
{
return rotate(x, x->right, x->right->left);
}

• (Um. Complicated. ?) Any takers? Oct 14, 2021 at 2:22
• No. It's okay. I'm thinking Oct 14, 2021 at 6:10
• Is there any way I can dynamically assign left or right to root? Like root[side] with side = "left"/"right" (JavaScript can do this) Oct 14, 2021 at 6:47
• (as in dynamically add an object property? No. That's easy in prototypal object modelling. I remember "morphing" Python objects.) Oct 14, 2021 at 8:35
• I added details for this to my Answer. Oct 14, 2021 at 14:07

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

    TreeNode(int key) {
this->key = key;
}


Use the base/member init list in your constructor, rather than assigning values in the body. So:

    TreeNode(int key)
: key{key} {}


Where's the destructor, copy constructor, etc? Remember the rule of three.

It looks like you don't have any way of removing nodes at all, and leak memory if you discard the entire tree when you are done with it.

 if (this->root == nullptr) return;

Don't do explicit comparisons against nullptr. Don't write this-> everywhere either! This line would just be: if (!root) return;

TreeNode* newNode(int key)
{
TreeNode* Node = new TreeNode(key);
return (Node);
}


What's the point of that? I think you can rely on the constructor doing what it's supposed to and not need to make another function to create an instance of an object.

cout << root->key << " ";


Don't use a string where a char will do. Use ' ' here instead of " ".

This code is duplicated:

          root = (key < root->key) ? rightRotate(root) : leftRotate(root);
return root = (key < root->key) ? rightRotate(root) : leftRotate(root);


Try and make it back on the common branch rather than on both sides of a conditional statement, or stick it into a helper function.

Just looking at the code, I wonder if there is some subtle difference ... or were they supposed to be mirror images? It's actually a lot of work and cognitive overhead to deal with duplication like this.

# P.S.

Otherwise, I think you're doing good. Keep it up! Your comments are meaningful and aid in reading the code.

# mirroring code

Is there any way I can dynamically assign left or right to root? Like root[side] with side = "left"/"right"

Yes. I've done this on a data structure that had a kind of AVL tree at its heart. I only needed one copy of each algorithm, such as rotating. It could rotate to the left or rotate to the right with the same code. This has a benefit in coverage testing too.

The key is to make the two different fields (left pointer and right pointer) an array of two things so they can be indexed.

   Treenode* children[2];  // left and right


Then, you can use an enumeration for Left=0 and Right=1. Now each function can take another parameter, say:

TreeNode* rightRotate (TreeNode* x, direction dir)
{


The first thing you do is set up local meanings for "this way" and "the other way". I used S and D as the two logical directions (for sinistral and dexteral) instead of switching the meanings of the actual Left and Right locally.

    const direction S = dir;  // the way I'm going
const direction S = 1-dir;  // the other way


I'm not showing the needed casting for "strong" types, just the underlying math that 1-dir is always the other one. In real code, this was a separate helper function that's used everywhere I have mirroring-enabled code.

    TreeNode* y = x->children[S];

That is, change left to children[S] and right to children[D].