en.unionpedia.org

Splay tree, the Glossary

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again.^[1]

37 relations: Amortized analysis, AVL tree, B-tree, Big O notation, Binary search tree, Cache (computing), Daniel Sleator, DIMACS, Double-ended queue, Entropy (information theory), Finger tree, Garbage collection (computer science), Geometry of binary search trees, Iacono's working set structure, Information Processing Letters, Journal of the ACM, Key-independent optimality, Link/cut tree, List of data structures, Locality of reference, Memory footprint, Potential method, Probabilistic analysis of algorithms, Probability distribution, Robert Tarjan, Scapegoat tree, Self-balancing binary search tree, SIAM Journal on Computing, Splaysort, Succinct data structure, T-tree, Telescoping series, The Art of Computer Programming, Treap, Tree (data structure), Tree rotation, Zipper (data structure).
Amortized data structures
Binary trees
Search trees

Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. Splay tree and amortized analysis are amortized data structures.

See Splay tree and Amortized analysis

AVL tree

In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. Splay tree and AVL tree are amortized data structures, binary trees and search trees.

See Splay tree and AVL tree

B-tree

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Splay tree and b-tree are search trees.

See Splay tree and B-tree

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

See Splay tree and Big O notation

Binary search tree

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. Splay tree and binary search tree are binary trees and search trees.

See Splay tree and Binary search tree

Cache (computing)

In computing, a cache is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere.

See Splay tree and Cache (computing)

Daniel Sleator

Daniel Dominic Kaplan Sleator (born 10 December 1953) is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States.

See Splay tree and Daniel Sleator

DIMACS

The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Applied Communication Sciences, and NEC.

See Splay tree and DIMACS

Double-ended queue

In computer science, a double-ended queue (abbreviated to deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

See Splay tree and Double-ended queue

Entropy (information theory)

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes.

See Splay tree and Entropy (information theory)

Finger tree

In computer science, a finger tree is a purely functional data structure that can be used to efficiently implement other functional data structures. Splay tree and finger tree are amortized data structures.

See Splay tree and Finger tree

Garbage collection (computer science)

In computer science, garbage collection (GC) is a form of automatic memory management.

See Splay tree and Garbage collection (computer science)

Geometry of binary search trees

In computer science, one approach to the dynamic optimality problem on online algorithms for binary search trees involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible to avoid rectangles with only two points on their boundary. Splay tree and geometry of binary search trees are binary trees.

See Splay tree and Geometry of binary search trees

Iacono's working set structure

In computer science, Iacono's working set structure is a comparison based dictionary.

See Splay tree and Iacono's working set structure

Information Processing Letters

Information Processing Letters is a peer-reviewed scientific journal in the field of computer science, published by Elsevier.

See Splay tree and Information Processing Letters

Journal of the ACM

The Journal of the ACM is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects.

See Splay tree and Journal of the ACM

Key-independent optimality

Key-independent optimality is a property of some binary search tree data structures in computer science proposed by John Iacono.

See Splay tree and Key-independent optimality

Link/cut tree

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations. Splay tree and Link/cut tree are amortized data structures.

See Splay tree and Link/cut tree

List of data structures

This is a list of well-known data structures.

See Splay tree and List of data structures

Locality of reference

In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time.

See Splay tree and Locality of reference

Memory footprint refers to the amount of main memory that a program uses or references while running.

See Splay tree and Memory footprint

Potential method

In computational complexity theory, the potential method is a method used to analyze the amortized time and space complexity of a data structure, a measure of its performance over sequences of operations that smooths out the cost of infrequent but expensive operations.

See Splay tree and Potential method

Probabilistic analysis of algorithms

In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem.

See Splay tree and Probabilistic analysis of algorithms

Probability distribution

In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of possible outcomes for an experiment.

See Splay tree and Probability distribution

Robert Tarjan

Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician.

See Splay tree and Robert Tarjan

Scapegoat tree

In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson in 1989 and again by Igal Galperin and Ronald L. Rivest in 1993. Splay tree and scapegoat tree are amortized data structures, binary trees and search trees.

See Splay tree and Scapegoat tree

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. Splay tree and self-balancing binary search tree are binary trees.

See Splay tree and Self-balancing binary search tree

SIAM Journal on Computing

The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.

See Splay tree and SIAM Journal on Computing

Splaysort

In computer science, splaysort is an adaptive comparison sorting algorithm based on the splay tree data structure.

See Splay tree and Splaysort

Succinct data structure

In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations.

See Splay tree and Succinct data structure

T-tree

In computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite. Splay tree and t-tree are binary trees and search trees.

See Splay tree and T-tree

Telescoping series

In mathematics, a telescoping series is a series whose general term t_n is of the form t_n.

See Splay tree and Telescoping series

The Art of Computer Programming

The Art of Computer Programming (TAOCP) is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis.

See Splay tree and The Art of Computer Programming

Treap

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. Splay tree and treap are binary trees and search trees.

See Splay tree and Treap

References

[1] https://en.wikipedia.org/wiki/Splay_tree

Also known as Dynamic Optimality Conjecture, Self-adjusting binary search tree, Splay binary search tree, Splay heap, Splay trees, Splaying.

Splay tree, the Glossary

Table of Contents

See also

Amortized data structures

Binary trees

Search trees

References