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}$

  • 3
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Sep 16 '20 at 22:53
  • $\begingroup$ Remember that a rooted tree can be viewed as root + sub-trees. $\endgroup$
    – greybeard
    Sep 17 '20 at 7:22
  • $\begingroup$ i dont know how to prove the inequality $\endgroup$
    – Eden Gilad
    Sep 17 '20 at 7:26

If the tree hasn't any single-children the hypothesis trivially holds.

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

  • $\begingroup$ 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)? $\endgroup$
    – Eden Gilad
    Oct 10 '20 at 18:15
  • $\begingroup$ anyone can tell me if its true? $\endgroup$
    – Eden Gilad
    Oct 11 '20 at 10:51

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.