Module: Algorithms

Defined in:

lib/algorithms.rb,
lib/algorithms/sort.rb,
lib/containers/heap.rb,
lib/containers/trie.rb,
lib/containers/deque.rb,
lib/containers/queue.rb,
lib/containers/stack.rb,
lib/algorithms/search.rb,
lib/algorithms/version.rb,
lib/containers/kd_tree.rb,
lib/containers/rb_tree_map.rb,
lib/containers/suffix_array.rb,
lib/containers/priority_queue.rb,
lib/containers/splay_tree_map.rb,
ext/containers/bst/bst.c,
ext/containers/deque/deque.c,
ext/algorithms/string/string.c,
ext/containers/rbtree_map/rbtree.c,
ext/containers/splaytree_map/splaytree.c

Overview

A SplayTreeMap is a map that is stored in ascending order of its keys, determined by applying

the function <=> to compare keys. No duplicate values for keys are allowed, so new values of a key
overwrites the old value of the key.

A major advantage of SplayTreeMap over a Hash is the fact that keys are stored in order and can thus be
iterated over in order. Also, Splay Trees are self-optimizing as recently accessed nodes stay near
the root and are easily re-accessed later. Splay Trees are also more simply implemented than Red-Black
trees.

Splay trees have amortized O(log n) performance for most methods, but are O(n) worst case. This happens
when keys are added in sorted order, causing the tree to have a height of the number of items added.

Defined Under Namespace

Modules: Algorithms, Containers

Constant Summary

VERSION =

"1.0.4"