背景

在有序表的查找中，折半查找假设每个元素被查找的概率是相同的。现实情况下，文本中的字符被查找的概率是不相同的，为了使算法总体查找的平均长度最优化。一般会考虑构建最优查找树来处理。

最优静态查找树

$$PH=\sum _{i=1}^{n}c{p}_i$$
注

1 $c$是常量
2 $p_i$是关键字的被查找概率
所得PH值最小的二叉树就是最优查找树
注
缺点:时间复杂度$O(n^3)$

次优查找树

为了规避最优查找树构建的高时间复杂度，一般使用次优查找树来替代，性能不低于最优查找树的3%。
核心：选出一个结点，使得它左右两侧的子数组的权值累加和之差的绝对值最小。
有序序列
$r_l.key<r_{l+1}.key<...<r_h.key$
$$△P_i=|\sum _{j=i+1}^h{w}_j-\sum _{j=l}^{i-1}{w}_j|$$

为便于计算引入累计权值和
$$s{w}_i=\sum _{j=l}^i{w}_j$$
并设$w_{l-1}=0$,$s{w}_{l-1}=0$

$$\{\begin{array}{l}s{w}_{i-1}-s{w}_{l-1}={\sum }_{j=l}^{i-1}{w}_j\\ s{w}_h-s{w}_{i+1}={\sum }_{j=i+1}^h{w}_j\end{array}$$
右子树-左子树的累计权值差
$$△P_i=|(s{w}_h-s{w}_i)-(s{w}_{i-1}-s{w}_{l-1})|=|s{w}_h+s{w}_{l-1}-s{w}_i-s{w}_{i-1}|$$

具体实现如下

package main

import (
	"fmt"
	"math"
)

//次优查找树
//O(nlog(n))

//BTreeNode is node
type BTreeNode struct {
	data           string
	lchild, rchild *BTreeNode
}

//Element is list data type
type Element struct {
	data   string
	weight float64
}

func main() {
	bt := BTreeNode{}
	list := []Element{
		{data: "A", weight: 1},
		{data: "B", weight: 1},
		{data: "C", weight: 2},
		{data: "D", weight: 5},
		{data: "E", weight: 3},
		{data: "F", weight: 4},
		{data: "G", weight: 4},
		{data: "H", weight: 3},
		{data: "I", weight: 5},
	}
	sw := []float64{0}
	for i := 0; i < len(list); i++ {
		sw = append(sw, list[i].weight+sw[i])
	}
	low := 1
	high := len(list)
	SecondOptimal(&bt, list, sw, low, high)
	fmt.Println(bt)
}

//SecondOptimal 次优查找树生成 low下标从1开始
//sw[0]=0
func SecondOptimal(BT *BTreeNode, list []Element, sw []float64, low int, high int) {
	i := low
	//初始化右子树和左子树的权值差的最小值
	min := sw[high] - sw[low-1]
	//计算P的增量 dw-sw[i]-sw[i-1]
	dw := sw[high] + sw[low-1]
	for j := low + 1; j <= high; j++ {
		if math.Abs(dw-sw[j]-sw[j-1]) < min {
			i = j
			min = math.Abs(dw - sw[j] - sw[j-1])
		}
	}
	BT.data = list[i-1].data
	if i == low {
		BT.lchild = nil
	} else {
		//构造左子树
		if BT.lchild == nil {
			BT.lchild = &BTreeNode{}
		}
		SecondOptimal(BT.lchild, list, sw, low, i-1)
	}
	if i == high {
		BT.rchild = nil
	} else {
		if BT.rchild == nil {
			BT.rchild = &BTreeNode{}
		}
		SecondOptimal(BT.rchild, list, sw, i+1, high)
	}
}