Red-black trees with relative node keys

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
4 Downloads (Pure)


This paper addresses the problem of storing an ordered list using a red-black tree, where node keys can only be expressed relative to each other. The insert and delete operations in a red-black tree are extended to maintain the relative key values. The extensions rely only on relative keys of neighboring nodes, adding constant overhead and thus preserving the logarithmic time complexity of the original operations. Keywords: Data structures; Algorithms; Search trees; Red-black trees; Relative keys
Original languageEnglish
Pages (from-to)591-596
Number of pages6
JournalInformation Processing Letters
Issue number11
Publication statusPublished - 2014


Dive into the research topics of 'Red-black trees with relative node keys'. Together they form a unique fingerprint.

Cite this