Splay Tree

Code can be found here

Examples can be found here

Functionalities

• Insertion

• Removal

• Joining

• Splitting

• Finding

• Operators supported

  • <, ==, !=

• Iterators

  • Bidirectional
  • Supported: ++, --, ==,!=,=,* (lvalue and rvalue dereference)
  • All std algorithms that work for bidirectional iterators

Requirements for user defined data type

• Operator <
• Operator ==
• Operator !=

Usage of Splay Tree

Inclusion

#include "splay_tree.hpp"

Declaration

SplayTree<int> st1;
SplayTree<float> st2;

Insertion

st1.insert(1);
st2.insert(1.5);

Removal

st1.remove(1);
st2.remove(1.5);

Joining

Joining of two splay trees can take place only when the largest element of the first tree is smaller than the smallest element in the second tree

// assume two trees of type SplayTree<float> name st1 and st2
SplayTree<float> joined = join(st1, st2);

OR

SplayTree<float> joined = st1 + st2;

OR

// operator< is supported for splay trees
if (st1 < st2) {
	SplayTree<float> joined = join(st1, st2);
}

Splitting

// obtaining iterator of element by which to split the tree and then splitting
// assume st1 to be of type SplayTree<int>
SplayTree<int>::iterator it = st1.find(1);
std::pair<SplayTree<int>, SplayTree<int>> st = split(st1, it);

OR

// splitting based on value
std::pair<SplayTree<int>, SplayTree<int>> st = split(st1, 1);

// st.first now provides all elements occurring before it
// st.second now provides all elements occurring after it
// st1 remains unchanged

Finding

// assume st1 of type SplayTree<int>
SplayTree<int>::iterator it = st1.find(1);

OR

SplayTree<int>::iterator it = std::find(st1.begin(), st1.end(), 1);

Iterators

// assume st1 of type SplayTree<int>
SplayTree<int>::iterator it = st1.begin();
SplayTree<int>::iterator it2 = st1.end();

OR

SplayTree<int>::iterator it = std::begin(st1);
SplayTree<int>::iterator it2 = std::end(st1);