Optimal alphabetic binary tree for a nonregular cost function
type: Item
instance of: scholarly article
title: Optimal alphabetic binary tree for a nonregular cost function
zbMATH Open document ID: 0551.68057
DOI: 10.1016/0166-218X(84)90128-8
author: Cun-Quan Zhang
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3878375
zbMATH Keywords: cost function of a binary tree
zbMATH Keywords: algorithm
zbMATH Keywords: optimal alphabetic binary tree
MaRDI profile type: Publication
cites work: Optimal Computer Search Trees and Variable-Length Alphabetical Codes
cites work: Binary Trees Optimum Under Various Criteria
description: scientific article; zbMATH DE number 3878375