B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by 29athrowaway on Monday June 24, 2024 @02:13AM (#40773000)

Left leaning red black trees are simpler to implement than the regular red black tree.

[ Parent | on HN ]

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by skribanto on Monday June 24, 2024 @12:29PM (#40778039)

Left leaning red black trees enforce extra constraints, which remove symmetries. This actually adds an edge case when instead you can just treat left/right rotations and comparisons as symmetric operations.

Left Leaning Red Black Trees Considerer Harmful: https://www.read.seas.harvard.edu/~kohler/notes/llrb.html

[ Parent | on HN ]