2
$\begingroup$

(Note: I couldn't put "balanced tree" in the tags ; this topic isn't about balanced search trees, just balanced trees.)

Let $A$ a binary tree.

We have the relation: $log(|A|+1) \leq h(A) \leq |A|-1$ where $|A|$ denotes the size of A (the number of nodes) and $h(A)$ its height.

Then I was told that A is balanced if $h(A) = O(log|A|)$. I don't really understand what that means. I know the symbol $O$ when we use it in maths with "$n$" stuff. For exemple $u_n = O(v_n)$ when $n \to +\infty$ or $f = O(g)$ at a certain point $x$. But there, how can we told that the tree $A$ "evolves"?

Applying the definition, it would mean that $\frac{|A|}{log|A|} \leq M$ but for a given tree, this is always true. So do we fix set the tree's size and have the relation for any size or do we fix the size and have the relation for any height, or something else?

Thanks.

$\endgroup$
2
$\begingroup$

You're right – a single tree cannot be balanced, or rather, is trivially balanced. A collection of trees can, however, be balanced meaningfully: there exists a constant $M$ such that all trees in it have height at most $M\log n$, where $n$ is the number of elements in the tree.

For example, take any algorithm that uses a binary tree. We know that operations on binary tree take time $O(h)$, where $h$ is the height of the tree. Suppose now that the algorithm maintains the property that the tree is balanced; that is, the set of all trees that occur in all executions of the algorithm forms a collection of balanced trees. Then we can bound the running time of operations on the tree at a certain point in time by $O(\log n)$, where $n$ is the number of elements in the tree at that point.

In practice, we "misuse notation" by calling a single tree balanced. What we mean that the set of all "instances" of the tree are balanced. Usually what set is meant is clear from context.

$\endgroup$
  • $\begingroup$ Thanks for your answer. So basically, what you mean is that a tree is -or not- balanced relatively to a given algorithm? $\endgroup$ – Urefeu Dec 5 '16 at 8:16
  • $\begingroup$ You can think of it this way, but it's only a special case. The general case is that a set of trees can be balanced or not. In the particular case of algorithms, we are interested in the set of trees that pop up in a specific algorithm. $\endgroup$ – Yuval Filmus Dec 5 '16 at 9:08
  • $\begingroup$ But if the set is not boundless, we can always find a constant M. And in an algorithm, we don't process a boundless set so... $\endgroup$ – Urefeu Dec 5 '16 at 11:10
  • 1
    $\begingroup$ Right, the set has to be infinite for the definition to be non-trivial. While in any particular execution there may be a finite number of trees, there are infinitely many potential executions, and we consider the trees appearing in all of them. Usually the number of elements in the trees increase with input size, and so there are infinitely many of them. $\endgroup$ – Yuval Filmus Dec 5 '16 at 11:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.