Splay tree

From WikiMD's Food, Medicine & Wellness Encyclopedia

Splay tree is a self-adjusting 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 amortized time complexity of O(log n) for n elements. This performance is comparable to other trees that balance height, such as AVL trees, but is achieved through a different mechanism known as splaying. Splaying not only helps with balancing the tree but also ensures that frequently accessed elements are moved closer to the root, making subsequent accesses faster.

Overview[edit | edit source]

A splay tree works by performing a splay operation on every access (including insertion, search, and deletion), which moves the accessed element to the root of the tree through a series of tree rotations. The splay operation is designed to not only move the accessed element to the root but also to partially rebalance the tree, improving the efficiency of future operations.

Operations[edit | edit source]

Splay Operation[edit | edit source]

The splay operation is central to the splay tree's functionality. It involves rotating the accessed node until it becomes the root of the tree. This is achieved through a series of specific rotations based on the node's position relative to its parent and grandparent: zig, zig-zig, and zig-zag.

Insertion[edit | edit source]

To insert a new element, the tree first performs a standard binary search tree insertion. After the element is inserted, a splay operation is performed on the inserted node, moving it to the root.

Search[edit | edit source]

When searching for an element, a binary search is performed. Regardless of whether the element is found, the last accessed node (either the node that was searched for or the last node accessed during the search) is splayed to the root.

Deletion[edit | edit source]

To delete an element, the tree first splays the target element to the root. Then, the tree is split into two subtrees: one containing all elements less than the deleted element and another containing all elements greater. These two trees are then joined, with the root of the joined tree being the minimum element of the right subtree after another splay operation.

Advantages and Disadvantages[edit | edit source]

The main advantage of splay trees is their ability to adapt to the sequence of operations performed on them, providing efficient access to frequently accessed elements. This makes them particularly useful in applications where access patterns are not uniform or predictable.

However, splay trees can have poor worst-case performance for individual operations, and the tree can become unbalanced if the access pattern is not sufficiently random or if there are long sequences of operations on elements that are far apart in the key space.

Applications[edit | edit source]

Splay trees are used in various applications that require efficient, adaptable, and easy-to-implement data structures for non-uniform access patterns. Examples include implementing caches, memory allocators, and data compression algorithms.

See Also[edit | edit source]



This computer science-related article is a stub. You can help WikiMD by expanding it.

Wiki.png

Navigation: Wellness - Encyclopedia - Health topics - Disease Index‏‎ - Drugs - World Directory - Gray's Anatomy - Keto diet - Recipes

Search WikiMD


Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD

WikiMD is not a substitute for professional medical advice. See full disclaimer.

Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.

Contributors: Prab R. Tumpati, MD