CODEWITHSUNDEEP
algorithmsortingdata-structurestreebinary-tree
vishwarajanand
vishwarajanand

Reputation: 1071

Compare height balanced tree to weight balanced tree

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?

Upvotes: 1

Views: 727

Answers (1)

Vatine
Vatine

Reputation: 21258

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.

Upvotes: 4

Related Questions