Class: SplayTree

data-structures/splay-tree. SplayTree

Constructor

new SplayTree()

Splay tree. http://en.wikipedia.org/wiki/Splay_tree
Source:

Methods

_getHeight(node) → {Number}

Recursive worker function for getHeight()
Parameters:
Name Type Description
node Node The node of the current recursive frame.
Source:
Returns:
The height of the tree.
Type
Number

_splaylessSearch(value)

Finds a node by it's value.

Average time complexity: O(log N).
Parameters:
Name Type Description
value Number | String of the node which should be found.
Source:

getDiameter() → {Number}

Finds the diameter of the Splay Tree.
Source:
Returns:
The longest path in the tree.
Type
Number

getHeight() → {Number}

Returns the height of the tree.
Source:
Returns:
The height of the tree.
Type
Number

inorder(callback)

In-order traversal of the whole Splay Tree.
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.
Source:

insert(value, current)

Inserts a node into the splay tree.

Time complexity: O(log N) in the average case and amortized O(log n) in the worst case.
Parameters:
Name Type Description
value Number | String Node value.
current Node Current node.
Source:

isBalanced() → {Boolean}

Returns whether the Splay Tree is balanced.
Source:
Returns:
Whether the tree is balanced or not.
Type
Boolean

lowestCommonAncestor() → {Node}

Finds the lowest common ancestor of two nodes.
Source:
Returns:
The lowest common ancestor of the two nodes or null.
Type
Node

postorder(callback)

Post-order traversal of the whole tree.
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.
Source:

preorder(callback)

Pre-order preorder traversal of the whole tree.
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.
Source:

remove(value) → {Boolean}

Removes node with given value from the tree.

Average runtime complexity: O(log N).
Parameters:
Name Type Description
value Number | String Value to be removed
Source:
Returns:
True/false depending on whether the given node is removed.
Type
Boolean
Finds a node by it's value.

Average time complexity: O(log N).
Parameters:
Name Type Description
value Number | String of the node which should be found.
Source: