数据结构中的最佳倒立树
为字母成本不相等找到最佳的无前缀码的问题在于计算最小成本的无前缀码，其中编码字母由长度为α和β的不相等的成本（长度）字母组成，其中α≤β。我们限制自己仅限于二叉树。
该代码由一棵偏斜的树表示，就像霍夫曼树表示霍夫曼编码问题的解决方案一样。尽管有相似之处，但信件成本不相等的情况比经典的霍夫曼问题要困难得多。尽管有很多关于该问题的文献，但没有多项式时间算法是已知的或可用于一般信函成本。
但是，已知可用的多项式时间算法α和β是整数常数。
这种情况下，计算最小代价树的问题最早是由Karp于1961年研究的，他通过简化为整数线性规划解决了该问题，从而在n和β上都产生了指数算法。从那时起，在问题的各个方面进行了大量工作，例如；限制最佳树的成本；所有权重相等时对特殊情况的限制。
尽管进行了所有这些努力，令人惊讶的是，基本问题是多项式时间可解的还是NP完全的仍是未知的。
Golin和Rote描述了一种O（nβ+2）时间动态编程算法，该算法以自顶向下的方式构建树。
通过使用其他方法（单调矩阵概念，例如Monge属性和SMAWK算法），此方法得到了改进。
定理1：可以在O（nβ）时间内构建最佳的偏斜树。
对于β较小的情况，这是最有效的已知算法；实际上，信函成本通常很小（例如摩尔斯电码）。
最近，已经提供了一种有效的近似算法的方案。
定理2
对于最佳偏斜树，有多项式时间近似方案。