New answers tagged


Your dynamic program is a step in the right direction. My idea would be to maintain two values for a node v: $L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases) $U_v$: and the longest path in the subtree of v (i.e., case 3). You already gave the formula for $L_v$. For $U_v$ you take ...


You are correct $-$ the red-black tree you have drawn is not balanced. For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed. However ...


Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore $$ d(h) = \min(d(h-1),d(h-2)) + 1. $$ Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of ...


This is case 4, because w's right child is red. the left child (of z) could have any color red/black.

Top 50 recent answers are included