How proof of Hoffman algorithm greedy property starts with optimal tree T?

Question

In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts with tree T which has b and c at the maximum depth of tree. I can't understand why tree T is called optimal, because if x and y have smallest probabilities, then tree T cannot be optimal because Hoffman algorithm won't build such tree. I think my problem here is with understanding what optimal tree means.

If someone comes from CSLR this is about lemma 16.2 and proof to that.

Answer 1

A code tree is optimal if the average codeword length is minimal. This has nothing to do with Huffman's algorithm. Huffman's algorithm is guaranteed to produce an optimal code tree, but there might be other code trees. In fact, Huffman's algorithm could produce different code trees using different tie-breaking rules. Moreover, not every optimal code tree can be produced using Huffman's algorithm, even with an arbitrary tie-breaking rule.

Here is a formal definition of an optimal code tree. Let $\pi$ be a distribution. The $\pi$-cost of a code tree is the expected length of a codeword, where the expectation is taken with respect to $\pi$. A code tree is optimal for $\pi$ if its $\pi$-cost is equal to the minimum $\pi$-cost of any code tree.