1
$\begingroup$

If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken an arbitrary tree with a left subtree containing $i$ nodes and the right subtree containing $n-i-1$ nodes.

Correct me if I'm misunderstanding this, but since these left and right subtrees can be anything (where $i=0,1,2,...,n-1$) then the average of $D$ is given by $$\langle D \rangle=\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+\sum_{i=0}^{n-1}(n-1)\right)$$ where I divided by $n$ since there are $n$ different left/right-subtree possibilities. What I don't understand is that online sources and my textbook equates this to $D$ itself. In other words, I don't quite understand why we're allowed to set $\langle D(n) \rangle = D(n)$.

Ignoring that, I continued on and I'm also running into the problem where my book is writing $$ D(n) =\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+(n-1)\right)$$ and seems to be ignoring the sum altogether. The reason why I say this is because later the book claims that $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+n(n-1)$$ This doesn't make any sense to me since I had a $$\sum_{i=0}^{n-1}(n-1)\in O(n^2)$$ term in my expression so multiplying by another $n$ should be give me something like $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+O(n^3)$$ instead. I feel like I'm missing something obvious but I can't quite figure it out. Any ideas?

$\endgroup$
1
$\begingroup$

Suppose that $T$ is a random tree on $n$ vertices, according to the distribution you consider. Let $T_L,T_R$ be its two subtrees, and let their size be $N_L,N_R$. Let $P$ be the total path length of $T$. Let $P_L(i)$ be the total path length of $T_L$ if $N_L=i$, and zero otherwise, and define $P_R(i)$ similarly. We have $$ P = \sum_{i=0}^{n-1} (P_L(i) + P_R(n-1-i)) + n-1. $$ According to linearity expectation, we have $$ \mathbb{E}[P] = \sum_{i=0}^{n-1} (\mathbb{E}[P_L(i)] + \mathbb{E}[P_R(n-1-i)]) + n-1. $$ By definition, $\mathbb{E}[P] = D(n)$, where $D(n)$ is the expected internal path length of a random tree on $n$ vertices.

According to your probability distribution, the probability that $N_L=i$ is $1/n$. When that happens, $T_L$ is just a random tree on $i$ vertices. Therefore $$ \mathbb{E}[P_L(i)] = \Pr[N_L=i] \mathbb{E}[P_L(i)|N_L=i] + \Pr[N_L\neq i] \mathbb{E}[P_L(i)|N_L\neq i] = \\ \frac{1}{n} \cdot D(i) + \left(1-\frac{1}{n}\right) \cdot 0 = \frac{D(i)}{n}. $$ Therefore we obtain the recurrence $$ D(n) = \frac{1}{n} \sum_{i=0}^{n-1} (D(i) + D(n-1-i)) + n-1 = \frac{2}{n} \sum_{i=0}^{n-1} D(i) + n-1. $$ Equivalently, $$ nD(n) = 2\sum_{i=0}^{n-1} D(i) + n(n-1). $$ The initial condition is $D(0) = 0$.

We can solve this recurrence using generating functions. Let $P(x) = \sum_{n=0}^\infty D(n) x^n$. First, $$ P'(n) = \sum_{n=1}^\infty nD(n) x^{n-1}. $$ Second, $$ \frac{P(n)}{1-x} = \sum_{n=0}^\infty [D(0) + \cdots + D(n)] x^n. $$ Third, $$ \sum_{n=0}^\infty n(n-1) x^{n-2} = \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2}{(1-x)^3}. $$ Putting everything together, we obtain $$ P'(x) = \sum_{n=1}^\infty nD(n) x^{n-1} = 2\sum_{n=1}^\infty (D(0) + \cdots + D(n-1)) x^{n-1} + \sum_{n=1}^\infty n(n-1) x^{n-1} = \\ \frac{2P(x)}{1-x} + \frac{2x}{(1-x)^3}. $$ The solution to this ODE is $$ P(x) = \frac{-2\log (1-x)-2x}{(1-x)^2} = \frac{1}{(1-x)^2} \sum_{n=2}^\infty \frac{2}{n} x^n, $$ which implies that $$ D(n) = 2\sum_{m=2}^n \frac{n-m+1}{m} = 2(n+1)(H_n-1)-2(n-1) = 2(n+1)H_n-4n. $$ Since $H_n = \ln n + \gamma + 1/2n + O(1/n^2)$, we deduce that $$ D(n) = 2(n+1)(\ln n + \gamma + 1/2n + O(1/n^2)) - 4n = \\ 2n\ln n + 2\ln n + (2\gamma-4) n + 2\gamma + 1 + O(1/n). $$

$\endgroup$
0
$\begingroup$

You don't need to multiply by $n$ in the last but one expression, because the right hand side of the D(n) expression has the factor $\frac{1}{n}$.

So you only have to explain the $\mathcal{O}(n^2)$ versus $\mathcal{O}(n)$ terms; not the $\mathcal{O}(n^3)$ versus $\mathcal{O}(n)$ terms.

Also, I have a doubt whether one can take $i$ to be really arbitrary (e.g. 0) in the first expression. When $i=0$ it means the left sub-tree is empty, so the initial is not really a binary tree.

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