最优二叉查找树和普通二叉查找树有什么区别？

二叉搜索树和最优二叉搜索树的时间复杂度各是多少？~

二叉查找树（BST，Binary Search Tree） ，又名二叉搜索树或二叉检索树，是一颗满足如下条件的树：
1、每个节点包含一个键值
2、每个节点有最多两个孩子
3、对于任意两个节点x和y，它们满足下述搜索性质:
a、如果y在x的左子树里，则key[y] <= key[x]
b、如果y在x的右子树里，则key[y] >= key[x]

最优二叉查找树（Optimal BST，Optimal Binary Search Tree）
最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是：给定键值序列 K = ，k1 < k2 <· · · < kn ，其中键值ki ,被查找的概率为pi ，要求以这些键值构建一颗二叉查找树T，使得查找的期望代价最低（查找代价为检查的节点数）。
下面是对于查找期望代价的解释：
对于键值ki , 如果其在构造的二叉查找树里的深度（离开树根的分支数）为depthT(ki )，则搜索该键值的代价= depthT(ki ) +1（需要加上深度为0的树根节点）。由于每个键值被查找的概率分别为pi ，i=1,2,3…,n。所以查找期望代价为：
E[T的查找代价] = ∑i=1~n (depthT(ki ) +1) · pi
时间复杂度
1、穷举
穷举构造最优二叉查找树，其实就是这样的一个问题：
给一个拥有n个数的已排序的节点，可以将其构造成多少种不同的BST（用来找到一个最优的二叉查找树）？
设可以构造成T(n)个，那么枚举每一个元素作为根节点的情况，当第一个元素作为根节点时，其余n-1个构成右子树，无左子树，是n-1情况时的子问题， 共T(n-1)种；当第二个元素作为根节点时，左子树有1个元素，右子树有n-2个元素，根据乘法原理共有T(1)T(n-2)种情况……依此类推得 到：T(n) = T(0)T(n-1) + T(1)T(n-2) + T(2)T(n-3) + ...... + T(n-2)T(1) + T(n-1)T(0)；此外，有T(0)=T(1)=1。
下面来求解T(n)：
定义函数 f(x) = T(0) + T(1) · x + T(2) · x2 + ......
那么有：
f(x)2 = (T(0)2 ) + (T(0)T(1) + T(1)T(0)) · x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) · x2 + ......
= T(1) + T(2) · x + T(3) · x2 + ......
= (f(x) - T(0)) / x
= (f(x) - 1) / x
这样解方程得到 f(x) = [1 - (1 - 4x)1/2 ] / 2x
右边进行泰勒展开，再与定义式比较最终得到： T(n) = (2n)! / (n!(n+1)!)
然后根据Stirling公式：n! ～ (2πn)1/2 · (n/e)n
于是有(2n)! / n!(n+1)! ～ (4n1/2 · 2n2n ) / (2n1/2 · nn · (2(n+1))1/2 · (n+1)n )
～ 4n · (n+1)-3/2 · (n/(n+1))n
～ 4n · n-3/2
因此最后得到穷举方法构造最优二叉查找树的时间复杂度： T(n) = O(4n · n-3/2 )

2、递归
实际上左右子树是互不影响的，不需要穷举所有左右子树的组合，所以不需要用乘法原理，加法原理就可以了，这样式子变为：
T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0)
= 2(T(0) + T(1) + T(2) + ...... + T(n-1))
= 3T(n-1)
所以得到T(n) = O(3n ) ，还是指数级的一个算法

3、动态规划
上面得到指数级算法的原因在于，计算了很多重复的子树情况，一些子树的查找代价被计算了很多遍；而一棵树如果是最优二叉搜索树，那么要么它是空树，要么它 的左、右子树也是最优二叉搜索树，因此只需要将子树的查找代价记录下来，采用记忆化搜索或者是自底向上的动态规划的方法，虽然需要消耗一定的空间，但可以 把时间复杂度从指数级降到多项式级，这些空间消耗也是可以接受的。
以下是采用自底向上的解法：
输入：键值序列 K = ，概率序列 P =
输出：两个二维数组，Price[i][j]表示ki 到kj 构成的最优子树的查找代价，Root[i][j]表示表示ki 到kj 构成的最优子树的根节点位置（用于重构最优二叉查找树）
算法1 ：
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1，长度为size
For 该子树的所有节点作为根节点root = start to end
对于每个root，根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：
左右子树的最优子树代价之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中

