Optimal alphabetic binary tree for a nonregular cost function
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.
- Operations research applications of dichotomous search
- On the Huffman and alphabetic tree problem with general cost functions
- Optimal alphabetic trees for binary search
- scientific article; zbMATH DE number 4173001 (Why is no real title available?)
- scientific article; zbMATH DE number 4031716 (Why is no real title available?)
- The Optimal Alphabetic Tree problem revisited
- Old and new results on alphabetic codes
This page was built for publication: Optimal alphabetic binary tree for a nonregular cost function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800733)
