一道经典的数据结构（面试）题目

第2问是什么意思？
3 也可以是
        15
    4        23
       11         25
         12           31
该树平衡，属完全二叉树
平衡不一定是完全二叉树。
查找，最好就是找15 一次解决。 最坏：纯属结构n/2   平均log2(n)
插入和删除应该和查找一样的。只不过在删除的时候需要变换树的结构。
我记得应该有三种变换方法都可以。

4，对二叉树的复杂性的分析（请用0()的公式）：（这里只需要写答案，但如果能用数学推论的方式，写出如何从二叉树倒O（）结论的步骤加20分）

O（lg n）

4a.在二叉树里寻找一个新号码复杂性（经过多少次计算），请写出最好的，最坏的和平均值。
4b.在二叉树里插入一个新号码的复杂性，请写出最好的，最坏的和平均值。
4c.在二叉树里抽掉一个号码的复杂性，请写出最好的，最坏和平均值。

三种操作都是一样的
最好 O(1)
最坏 O(n)
平均 O(lg n)


5，请列出你学过的和经常用的数据结构的名称：

2.
   a. 15->9->4->12->23->25->31
   b. 15->23->25->31->9->12->4  中的 11 排在哪个位子?????

看来我已经把这些东西还给书本了

悲剧 只看懂前3题

我晕啊...第一遍我好像完全看不懂在说什么诶！

数据结构。。没学过啊。。 看来需要恶补下了

(1)插入后：
                       15

                 9           23
                  
             4       11          25
                    
                        12           31
(2).
a.从小到大
路线为：15->9->4->9->11->9->15->23->31
解释一下：
搜索最小的路线，从root开始，root为15， 根据二叉树规则可知，最小的节点在左子树中，这样递归，一直到4，然后返回，节点4没有左子树，于是返回到9，大家知道这时候9的右子树中，是大于9而小于15的集合，所以路线进入9的右子树，11节点没有子树，所以返回到9，这时4，11节点都遍历完毕，返回到15节点，开始遍历15节点的右子树，所以得到上边的结果。
b.从大到小
路线为：15->23->31->23->15->9->11->9->4
理论同上
(3).去掉9节点后：
                       15

                  11        23
                  
              4      12          25
                                  
                                     31
(4).渐进时间复杂度,找15需要比较1次，找11，22，需要比较2次，找4，12，25需要比较3次，找31需要比较4次
如果是搜索算饭复杂度分析,那么有：
f(7) = (1 + (2 + 2) + (3 + 3 + 3) + 4)/7 = 18/7 = O(18/7)
\.对于有n个元素的数组，如果每个元素被找到的概率相等，那么查找成功的平均比较次数为:
最好的情况，为该二叉树为完全二叉树：
f(n) = (2^0 + 2^1 + 2^2 + ... + 2^n)/n
最坏的情况，为该树为单叉树：
f(n) = (1 + 2 + 3 + ... + n)/n
平均时间复杂度为：O(nlog2n)
(5).线性表、树、图 基本上就三大类吧

唉？数据结构太差了。尤其是关于树。。

我记不清了。但是好似去一个节点的时候。似乎替换规则是有方法的。。。
会有不同的树么？