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…