Presenting results in two papers by Siddhartha Sen and Robert E. Tarjan from ISAAC09 and SODA10.
Abstract: We discuss the often-neglected topic of rebalancing after deletion in balanced trees. Textbooks frequently omit it, many database systems don't implement it, so we desire data structures that don't require it. We therefore discuss variants of multiway search trees and balanced binary trees that do not perform deletion rebalancing, yet their search time remains logarithmic in the number of insertions. We also discuss a strong claim made by the authors that "[w]ith the addition of periodic rebuilding, the performance of these structures is theoretically superior to that of many if not all classic balanced tree structures." We lay out the facts and let you decide if this is a veritable "timber!" for our beloved search trees.