次优二叉查找树（次优查找树)_递归和非递归实现_20230414

次优二叉查找树（次优查找树)-递归和非递归实现

1. 前言

当有序表中的各记录的查找概率相等的时候，采用折半查找效率可以提升查找性能；如果有序表中的各记录的查找概率不相等，那么折半查找就不再适用。

如果只考虑查找成功的情况，则使查找性能达到最佳性能的判定树就是带权路径长度的之和,也即路径各个记录的查找深度与查找权值的乘积之和，当这个和取得最小值的时候。
$$PH=\Sigma c_i\ast w_i,i\in (\mathrm{1....}n)$$
最优二叉查找树需要利用到动态规划的相关知识，之前的文章有所涵盖，有兴趣的读者可查阅之前的文章进行理解。本文所阐述的方法，采用的是贪婪的编程思维，构建出次优二叉查找树(Nearly optimal binary search tree)。

2. 问题分析

已知一个按照关键有序的记录:

(r_l,r_l+1…r_h)

其中关键字为升序排列，对于每个记录的权值

(w_l,w_l+1…w_h)

现在构造一颗二叉树，是这颗二叉树的带权路径长度PH在同样的二叉树中近似最小，我们称这类二叉树为次优二叉树。

利用贪婪方法，构造次优查找树的方法是：首先在序列l…h构造根节点root(i)，使根节点左右两颗子树的差值取最小值，那么这个点就是根节点。采用公式，让理解更为方便。

Δpi=|Σwj(i+1<j<h)-Σwj(l<j<i-1)|

求得i之后，然后分别对子序列(r_l,r_l+1…r_i-1)和(r_i+1,r_r+2…r_h)再分别构造两颗次优二叉树，并设定其根节点为root(i)，分别定位root(i)的左子树和右子树。

根据上面的分析，引入递归算法和非递归算法构造次优二叉书。

3. 递归算法分析

由于构造二叉树的过程需要分别对左右子树进行处理，所以整体的需要涉及两次递归调用。二叉树的构造过程和遍历过程非常类似，都是对左右子树访问的过程。针对本问题，我们选择先序遍历模式完成问题的解答。

由于采用递归，那么递归的结束条件是什么呢？ 递归的结束条件就是遍历到叶子结点，在本问题当中，可以理解问题根节点的下标等于high或者low的时候，此时递归就满足结束条件（不再进行入栈操作）。

4. 递归代码C语言实现

递归函数的操作对象为记录的权值和，在递归函数之前需要求解sw[0…n-1]，我们使用void find_sw(int *sw, SSTable st)函数完成此项任务。

递归函数中包含子树下标的最小值与最大值，在先序递归之前，通过迭代求出根节点所在位置，然后与high和low进行比较，我们使用void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)函数完成这项任务。

a.) find_sw函数实现,注意第1个元素的sw值为0

void find_sw(int *sw, SSTable st)
{int i;*(sw + 0) = 0;for (i = 1; i <= st.len; i++){sw[i] = sw[i - 1] + st.elem[i].value;}
}

b.) second_optimal函数实现

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)
{int min;int i;int j;int dw;int delta;min=INT_MAX;dw=sw[high]+sw[low-1];i=low;for(j=i;j<=high;j++){delta=abs(dw-(sw[j]+sw[j-1]));if(delta<min){i=j;min=delta;}}*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=rec[i];if(i==low){(*bt)->lchild=NULL;}else{second_optimal(&((*bt)->lchild),rec,sw,low,i-1);}if(i==high){(*bt)->rchild=NULL;}else{second_optimal(&((*bt)->rchild), rec, sw, i + 1, high);}
}

5. 非递归实现

为了实现非递归建立次优二叉查找树，就需要借助栈(stack)的概念，本质是就是借助自定义栈来实现编译器中的函数栈的管理。栈实际上储存的是记忆的状态，采用“后进先出”模式来模拟编译器中的函数栈。我们在利用栈实现功能之前，首先需要定义过程中需要记忆(保存)哪些参数。很明显，对于本问题，我们至少需要保留三个变量参数的当前状态，下一个待处理二叉树结点的指针（它必定来自于当前结点的左孩子或者右孩子），子树需要处理的范围，也就是low和high的下标位置，有了这些背景分析，定义栈保存的元素：

typedef struct StackNode
{BiTree node;int    low;int    high;
}StackNode;

基于上述定义，非递归次优二叉树实现函数如下：

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int len)
{int min;int i;int j;int delta;int dw;int low;int high;SqStack S;StackNode st_node;StackNode temp;low=1;high=len;InitStack_Sq(&S);st_node.low=low;st_node.high=high;st_node.node=(BiTree)malloc(sizeof(BiTNode));*bt = st_node.node;Push_Sq(&S,st_node);while(!StackEmpty_Sq(S)){Pop_Sq(&S,&temp);low=temp.low;high=temp.high;i=low;min=INT_MAX;dw=sw[high]+sw[low-1];for(j=i;j<=high;j++){delta=abs(dw-sw[j]-sw[j-1]);if(delta<min){i=j;min=delta;}}temp.node->data=rec[i];//it should start with from pushing the right child into the stackif(i==high){temp.node->rchild=NULL;}else{st_node.low=i+1;st_node.high=high;temp.node->rchild=(BiTree)malloc(sizeof(BiTNode));st_node.node=temp.node->rchild;// here it is st_node.node instead of st_node.node->rchildPush_Sq(&S, st_node);}if (i == low){temp.node->lchild = NULL;}else{st_node.low = low;st_node.high = i - 1;temp.node->lchild = (BiTree)malloc(sizeof(BiTNode));st_node.node= temp.node->lchild;// here it is st_node.node instead of st_node.node->lchildPush_Sq(&S, st_node);}}}

上述函数的实现涉及到栈操作，有兴趣的读者可以参考《数据结构》严蔚敏版自行实现，在此不再赘述。对于上述非递归代码，请读者自行理解。

6. 总结

次优二叉查找树是一种基于贪心算法实现的二叉树，它摒弃了动态规划建立最优二叉树的繁琐流程，同时又保留了查询的效率。本文针对次优二叉树，采用递归和迭代两种不同的方式加以实现，加深了对递归的理解，同时也复习了栈(stack)的相关知识。

参考资料：

1. 《数据结构》-清华大学，严蔚敏