4 ms·

Weight is a weaker condition, since you can construct a polynomial weight sequence that results in linear height. In general, height is the easiest thing to re

• jbapple 7y ago
  > Weight is a weaker condition, since you can construct a polynomial weight sequence that results in linear height. I'd like to hear more. The varieties of weight-balanced trees I'm aware of all have logarithmic height. > In general, height is the easiest thing to restrict, but doing so restricts dynamic performance optimizations - you can't use splay trees, for instance Good point. BTW, you might be interested in Bose et al.'s "De-amortizing Binary Search Trees" <https://arxiv.org/pdf/1111.1665.pdf> https://arxiv.org/pdf/1111.1665.pdf>, shows how to keep height logarithmic with "essentially any Binary Search Tree" (their phrase).