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

二叉查找树（BST，Binary Search Tree） ，又名二叉搜索树或二叉检索树，是一颗满足如下条件的树：

成都创新互联是专业的仓山网站建设公司，仓山接单;提供网站设计制作、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行仓山网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

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 ，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 = k1 , k2 , . . . , kn ，概率序列 P = p1 , p2 , . . . , pn

输出：两个二维数组，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和Root中

下面分析这个算法的时间复杂度：

由于除了计算出我们最后需要得到的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[end-1] to Root[start+1]

对于每个root，根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：

左右子树的最优子树代价之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）

在内层循环中找到代价最小的price和root分别记录在Price和Root中

在分析该算法的时间复杂度时应注意，考察的子树是与考察的内层循环中root数量一一对应的，而当start递进时，前一个root的终点正好等于后一个root的起点（算法中的红色部分），也就是说对于固定的size来说，考察的root的范围加起来应当首位相接 而且至多刚好覆盖 所有节点，因此对于每个size，最多只考察2n个root（这里缩放了一下），因此总共最多考察了2n · n = 2n2 个子树；另一方面，Root数组中每一个值对应得到的一个最优二叉查找树，也即至少需要考察n2 个子树。因此根据定义得到 T(n) = O(n2 )

在二叉搜索树中查找"比参数key大的最小值”

算法思路:中序遍历二叉树，得到的是一个有序序列啊，在遍历过程中就可以第一次比比参数key大的值就是符合要求的！也有可能key就是最大的。

另一种思路就是递归：就是和根比较，key比根大，说要有比参数key大的最小值”一定在右子树上，否则就在左子树上，按这种思想也可以找到!

二叉排序树

二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。

实例

当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的左孩子是不是空，如果是空则将要插入的值作为当前节点的左孩子，不是空则将当前节点的左孩子作为当前节点继续查找；当要插入的值比当前节点的值大时，判断当前节点的右孩子是不是空，如果是空则将要插入的值作为当前节点的右孩子，不是空则把当前节点的右孩子作为当前节点继续查找

节点定义

递归实现

非递归实现

使用中序遍历，遍历出来的结构刚好是一个升序排列的数列

递归写法

非递归写法

搜索二叉排序树的时候，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值和搜索的值相等，则搜索结束，返回成功；如果当前节点的值小于搜索值，则判断当前节点的左孩子是不是空，如果是空，则搜索的值不在树中，搜索结束返回失败，如果不为空，则将当前节点的左孩子作为当前节点，继续搜索；如果当前节点的值大于搜索值，则判断当前节点的右子树是不是空，如果是空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则将当前节点的右孩子作为当前节点，继续搜索。

二叉排序树的删除分为如下三种基本的情况

直接删除节点即可

将要删除的节点的孩子节点替换当前节点即可

在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点，同时将这个最小的节点删除掉（也可以从左子树中找一个最大的节点）

具体情况

算法实现：

二叉排序树的查找时间与二叉树的高度有关，高度越高需要的查找时间就越多。

二叉排序树的高度有两种极端的情况，一种是完全二叉树，一种是每层只有一个节点的情况，变成了一个链表。

当是完全二叉树的时候：这种情况下的时间复杂为O(log2N)

当每一层只有一个节点时，也就是链表的时候：这种情况下的时间复杂度为O(n)

所以二叉排序树的搜索时间复杂度在：O(log2N) O(n)之间。它的插入，删除复杂度也在O(log2N) O(n)之间

二叉树 的 常用公式 谁能和新手 说说啊！

(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2^h-1个结点(h=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为int（log2n）+1；

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I1，则其父结点的编号为I/2；

如果2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；

如果2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

扩展资料：

类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：

1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；

2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3）左、右子树也分别为二叉排序树。

若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

结点的度：结点拥有的子树的数目。

叶子结点：度为0的结点。

分支结点：度不为0的结点。

树的度：树中结点的最大的度。

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。

树的高度：树中结点的最大层次。

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

参考资料：百度百科---二叉树

网站名称：go语言二叉搜树算法 go 二叉树遍历
新闻来源：http://azwzsj.com/article/hhsiji.html