Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Grandchildren-weight-balanced binary search trees
Vincent Jugé
We revisit weight-balanced trees, also known as trees of bounded balance. This class of binary search trees was invented by Nievergelt and Reingold in 1972. Such trees are obtained…
cs.DS2024
Efficient top-down updates in AVL trees
Vincent Jugé
Since AVL trees were invented in 1962, two major open questions about rebalancing operations, which found positive answers in other balanced binary search trees, were left open: ca…