Improving time and space efficiency in generalized binary search trees
type: Item
instance of: scholarly article
title: Improving time and space efficiency in generalized binary search trees
zbMATH Open document ID: 0611.68040
DOI: 10.1007/BF00263296
author: Walter Cunto
author: Jose Luis Gascon
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: This paper deals with main memory data structures for which time and space performance are simultaneously considered. The main contribution is a new data structure called Generalized Binary Search Tree (GBS-tree) together with searching and updating algorithms on this structure. GBS- trees generalise different data structures based on binary trees that have appeared in the literature. A k-t GBS-tree allows up to t keys per node and subtrees in the tree's fringe of exactly 2k-1 full nodes are kept balanced. Their time and space performances are analysed in depth. The time performance is expressed in terms of the average and the variance of the number of binary comparisons between a given key and keys already in the structure. The space performance measures both the space used to space generated ratio (space utilization factor) and the pointers to keys ratio of these trees. The analysis shows that the time performance always improves when GBS-trees of higher order are considered. In the absence of balancing techniques, larger values of t, which produces smaller pointers to key ratios, induce unacceptably poor space utilizations factors. We show that both pointers to keys ratio and space utilization factor improve when larger values of k are used. Thus, local balancing techniques are adequate, not only for time performance improvement, but also, for space performance improvement.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3988728
zbMATH Keywords: data structures
zbMATH Keywords: searching
zbMATH Keywords: updating
zbMATH Keywords: GBS-trees
zbMATH Keywords: time performance
zbMATH Keywords: space performance
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: time complexity
zbMATH Keywords: space complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00263296
OpenAlex ID: W2066572674
description: scientific article; zbMATH DE number 3988728