# proof non-empty AVL tree

The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.

The root is not considered an single child.

let mark in numOnly a number of vertices in T that hold the attribute "single son ", and ‘with n we mark the total number of vertices in the T tree.

i need to prove that every non-empty AVL tree has inequality $$\frac{numOnly}{n}\leq \frac{1}{2}$$

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Have you worked through some examples? Have you tried to construct a counterexample?
– D.W.
Sep 16 '20 at 22:53
• Remember that a rooted tree can be viewed as root + sub-trees. Sep 17 '20 at 7:22
• i dont know how to prove the inequality Sep 17 '20 at 7:26

Given a single-child vertex $$v$$, we can show that the parent of this vertex $$v$$ cannot be a single-child. Let $$p(v)$$ be the parent of $$v$$.
If $$p(v)$$ is the root then $$p(v)$$ isn't a single-child per definition.
If $$p(v)$$ is not the root: Assume that $$p(v)$$ is a single-child then $$p(p(v))$$ has only one child. This implies that the difference in height of the subtrees of $$p(p(v))$$ must be at least $$2$$ which conflicts with the AVL-criterium and therefore implies that $$p(v)$$ is not a single-child.
Using this and the fact that for every single-child there is a unique parent, we can conclude that $$2\cdot numOnly \leq n$$.
• Is it true that every binary tree called "T" if $\frac{numOnly}{n}\leq \frac{1}{2}$ then the height of "T" maintains the condition: height(T)=O(logn)? Oct 10 '20 at 18:15