Splay Tree

发布于 2009-11-10 20:38:23 浏览：7469 订阅该版

A splay tree is a self-balancing binary search tree with the additional property that **recently accessed elements are quick to access again**. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time. For many non-uniform sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Sleator and Robert Tarjan.

Good performance for a splay tree depends on the fact that it is self-balancing, and indeed self optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage for nearly all practical applications, and is particularly useful for implementing **caches and garbage collection algorithms**; however it is important to note that for uniform access, a splay tree's performance will be considerably (although not asymptotically) worse than a somewhat balanced simple binary search tree.

Splay trees also have the advantage of being considerably simpler to implement than other self-balancing binary search trees, such as red-black trees or AVL trees, while their average-case performance is just as efficient. Also, splay trees do not need to store any bookkeeping data, thus **minimizing memory requirements**. However, these other data structures provide worst-case time guarantees, and can be more efficient in practice for uniform access.

Splay Tree implementation on FreeBSD: (Red-Black Tree implementation is also included)
[http://fxr.watson.org/fxr/source/sys/tree.h](http://fxr.watson.org/fxr/source/sys/tree.h)