𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Explanation of Splaying

✍ Scribed by Ashok Subramanian

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
127 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We propose a framework for studying bottom-up restructuring heuristics for binary search trees. We identify the key role played by depth-reducing rules in obtaining logarithmic amortized cost per access. We show that splaying is by no means the only heuristic that offers logarithmic amortized cost.

πŸ“œ SIMILAR VOLUMES

A systematic analysis of splaying
A systematic analysis of splaying
✍ Berry Schoenmakers πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 496 KB
Inorder traversal of splay trees
Inorder traversal of splay trees
✍ Colm Γ“ DΓΊnlaing πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 357 KB

Splay trees, a form of self-adjusting binary tree, were introduced by Sleator and Tarjan in the early 1980s. Their main use is to store ordered lists. The idea is to keep the trees reasonably well balanced through a 'splay heuristic.' Sleator and Tarjan showed that if amortised rather than worst-cas

An explanation of reasoning neural netwo
An explanation of reasoning neural networks
✍ R.R. Tsaih πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 693 KB

tioning Neural Networks (RN) adopts the layered feedforward network structure, and its learning algorithm belongs to the weight-and-structure-change category of learning algorithm. In this paper, we firstly explain that, in the layered feedforward network, the essential characteristic of the mapping