Title :
Optimal operations on red-black trees
Author :
Chen, Lin ; Schott, René
Author_Institution :
Univ. of Southern California, Los Angeles, CA, USA
Abstract :
We show that some fundamental operations such as deletion and insertion can be performed in O(log n) time and O(1) space on red-black trees given two child pointers for each node. This improves the space efficiency while maintaining the time bound
Keywords :
computational complexity; optimisation; search problems; tree data structures; trees (mathematics); balanced binary search trees; child pointers; deletion; insertion; optimal operations; red-black trees; space efficiency; symmetric binary B-trees; time bound; Binary search trees; Memory management; Tree data structures;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315316
