Super simple splay execution -- ref stjepang/splay.cpp

SimpleSplay.cpp

// Simple Splay

#include<iostream>
using namespace std;

template<class T>
struct Node {
	T value;
	Node *l, *r, *p;

	Node() { l = r = p = nullptr; }

	~Node() {
		if (l) delete l;
		if (r) delete r;
	}

	void setL(Node* L) { l = L; if (l) l->p = this; }
	void setR(Node* R) { r = R; if (r) r->p = this; }
};

template<class T>
struct Splay {
	Node<T>* root = nullptr;

	~Splay() { if (root) delete root; }

	void rotate(Node<T>* A, Node<T>* B) {
		Node<T>* p = A->p;

		if (A->l == B) A->setL(B->r), B->setR(A);
		else A->setR(B->l), B->setL(A);

		if (!p) root = B, B->p = nullptr;
		else if (p->l == A) p->setL(B);
		else p->setR(B);
	}
	
	void splay(Node<T>* A) {
		while (A != root) {
			Node<T> * B = A->p;
			Node<T> * C = A->p->p;

			if (B == root) {
				rotate(B, A);
				break;
			}

			if ((C->l && C->l->l == A) || (C->r && C->r->r == A)) {
				rotate(C, B);
				rotate(B, A);
			} else {
				rotate(B, A);
				rotate(C, A);
			}
		}
	}

  void insert(T value) {
    Node<T>* B = nullptr;
    Node<T>* A = root;

    while (A) {
      B = A;

      if (value < A->value) A = A->l;
      else A = A->r;
    }

    Node<T>* C = new Node<T>;
    C->value = value;

    if (root == nullptr) root = C;
    else {
      if (value < B->value) B->setL(C);
      else B->setR(C);
      splay(C);
    }
  }
};

template<class T>
void print(Node<T>* n, int depth = 0) {
  if (n->l) print(n->l, depth + 1);

  for (int i = 0; i < depth*3; ++i) printf(" ");
  printf("%u\n", n->value);

  if (n->r) print(n->r, depth + 1);
}

int main() {
  Splay<uint32_t> splay;

  uint32_t num = 1;
  for (int i = 0; i < 100; ++i) {
    num = num * 17 + 255;
    splay.insert(num);
  }

  print(splay.root);
  return 0;
}