3 ms·
But logit-weight trees have logarithmic height, yes?
by jbapple 7y ago
But logit-weight trees have logarithmic height, yes?
- sesqu 7y agoWeight 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 restrict, but doing so restricts dynamic performance optimizations - you can't use splay trees, for instance
- 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).