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?
$\begingroup$
$\endgroup$
1
-
$\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$– siracusaAug 20, 2019 at 1:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
