A lopsided binary tree has two weights (a and b) associated with its edges, one for left children and one for right children. Minimum weighted depths for the worst case (maximum depth) and average case (average depth) are roughly logrN, where N is the number of leaves and r satisfies r−a + r−b = 1 (so if a = b = 1 then r = 2). Lopsided trees can arise in analyzing recursive binary decision algorithms where the costs of the choices are different, or in prefix-free encoding on a binary alphabet. The authors present an example algorithm that searches for an unbounded key when the costs of comparisons depend on the outcome (though it should not be followed blindly: the recurrence relation for g(j) at the bottom of page 585 unfortunately yields g(j) = 1 for all j).
The approach and results would appeal primarily to those interested in tightening bounds on tree-related algorithms and seeking to increase their repertoire of techniques. It is not obvious how many actual problems can be phrased so as to use the material directly, but this paper might provide a helpful stepping-stone for future applications, perhaps including the analysis of time complexity for algorithms that involve alternatives between recursive calls (such as iterative algorithms that use two or-parallel sub-algorithms at each step, selecting the faster result).
