Definition

splay tree

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.

Also see binary tree, B-tree, and tree structure.

This was last updated in September 2005
Posted by: Margaret Rouse

Email Alerts

Register now to receive SearchOracle.com-related news, tips and more, delivered to your inbox.
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy

More News and Tutorials

Do you have something to add to this definition? Let us know.

Send your comments to techterms@whatis.com

There are Comments. Add yours.

 
TIP: Want to include a code block in your comment? Use <pre> or <code> tags around the desired text. Ex: <code>insert code</code>

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
Sort by: OldestNewest

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to: