2
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ key = root->key; // Modifies the outer-scoped variable does it?! \$\endgroup\$
    – greybeard
    Oct 14, 2021 at 2:01
  • \$\begingroup\$ (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.)) \$\endgroup\$
    – greybeard
    Oct 14, 2021 at 7:43
  • \$\begingroup\$ I do in on purpose \$\endgroup\$
    – Tan Nguyen
    Oct 14, 2021 at 7:45

2 Answers 2

1
\$\begingroup\$

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);
}
\$\endgroup\$
9
  • \$\begingroup\$ (Um. Complicated. ?) Any takers? \$\endgroup\$
    – greybeard
    Oct 14, 2021 at 2:22
  • \$\begingroup\$ No. It's okay. I'm thinking \$\endgroup\$
    – Tan Nguyen
    Oct 14, 2021 at 6:10
  • \$\begingroup\$ Is there any way I can dynamically assign left or right to root? Like root[side] with side = "left"/"right" (JavaScript can do this) \$\endgroup\$
    – Tan Nguyen
    Oct 14, 2021 at 6:47
  • \$\begingroup\$ (as in dynamically add an object property? No. That's easy in prototypal object modelling. I remember "morphing" Python objects.) \$\endgroup\$
    – greybeard
    Oct 14, 2021 at 8:35
  • \$\begingroup\$ I added details for this to my Answer. \$\endgroup\$
    – JDługosz
    Oct 14, 2021 at 14:07
1
\$\begingroup\$

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.

Then your code becomes:

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

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

\$\endgroup\$
3
  • \$\begingroup\$ Thanks. It's a lot of insight \$\endgroup\$
    – Tan Nguyen
    Oct 14, 2021 at 6:19
  • \$\begingroup\$ Is there any way I can dynamically assign left or right to root? Like root[side] with side = "left"/"right" (JavaScript can do this) \$\endgroup\$
    – Tan Nguyen
    Oct 14, 2021 at 6:47
  • 1
    \$\begingroup\$ @TanNguyen I updated my post to answer this. You can also look into pointers to members to do what you can with JavaScript. Though the way I showed is simple and generates very efficient code. \$\endgroup\$
    – JDługosz
    Oct 14, 2021 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.