次优查找树的查找原理

本文主要是介绍次优查找树的查找原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者：Sullivan
链接：https://www.zhihu.com/question/21063814/answer/84913614
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1、 次优查找树是折半查找的一种一般形式，其理论基础是“被查找的各元素是不等概的”，而折半查找就是等概的，我们在使用中默认了这一性质。
比如，对于有序数组

int a = {1,2,3,4,5};

用折半查找时，应该现比较最中间的3，如果如果待查整数等于3，查找结束。如果小于3，就继续在左边的部分数组里查找；反之，在右边的数组里查找。
问题在于，我们为什么不从4开始找呢？为什么不从1开始呢？
因为在等概率的情况下，这样能让整体的平均搜索的长度（也就是次数）最小，实际也是二分查找树的深度最小。因为相同结点数的二叉树，越是丰满的二叉树高度越小。也就是说，每个节点的左右子树的高度差最小，二叉树的高度就越小，查找越底层的元素所需要的路径长度就越短，比较次数也越少（相同结点数完全二叉树的深度小于等于其他形态的二叉树的深度）。
我的ubuntu不好画图，给你个链接看看，你自己也可以画一下图。具有12个关键字的有序表,折半查找的平均查找长度()_牛客网。你把每个元素查找成功时的路径长度加起来看看，是不是完全二叉树最小？

2、现在我告诉你，每个元素被查找的概率是不一定相同的。刚才的办法还是最佳的吗？
比如按照刚才的查找树，元素5是最后一个，按照折半查找的话，每次查找都要花费3次比较才能找到，然而元素5被查找的概率是0.8，也就是说查了10000次，可能8000次都是它，那么这8000次查找就用了 times = 8000 * 3 = 24000次查找。但是如果把5放到查找树的根节点位置，那么是不是只需要8000次比较就行了？
所以，对于每个元素被查找的概率不同的情况下，折半查找不是最佳方法！

3、如果仅仅考虑查找成功的情况，构造一颗静态最优查找树的性能是最好的。
用数学公式来表示就是：使得 $PH = \sum_{i=1}^{n}{\omega_{i}h_{i}}$ 的PH值最小的树为该数组的静态最优查找树。其中i为节点标号， $\omega _{i}$ 为节点i的带权路径长度， $\omega _{i} = c _{i} * p _{i}$ ，它等于结点i的查找路径长度c，乘以该结点被查找的概率p；h表示节点i在搜索树中的高度。
通俗点来说，就是权值越大的结点，越放到靠近根结点的位置！这个很好理解，这种结点要么查找概率大，要么需要的比较次数（折半查找中的次数）多，要么以上两者都占了，当然应该越早查越好啊，对不对？
然并卵，这种树的构造时间复杂度为 $\Theta (n^{3})$ ，等你构造出来，天早就黑了好么……
关于为什么它的时间复杂度这么高，请参考http://www.cs.rutgers.edu/~kaplan/503/handouts/optimalbst.html或者Dynamic Programming

4、那么肿么办呢？我们来构造次优查找树。
书上首先就告诉你了，这种树的查找效率很少低于最优查找树的3%。
核心：选出一个结点，使得它左右两侧的子数组的权值累加和之差的绝对值最小。把这个结点当做根节点，递归地用刚才的左右字数组构造它的左右子树。
数学表达式： $\Delta P_{i} = |\sum_{j=i+1}^{h}{\omega _{j}} - \sum_{j=l}^{i-1}{\omega _{j}}|$ 。
之前的折半查找树是为了让左右子树的高度差尽量小，现在你就把高度的概念替换为权值之和来理解，就好了。为什么要让左右子树的权值累加和之差最小？为了使树的深度最小。

