Compare height balanced tree to weight balanced tree

1
votes

I was thinking of scenarios when a height balanced tree outperforms a weight balanced tree. Following are the questions I could not find an answer to even after a good amount of search:

  1. Both the trees have similar time and space complexity, so why would I prefer one over another?

  2. Are there some applications where weight balanced trees are preferred to height balanced ones?

  3. If I want to know which of these given trees can fit my needs, what features should I observe in my CRUD querying pattern?

1
algorithmsortingdata-structurestreebinary-tree
Since rebalancing is not cost-free, you may also want to considere (based on your requirements) unbalanced trees that have otherwise limits on the imbalance. For example, CritBit tries (bit wise PatriciaTries) are unbalanced, but still have a strict limit on the maximum depth, for example 32 levels for 32 bit values. For large datasets such unbalanced datastructures may be the best choice. - TilmannZ
@TilmannZ If I understand correctly, CritBit trees is like lazily balancing trees i.e. rebalancing when max-depth is reached. We can simulate CritBit tree with a weight balanced tree where the weight of a node is max-depth of a subtree. My question was more towards how to quantify the performance of one tree over another for my querying pattern. With Vatine's approach, I can just do that. Once that's in place, I would surely experiment with different types of weight functions to best fit my needs. - vishwarajanand
If you look at how a CritBit tree works, it splits strictly (only) when two values differ in their bits. That means there is only one way the tree can be structured for a give set of data. There is no such thing as (re-)balancing in CritBit trees (or generally in 'tries'), because any restructuring would result in an invalid tree. - TilmannZ

1 Answers

4
votes

A height-balanced tree improves the worst-case lookup time (for a binary tree, it will always be bounded by log2(n)), at the expense of making the typical case roughly one lookup less (approximately half of the nodes will be at the maximum depth).

If your weight is related to frequency-of-lookup, a weight-balanced tree will improve the average lookup time, at the expense of making the worst case higher (more frequently requested items have a higher weight, and will thus tend to be in shallower trees, with the cost being deeper trees for less-frequently-requested items).

The best way to figure out what works best is to measure. If you can gather some representative query traffic, you can simply build a test rig where you count the tree operations (inserts, following a child pointer, ...) and replay your canned queries against both a height-balanced and a weight-balanced tree. But as a general rule, a height-balanced tree would work better the more even the request frequencies are across your data set, and the more skewed it is, the more advantage you'd get from a weight-balanced tree.