Red-black trees with relative node keys

M.J. Holenderski; R.J. Bril; J.J. Lukkien

doi:10.1016/j.ipl.2014.06.004

Red-black trees with relative node keys

M.J. Holenderski, R.J. Bril, J.J. Lukkien

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

4 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	591-596
Number of pages	6
Journal	Information Processing Letters
Volume	114
Issue number	11
DOIs	https://doi.org/10.1016/j.ipl.2014.06.004
Publication status	Published - 2014

Access to Document

10.1016/j.ipl.2014.06.004

Cite this

@article{c1eb22de1adb45da94c05e52f8eed1de,

title = "Red-black trees with relative node keys",

abstract = "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",

author = "M.J. Holenderski and R.J. Bril and J.J. Lukkien",

year = "2014",

doi = "10.1016/j.ipl.2014.06.004",

language = "English",

volume = "114",

pages = "591--596",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - Red-black trees with relative node keys

AU - Holenderski, M.J.

AU - Bril, R.J.

AU - Lukkien, J.J.

PY - 2014

Y1 - 2014

N2 - 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

AB - 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

U2 - 10.1016/j.ipl.2014.06.004

DO - 10.1016/j.ipl.2014.06.004

M3 - Article

SN - 0020-0190

VL - 114

SP - 591

EP - 596

JO - Information Processing Letters

JF - Information Processing Letters

IS - 11

ER -

Red-black trees with relative node keys

Abstract

Access to Document

Fingerprint

Cite this