splay.h File Reference

#include "common.h"
#include "collection.h"
#include "vector.h"
#include "mempool.h"

Go to the source code of this file.

Data Structures
struct	_cp_splaynode
struct	_cp_splaytree

---

Detailed Description

splay tree definitions

splay trees move the node last accessed to the root of the tree as part of every operation. This makes tree operations slower than in AVL or red-black trees. A natural application for splay trees would be in implementing a cache, where a small number of keys out of a large search space are expected to be accessed at a significantly higher probability than average.

The splay tree was introduced by Daniel D. Sleator and Robert E. Tarjan in an article titled Self-Adjusting Binary Search Trees, 1985

Definition in file splay.h.

---