2 ms·
Related, maybe interesting to this crowd: In FreeBSD, the RB tree implementation has been replaced with a "weak AVL" tree implementation: https://github.com/fr
by loeg 6y ago
Related, maybe interesting to this crowd: In FreeBSD, the RB tree implementation has been replaced with a "weak AVL" tree implementation:
https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a3bf25303ff539f6432b9c76848 https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a...
> Weak AVL (Wavl) trees sit between AVL and red-black trees in terms of how
strictly balance is enforced. They have the stricter balance of AVL
trees as the tree is built - a wavl tree is an AVL tree until the
first deletion. Once removals start, wavl trees are lazier about
rebalancing than AVL trees, so that removals can be fast, but the
balance of the tree can decay to that of a red-black tree. Subsequent
insertions can push balance back toward the stricter AVL conditions.
> ...
> Testing has shown that for the cases where red-black trees do worst,
wavl trees better balance leads to faster lookups, so that if lookups
outnumber insertions by a nontrivial amount, lookup time saved exceeds
the extra cost of balancing.