Top-down splay tree implementation (without rank support). More...

#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for tpl_splay_tree.H:

This graph shows which files directly or indirectly include this file:

Classes
class	GenTdSplayTree< NodeType, Key, Compare >
	Top-down splay tree - Self-adjusting BST with amortized O(log n) operations. More...

struct	GenTdSplayTree< NodeType, Key, Compare >::Iterator
	Iterator over the nodes. More...

struct	Splay_Tree< Key, Compare >

struct	Splay_Tree_Vtl< Key, Compare >

Detailed Description

Top-down splay tree implementation (without rank support).

This file provides Splay_Tree, a self-adjusting binary search tree that moves accessed nodes to the root via rotations (splaying). This provides amortized O(log n) performance and excellent cache locality for frequently accessed items.

Note: This code is adapted from Danny Sleator's implementation.

See also: http://www.link.cs.cmu.edu/link/ftp-site/splaying/

Author: Leandro Rabindranath León

Definition in file tpl_splay_tree.H.

Classes

Detailed Description