Optimal alphabetic binary tree for a nonregular cost function (Q800733)

A nonregular cost function of a binary tree T is defined by \[ f(T)=\sum_{v\in T}w(v), \] where \(w(v)=\max \{w(v'),w(v'')\},\) if v' and v'' are the sons of v. The following algorithm will construct the optimal alphabetic binary tree with a given weighted terminal node sequence: 1. In the node sequence \(\{v_ 1,...,v_ n\},\) combine the node \(v_ i\) of the smallest weight with its smaller neighbour \(v_{i-1}\) (or \(v_{i+1}),\) to form a new node \(v_{(i-1,i)},\) as the father of \(v_{i-1}\) and \(v_ i;\) 2. Get a new sequence \(\{v_ 1,...,v_{i-2},v_{(i- 1,i)},v_{i+1},...,v_ n\}\) of length \(n-1;\) 3. Repeat step 1 and 2 on the new sequence, until the sequence becomes of length one.