0
$\begingroup$

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them being 0?

$\endgroup$
  • $\begingroup$ If you enforce a balance difference of zero, your tree can't hold an arbitrary number of elements anymore (only $2^k-1$ nodes, I think). For example, how would you arrange your tree when it has only two nodes? $\endgroup$ – siracusa Aug 20 at 1:37
0
$\begingroup$

What matters is that the height of the tree is limited by $O(\log n)$. As long as you maintain that property your searches will remain efficient.

Forcing the height difference to be zero we get the above property. However we also get the property if we allow the difference to be 1. The crux is that the latter requires a lot less rebalancing to achieve. The average height of a node will very slightly increase due to our more relaxed tree structure but this downside is greatly overshadowed by the reduction in rebalancing operations.

$\endgroup$

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.