下面分析这个算法的时间复杂度：
由于除了计算出我们最后需要得到的Price和Root二维数组，还产生了部分冗余的子树，因此不能简单的将算法归结为O(n2 )的算法。
对于子树大小为1时，我们考察了n个子树；
对于子树大小为2时，一共产生了(n - 1)个最优子树，但是在我们的每次考察中，都将子树的所有节点作为根节点考虑过一次，因此每得到1个大小为2的子树，我们需要考察2个不同的子树来找到一 个代价最小的，因此最后我们实际上考察了2(n - 1)个子树；
对于子树大小为3时，类似的，我们考察了3(n - 2)个子树；
……
对于子树大小为n时，我们考察了n个子树。
最后，我们一共考察了T(n) = n + 2(n - 1) + 3(n - 2) + ...... + n个子树。
求解这个公式依然可以借用之前的方法，定义函数 f(x) = 1 + 2x + 3x2 + ...... = (1 - x)-2
这样一来 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ......
再借用泰勒展开得到 T(n) = (n + 2)(n + 1)n/6 = O(n3 )
或者把所有项视为n2，则有 T(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3
把中间n/2项都视为n/4 · 3n/4的话，则有 T(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3
根据时间复杂度的定义有 T(n) = O(n3 )


下面介绍一个定理，可以借此把动态规划算法的时间复杂度进一步降到O(n2 )，详细的证明参见参考文献：
定理1 ：Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] （Root数组定义见算法1）

也就是说，算法1的第3个For就可以不用循环子树中的所有节点了，只要循环另两个子树的根节点之间的范围就可以了。算法如下，红色的为修改的部分：
算法2 ：
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1，长度为size
For 该子树的所有节点作为根节点root = Root[start][end-1] to Root[start+1][end]
对于每个root，根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：
左右子树的最优子树代价之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中
在分析该算法的时间复杂度时应注意，考察的子树是与考察的内层循环中root数量一一对应的，而当start递进时，前一个root的终点正好等于后一个root的起点（算法中的红色部分），也就是说对于固定的size来说，考察的root的范围加起来应当首位相接 而且至多刚好覆盖 所有节点，因此对于每个size，最多只考察2n个root（这里缩放了一下），因此总共最多考察了2n · n = 2n2 个子树；另一方面，Root数组中每一个值对应得到的一个最优二叉查找树，也即至少需要考察n2 个子树。因此根据定义得到 T(n) = O(n2 )

最小生成树是用和最少的边集将一个图连成任意2点可达，并且这个边集的总长度最小。最短路径是一个图中2个点的最短距离。完全不是一个概念。

那也不一样啊，一点到其余各点的路径和最小，就是一点到其它点的最短路径和。差的太远了。

比如这样一个图(边权已标出)
******4
*****v--v
****5 \ / 3
*******v
****2 / \ 4
*****v v
最小生成树为
****v--v
******/
*****v
****/ \
***v v
总长为4+3+2+4=13

中间那个点到各点的最短路径为5+2+3+4=14
显然不一样啊，反例太多了，举了一种。

最优，就是查找效率最快。
好像是 通过 分级查询 ，一级一级 查询。
比如身份证 单个查询 地区，可以分为多个表。 每个表，可能代表一个省。
省下面又分为 市， 区。这样一层一层，不需要全省都一起查，效率就高了

---

白下区13875629443： 最优二叉查找树和普通二叉查找树有什么区别? - ？
壤俩快力： 最优,就是查找效率最快. 好像是 通过 分级查询 ,一级一级 查询. 比如身份证 单个查询 地区,可以分为多个表. 每个表,可能代表一个省. 省下面又分为 市, 区.这样一层一层,不需要全省都一起查,效率就高了

白下区13875629443： 最佳二叉搜索树是什么?与二叉搜索树有什么区别? - ？
壤俩快力： 二叉查找树与二叉排序树区别 就平均时间性能而言,二叉排序树上的查找和二分查找差不多.就维护表的有序性而言,二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作,且其平均的执行时间均为O(lgn),因此更有效.二分查找所涉及的有序表是一个向量,若有插入和删除结点的操作,则维护表的有序性所花的代价是O(n).当有序表是静态查找表时,宜用向量作为其存储结构,而采用二分查找实现其查找操作;若有序表里动态查找表,则应选择二叉排序树作为其存储结构.

白下区13875629443： 什么是最佳二叉树 - ？
壤俩快力： 最佳二叉树就是,就是最佳二叉查找树,即平均查找长度最短的二叉查找树.它的结点构成上的特点是:除了最下一层可以不满外,其他各层都是充满了的.

白下区13875629443： 二叉判定树和二叉排序树有什么区别? - ？
壤俩快力： 二叉判定树神判大是用来分析某个算法而设计的二叉树,如:可以用来分析折半查找的过程,分析几个游竖数字的比较过程等;而二叉排序树是用来对一组关冲物键字进行排序的方法.

白下区13875629443： 树和二叉树的基本知识? - ？
壤俩快力： 二叉树在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆.二叉树的每个结点至多只有二棵子树(不存在度大于2的结...

白下区13875629443： 最优二叉搜索树的最优子结构是什么?子结构的递归过程是如何的 - ？
壤俩快力： 一道动态规划问题其实就是一个递推问题,假设当前决策结果是f[n],则最优子结构就是要让f[n-k]最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

白下区13875629443： 什么是二叉树?二叉树拿来干什么? - ？
壤俩快力： 1、二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3.有根二叉树还要满足根结点的度不大于2.有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点.然而,没有足够的信息来区分左结点...

白下区13875629443： 计算机c语言中 什么是二叉树 - ？
壤俩快力： 在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆或是二叉排序树.二叉树的每个结点至多只有二棵子树(不存在度大...

白下区13875629443： 平衡二叉树为什么叫AVL? - ？
壤俩快力： 平衡二叉树(Balanced Binary Tree) 是二叉搜索树(又名二叉查找树排序二叉树)的一种.在二叉搜索树中,搜索、插入、删除的复杂度都和书的高度相关,因此树高是制约二叉搜索树时间效率的最大瓶颈.理论上,任意高度为h二叉树最多...