JSplay

A NodeJS implementation of Splay Tree binary search algorithm.

$3

#### [1.0.1] - 2016-10-08

- Allowing splay the deepest node to the root using splayDeepest method

$3

JSplay is the classic splay tree search algorithm written completely in JavaScript, compatible with NodeJs applications
and browsers. Yep, that's right. Browsers.

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.

All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.

More info on Wikipedia.

$3

Regardless of the presence of the associated key prior to that operation, this splay tree implementation splays on every operation. If there isn't a node with
that key, the last node along the search path for the key will be splayed to the root.

#### Insertion

In order to insert a new node into the tree, you need to supply it's Key and Value. You're free to use a key with any type,
but it's extremely recommended to use integer keys in order to preserve fast key comparison between nodes. The new node will be splayed to the root of the tree.

``javascript
var JSplay = require("jsplay");

var tree = new JSplay();

// add method take two params: KEY (any type, preferably int), VALUE (any type)
tree.add(1, "one");
tree.add(2, 2);
tree.add(3, { "val" : "tree" });
tree.add(1, "one - updated"); // Updates node with key 1 to "one - updated"
`

#### Contains

Check if the tree contains a given node by its key.

`javascript
var JSplay = require("jsplay");

var tree = new JSplay();
tree.add(1, "one");
tree.contains(1); // true
tree.contains(2); // false
`

#### Get

Search for a node by its key and return it's value.

`javascript
var JSplay = require("jsplay");

var tree = new JSplay();
tree.add(1, "one");
tree.add(2, { "val" : 2 });

tree.get(1); // returns "one"
tree.get(2); // returns { "val" : 2 }
tree.get(3); // returns null
`

#### Remove

Removes a node from the tree.

`javascript
var JSplay = require("jsplay");

var tree = new JSplay();
tree.add(1, "one");
tree.add(2, { "val" : 2 });

tree.remove(1);
tree.contains(1); // returns false
`

#### Splay Deepest

Get the deepest node in the tree and splay it to the root. It allows
access the least used node.

`javascript
var JSplay = require("jsplay");

var tree = new JSplay();
tree.add(6, "six");
tree.add(5, "five");
tree.add(4, "four");
tree.add(2, "two");
tree.add(1, "one");
tree.add(3, "three");

tree.getRoot() // returns 3 - the last inserted node
tree.splayDeepest();
tree.getRoot(); // returns 6 - the first inserted node
`

$3

Just run:

$ npm install

$3

Just run:

$ make compress

$3

Tests were write using Jasmine. In order to run them, just type:

$ npm test

$3

To build a docker image, you should just simply type:

$ docker build -t pedrolopesme/jsplay .

In order to run it, simply do:

$ docker run pedrolopesme/jsplay`

$3

JSplay logo was created by PixelKit, released under Creative Commons Attribution 3.0 Unported (CC BY 3.0) license.

$3

MIT. Copyright (c) Pedro Mendes.