Date: Fri, 10 Jul 2020 12:28:16 -0500 From: Doug Moore <unkadoug@gmail.com> To: freebsd-current@freebsd.org Subject: A proposal to redefine RB trees Message-ID: <b749d0d9-0b83-b6d3-2214-cd9adb764db0@freebsd.org>
next in thread | raw e-mail | index | archive | help
I have a change ready to commit at https://reviews.freebsd.org/D25480 that would redefine the tree-balancing criteria for the RB tree macros, changing them from red-black trees to the weak-AVL trees described in the paper "Rank-balanced trees" by Haeupler, Sen and Tarjan. By happy coincidence (or the authors' deliberate scheme), the letters RB can represent "Rank-balanced" as easily as "red-black", so no global renaming is required. This change does not add or remove fields. It does keep a tighter balance constraint than red-black trees, so that in conditions where balancing really matters (for example, when inserting tree nodes in sorted order), weak-avl trees produce a better balanced tree and faster lookups. That same tighter balance constraint means that an insert operation is more likely to lead to restructuring of the tree than before, for which there is a small performance cost. The original paper at http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf provides more analysis of the relative benefits of weak-avl trees. Are there any objections? Doug Moore (dougm@freebsd.org)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?b749d0d9-0b83-b6d3-2214-cd9adb764db0>