1
$\begingroup$

I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close the shape of a tree is to a "fully balanced" tree, or how "skewed" the tree is.

I was thinking a possible metric would be the ratio of the number of nodes in the tree to the number of nodes in a fully balanced tree of the same height. This seems relatively naive though, and I was wondering if better metrics exist to measure how skewed/balanced a tree is.

$\endgroup$
  • $\begingroup$ There are many possible metrics. I don't know how we can tell you what to use, without knowing what you want or how you'll use it. You ask if "better" metrics exist, but how do you define better? Better in what sense? How will you evaluate answers? The question doesn't seem to be well-defined enough to be a good fit yet (see our help center); we need objectively answerable questions that enable answerers to know whether they have met the requirements, and readers to judge whether answers are correct. $\endgroup$ – D.W. Jul 3 '18 at 6:36
  • $\begingroup$ It very much depends on your application of the balancedness. Perhaps there are times where the ratio makes sense, but perhaps more often you would you the "cost" of making the tree "fully balanced". That is, suppose you are allowed to do small modifications to the tree (delete node, swap nodes, insert node, detach and reattach a subtree). Then the balancedness could be the number of operations you would need, and a fully balanced tree would have balancedness 0. $\endgroup$ – Pål GD Jul 3 '18 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.