On top-down splaying
type: Item
instance of: scholarly article
title: On top-down splaying
zbMATH Open document ID: 0642.68119
DOI: 10.1007/BF01933728
published in: BIT
publication date: 1987-01-01T00:00:00Z
review text: The splay tree is a self-adjusting binary search tree which has a good amortized performance. This paper studies some properties of top-down splay trees. Different ways to charge for the primitive operations of top-down splaying are discussed. We also give some empirical results concerning the behaviour of different top-down restructuring algorithms.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4047147
zbMATH Keywords: rotation
zbMATH Keywords: self-adjusting data structures
zbMATH Keywords: amortized complexity
zbMATH Keywords: splay tree
zbMATH Keywords: binary search tree
author: Erkki Mäkinen
MaRDI profile type: Publication
cites work: Self-Organizing Binary Search Trees
cites work: Self-adjusting binary search trees
cites work: A method for constructing binary search trees by making insertions at the root
cites work: Amortized Computational Complexity
description: scientific article; zbMATH DE number 4047147