Tall WAVL Tree Constructions and Modified Rebalancing

Abstract

Rank-balanced trees [2] are binary search trees whose nodes carry integer ranks constrained by local parent–child rank-difference rules. The weak AVL (WAVL) tree relaxes AVL by permitting (2, 2)-nodes, which simplifies deletion rebalancing while maintaining low update costs. Following the framework of Haeupler, Sen, and Tarjan [2], we investigate the possible height of WAVL trees in terms of the current size n. The rank rule implies an upper bound of h ≤ log√2 n, but it is not a priori clear whether this worst-case behavior can actually occur. We show that it can. We first construct, via a sequence of insertions and deletions, arbitrarily large WAVL trees in which every internal node is of type (2, 2), and show that these trees still have height only Θ(log2 n). We then use these trees as building blocks in a more unbalanced construction whose right spine consists entirely of 1-children and whose left subtrees are largely composed of (2, 2)-nodes. The resulting family has height Θ(log√2 n), showing that the structural upper bound is asymptotically tight. We then propose a modification of the deletion rebalancing rules that suppresses our extremal configuration. Under this modified rule, we conjecture that the height improves to O(logb n) for some b > √2, while the total number of rebalancing steps remains O(m + d). As a secondary contribution, we also attempt a history-independent argument of the classical bound h ≤ logϕ m, by slightly modifying the history-dependent counting argument used in [2].