Splay Tree

A splay-tree is a BST, self adjusting, that has

• the working-set property
• the dynamic-finger property
• conjectured to be dynamically optimal
• conjectured to have unified property

install with sbt

    val splayTreesVersion = "0.1.1"
    libraryDependencies += "com.nachinius" %% "splaytrees" % splayTreesVersion

usage

import com.nachinius.splay.Node

val objTres = new Node[Int,String](3,"tres")
val objCinco = objTres.insert(5,"cinco")

// better to insert in last inserted node (which is the root). Nevertheless you may insert anywhere, but if you use a node that is not already the root, the system will invoke an extra `splay` call

val objSeven = objCinco.insert(7, "siete")
// equivalent (in result, not performance) to
// val objSeven = objTress.insert(7,"siete")

//----
// To add a sequence of tuples (key: Key, value: Value)
val seq: (Key, Value)
seq.foldLeft(objTres) {
  case (n, (k,v)) => n.insert(k,v)
}
// e.g.
val seed = 1475648325L
val rnd = new scala.util.Random(seed)
val maxNumber = 10000
val last = Seq.fill(100)(rnd.nextInt(maxNumber)).foldLeft(objTres) {
 case (n, (k,v)) => n.insert(k, v.toString)
}
//--- 

//And then you can search
last.search(5)

// split at ndoe
last.split

// or split at a found value (we have inserted 7 before)
val optCuttedTree = last.search(7).map(_.split)

// you can call splay directly in any node, (if you have athe node reference)
last.splay

what is a Splay Tree

References

[1] Advanced Data Structures, MIT 6.851, Prof. Erik Demaine Lecture 19

[2] https://en.wikipedia.org/wiki/Splay_tree (retrieved 2018-february-05):