Red-black trees with relative node keys

•Storing an ordered list using a red-black tree with relative keys is proposed.•The insert and delete operations are extended to maintain relative keys.•The correctness of the extensions is proven.•The proposed extensions maintain logarithmic time complexity.

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.