次优二叉查找树(次优查找树)-递归和非递归实现
- 前言
当有序表中的各记录的查找概率相等的时候,采用折半查找效率可以提升查找性能;如果有序表中的各记录的查找概率不相等,那么折半查找就不再适用。
如果只考虑查找成功的情况,则使查找性能达到最佳性能的判定树就是带权路径长度的之和,也即路径各个记录的查找深度与查找权值的乘积之和,当这个和取得最小值的时候。
P
H
=
Σ
c
i
∗
w
i
,
i
∈
(
1....
n
)
PH=Σc_i*w_i,\ i∈(1....n)
PH=Σci∗wi, i∈(1....n)
最优二叉查找树需要利用到动态规划的相关知识,之前的文章有所涵盖,有兴趣的读者可查阅之前的文章进行理解。本文所阐述的方法,采用的是贪婪的编程思维,构建出次优二叉查找树(Nearly optimal binary search tree)。
- 问题分析
已知一个按照关键有序的记录:
(rl,rl+1…rh)
其中关键字为升序排列,对于每个记录的权值
(wl,wl+1…wh)
现在构造一颗二叉树,是这颗二叉树的带权路径长度PH在同样的二叉树中近似最小,我们称这类二叉树为次优二叉树。
利用贪婪方法,构造次优查找树的方法是:首先在序列l…h构造根节点root(i),使根节点左右两颗子树的差值取最小值,那么这个点就是根节点。采用公式,让理解更为方便。
Δpi=|Σwj(i+1<j<h)-Σwj(l<j<i-1)|
求得i之后,然后分别对子序列(rl,rl+1…ri-1)和(ri+1,rr+2…rh)再分别构造两颗次优二叉树,并设定其根节点为root(i),分别定位root(i)的左子树和右子树。
根据上面的分析,引入递归算法和非递归算法构造次优二叉书。
- 递归算法分析
由于构造二叉树的过程需要分别对左右子树进行处理,所以整体的需要涉及两次递归调用。二叉树的构造过程和遍历过程非常类似,都是对左右子树访问的过程。针对本问题,我们选择先序遍历模式完成问题的解答。
由于采用递归,那么递归的结束条件是什么呢? 递归的结束条件就是遍历到叶子结点,在本问题当中,可以理解问题根节点的下标等于high或者low的时候,此时递归就满足结束条件(不再进行入栈操作)。
- 递归代码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);
}
}
- 非递归实现
为了实现非递归建立次优二叉查找树,就需要借助栈(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 stack
if(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->rchild
Push_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->lchild
Push_Sq(&S, st_node);
}
}
}
上述函数的实现涉及到栈操作,有兴趣的读者可以参考《数据结构》严蔚敏版自行实现,在此不再赘述。对于上述非递归代码,请读者自行理解。
- 总结
次优二叉查找树是一种基于贪心算法实现的二叉树,它摒弃了动态规划建立最优二叉树的繁琐流程,同时又保留了查询的效率。本文针对次优二叉树,采用递归和迭代两种不同的方式加以实现,加深了对递归的理解,同时也复习了栈(stack)的相关知识。文章来源:https://www.toymoban.com/news/detail-415370.html
参考资料:文章来源地址https://www.toymoban.com/news/detail-415370.html
- 《数据结构》-清华大学,严蔚敏
到了这里,关于次优二叉查找树(次优查找树)_递归和非递归实现_20230414的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!