# About the definition of a balanced tree

(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.

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.