Back to Search Start Over

An insertion technique for one-sided height-balanced trees

Authors :
Daniel S. Hirschberg
Source :
Communications of the ACM. 19:471-473
Publication Year :
1976
Publisher :
Association for Computing Machinery (ACM), 1976.

Abstract

A restriction on height-balanced binary trees is presented. It is seen that this restriction reduces the extra memory requirements by half (from two extra bits per node to one) and maintains fast search capabilities at a cost of increased time requirements for inserting new nodes.

Subjects

Subjects :
Red–black tree
General Computer Science
Binary search tree
Optimal binary search tree
Ternary search tree
Weight-balanced tree
Exponential tree
Arithmetic
Algorithm
Random binary tree
Threaded binary tree
Mathematics

Details

ISSN :
15577317 and 00010782
Volume :
19
Database :
OpenAIRE
Journal :
Communications of the ACM
Accession number :
edsair.doi...........6431c43cfeae9e6f961f1cf01854d719
Full Text :
https://doi.org/10.1145/360303.360334
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details