A splay tree is a self-adjusting search algorithm for placing and locating files (called records or keys) in a database. The algorithm finds data by repeatedly making choices at decision points called nodes.
In a splay tree, as in a binary tree, a node has two branches (also called children). Records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. The starting point is called the root. The number of access operations required to reach the desired record is called the depth. In a practical tree, there can be thousands, millions, or billions of nodes, children, leaves, and records. Not every leaf necessarily contains a record, but more than half do. A leaf that does not contain data is called a null.
The splay tree scheme is unique because the tree organization varies depending on which nodes are most frequently accessed. This structural change takes place by means of so-called splaying operations, also called rotations. (In general, to splay is to spread or extend out or apart.) There are several ways in which splaying can be done. It always involves interchanging the root with the node in question. One or more other nodes might change position as well. The purpose of splaying is to minimize the number of access operations required to recover desired data records over a period of time.
Back to: Glossary