Class SplayTree<K, V>

A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. Insertion, look-up and removal in O(log n) amortized time. For many patterns of non-random operations splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern.

See

Template

V

Type Parameters

  • K

  • V = any

Hierarchy

Constructors

constructor

Properties

cmp count randSplay root?

Accessors

height length size

Methods

add clear contains delete empty entries get keys lowerBound max min remove set splay top values

Constructors

constructor

  • Create a new randomized Splay Tree

    Type Parameters

    • K

    • V = any

    Parameters

    • Optional compareFn: any
    • p: number = 0.5

      When an element is accessed, with probability p splay the tree. With probability 1 - p, leave the tree as it is.

    Returns SplayTree<K, V>

Properties

Protected cmp

cmp: Comparer<any>

Protected count

count: number

Protected randSplay

randSplay: number

Protected Optional root

root?: Node<K, V>

Accessors

height

length

size

  • get size(): number

  • Returns the total number of elements in the collection.

    Returns number

Methods

add

clear

contains

delete

  • Alias of remove but just returns true instead of the deleted value.

    Parameters

    • key: K

    Returns boolean

empty

entries

  • Returns an ordered iterable of all the keys and values in the tree.

    Returns

    A iterable of [key, value] pairs sorted by key.

    Returns Iterable<[K, V]>

get

  • Returns the value for key or undefined if the key is not found.

    Returns

    The value for the key or undefined.

    Parameters

    • key: K

      The key to find.

    Returns any

keys

lowerBound

  • Returns the largest key that is less than a given key.

    Returns

    The largest key found or undefined.

    Parameters

    • key: any

      The given key

    Returns K | Node<K, V>

max

  • Returns the maximum key in the tree or subtree.

    Returns

    The maximum key.

    Parameters

    • root: Node<K, V> = ...

    Returns K

min

  • Returns the minimum key in the tree or subtree.

    Returns

    The minimum key.

    Parameters

    • root: Node<K, V> = ...

    Returns K

remove

  • Removes a specified key if it exists in the tree. The removed value is returned or undefined if not found.

    Returns

    The removed value associated with key.

    Parameters

    • key: K

      The key to remove.

    Returns V

set

  • Inserts the key and value in the tree if the key does not exist.

    Returns

    Parameters

    • key: K

      A key which can be any comparable value

    • value: V

      A value associated with the key

    Returns void

splay

top

values

  • Returns an ordered iterable of all the keys and values in the tree.

    Returns

    A iterable of [key, value] pairs sorted by key.

    Returns Iterable<V>

Settings

Member Visibility

Theme

Generated using TypeDoc