带权路径长度（WPL）

带权路径长度（WPL）#

带权路径长度是树中 所有叶节点 的路径长度与其权值的乘积之和。具体来说：

• 路径长度：从树的根节点到任一节点的边的数量（或者说从该节点到根节点的边的数量）。
• 权值：分配给树中每个节点的数值，通常反映了某种度量（如在哈夫曼树中，一个字符的频率）。

对于哈夫曼树，WPL 最小化是其设计的关键目的，意味着常见的数据（高权值）具有较短的路径长度，从而实现整体存储和传输的效率。

WPL 的计算#

假设一个树结构中，每个叶节点 $n_i$ 有一个权值 $w_i$ 和一个从根到该节点的路径长度 $l_i$，WPL 计算公式为：

$\text{WPL} = \sum_{i=1}^{k} w_i \times l_i$

其中 $k$ 是叶节点的数量。

示例#

考虑一个简单的哈夫曼树：

1
    *
2
   / \
3
  5   *
4
     / \
5
    2   3

在这个例子中，数字代表权值，星号 (*) 表示内部节点（其权值是子节点权值的和）：

• 权值为 5 的节点路径长度为 1。
• 权值为 2 的节点路径长度为 2。
• 权值为 3 的节点路径长度为 2。

计算 WPL:

$WPL = (5 \times 1) + (2 \times 2) + (3 \times 2) = 5 + 4 + 6 = 15$