说了这么多，下面来上代码。请从主函数开始看，应该算是简单易懂
bitree.h 这里是树的二叉链表和各种遍历打印的定义。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;typedef struct TNode
{int data;struct TNode* lchild;struct TNode* rchild;
}BiTree, *pBiTree;void creat_tree(pBiTree &rt)
{char ch;ch=getchar();if('#'==ch){rt=NULL;}else{rt=(pBiTree)malloc(sizeof(BiTree));rt->data=ch;creat_tree(rt->lchild);        //构造左子树creat_tree(rt->rchild);    //构造右子树}
}void PreOrderPrint(pBiTree &rt)
{cout << "PreOrderPrint: ";if(!rt)return;stack<pBiTree> s;s.push(rt);while(!s.empty()){pBiTree cur = s.top();cout << (char)(cur->data);s.pop();if(cur->rchild)s.push(cur->rchild);if(cur->lchild)s.push(cur->lchild);}cout << '@' << endl;
}void InOrderPrint(pBiTree &rt)
{cout << "InOrderPrint: ";if(!rt)return;stack<pBiTree> s;pBiTree cur = rt;while(!s.empty() || cur != NULL){while(cur){s.push(cur);cur = cur->lchild;}if(!s.empty()){cur = s.top();cout << (char)(cur->data);s.pop();cur = cur->rchild;}}cout << '@' << endl;
}bool visit(pBiTree &node)
{if(node){cout << char(node->data);return 1;}elsereturn 0;
}void LevelOrderPrint(pBiTree &rt)
{cout << "LevelOrderPrint: ";if(!rt){cout << "@" << endl;return;}queue<pBiTree> q;q.push(rt);pBiTree cur = NULL;while(!q.empty()){cur = q.front();q.pop();if(visit(cur)){if(cur->lchild)q.push(cur->lchild);if(cur->rchild)q.push(cur->rchild);}}cout << "@" << endl;
}

second_optimal.cpp 这里是创建次优二叉树的实现

//second optimal tree
//suanfa93.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include "bitree.h"
using namespace std;void AssignVal(int* val, int low, int high, int factor)
{if(!val || low < 0 || low > high)return;if(low == high){val[low] = factor;return;}int mid = (low + high) / 2;val[mid] = factor;AssignVal(val, low, mid-1, factor+1);AssignVal(val, mid+1, high, factor+1);
}int* SearchLength(int len)
{if(len <= 0)return NULL;int* sl = (int*)malloc(sizeof(int) * len);if(!sl)exit(0);AssignVal(sl, 0, len-1, 1);return sl;
}float* SumWeight(int* nodes, float* prob, int size)
{float* sw = (float*)malloc(sizeof(float) * size);if(!sw)exit(0);float before = 0.0;for(int i = 0; i < size; i++){sw[i] = nodes[i] * prob[i] + before;before = sw[i];}return sw;
}void SecondOptimal(pBiTree &rt, int* nodes, float* sw, int low, int high)
{if(!nodes || !sw || low < 0 || low > high)return;int i = low;float min = fabs(sw[high] - sw[low]);float dw = sw[high]; for(int j = low + 1; j <= high; ++j){float tmp = fabs(dw - sw[j] - sw[j-1]);if(tmp < min){i = j;min = tmp;}}rt = (pBiTree)malloc(sizeof(BiTree));if(!rt)exit(0);rt->data = nodes[i];if(i == low)rt->lchild = NULL;elseSecondOptimal(rt->lchild, nodes, sw, low, i-1);if(i == high)rt->rchild = NULL;elseSecondOptimal(rt->rchild, nodes, sw, i+1, high);
}int main(int argc, char const *argv[])
{//1、已知条件，待查找的有序数组和数组中各元素被查找的概率(不等概率)const int size = 5;int nodes[size] = {'1','2','3','4','5'};float probability[size] = {0.2,0.3,0.2,0.1,0.2};//2、根据数组，求出每个元素查找成功时的平均查找长度（次数），存储在schlen数组中。int* schlen = SearchLength(size);//3、求出每个元素的权值sw，由待查数组nodes和schlen中下标相对的元素相乘得到。float* sw = SumWeight(schlen, probability, size);//4、然后根据书中的算法，递归的构造次优查找树pBiTree root;SecondOptimal(root, nodes, sw, 0, size - 1);//5、用前序、中序、层序遍历把次优查找树打印出来看看PreOrderPrint(root);InOrderPrint(root);LevelOrderPrint(root);return 0;
}