News for hackers. Stuff that matters.

A comment on B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees. Parent comment

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by nayuki on Monday June 24, 2024 @01:24PM (#40778608)
I would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set

B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set

[ Parent | on HN ]
Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by ncruces on Monday June 24, 2024 @07:14PM (#40782166)
Another (immutable/persistent) AA tree implementation, in Go:

https://github.com/ncruces/aa

[ Parent | on HN ]