ハフマン木の最適領域の隣接性について

概要

論文の詳細を見る
ハフマン木は有用なデータ構造としてこれまで多くの研究がなされている.キーとその重みが与えられた場合にハフマン木は簡単に計算をすることができることはよく知られている.重み付き拡張二分木が最適であるとは,他の全ての拡張二分木の中でその二分木が最も重み付き路長和を最小にする場合である.拡張二分木の最適領域とは,重み空間の領域であり,その中に含まれる重みはその二分木を最適とする.本論文では,ハフマン木の最適領域の性質についての研究を行う.レベルベクタとは,拡張二分木のそれぞれの葉までの路長をベクトルとして表現した形式であり,本稿ではレベルベクタとハフマン木を同一視する.まず,どの最適領域も非空かつ、凸集合であることを示す.また,2つのハフマン木の最適領域が隣接しているとは,ある重みが存在し,その重みでその2つのハフマン木だけが最適になると定義する.この最適性の必要十分条件が次の2つであることを証明する:1)葉のレベル差が高々1である;2)その2つのハフマン木のレベルベクタの和が他のどの2つのレベルベクタの和としても表されない.
2004-03-19