张老师根据自己工作的需要,设计了一种特殊的二叉搜索树。他把这种二叉树起名为 zh_tree,对于具有 个结点的 zh_tree,其中序遍历恰好为 ,其中数字 是每个结点的编号。 个结点恰好对应于一组学术论文中出现的n个不同的单词。第 个单词在该组论文中出现的次数记为 ,例如, 表示第 个结点所对应的单词在该组论文中出现了 次。
设该组论文中出现的单词总数为 ,显然,。记 为第 个单词在该组论文中出现的概率(频率)。 张老师把根结点深度规定为 ,如果第 个结点的深度为 ,则访问该结点的代价 为 ,其中 为已知的不超过 的正常数。 则 zh_tree 是满足以下条件的一棵二叉树:它使 达到最小。我们称上式为访问zh_tree的平均代价。
请你根据已知数据为张老师设计一棵 zh_tree。