二叉搜索树查找，插入等算法分析及ASL的推导

    小编在上一篇简书里分享了二叉搜索树的算法实现，但没有讨论下其各个算法的时间复杂度，今天小编就上次的代码来讨论下算法的时间复杂度。

    我们来看看之前二叉搜索树的查找算法【小编在原先的算法中我们添加一个全局变量count来记录程序的总执行步数】

查找算法

    我们知道，对于一个有n个节点的二叉树，如果它是不平衡的，那么它的最大深度，也就是高度为n，如下图所示：

只有左子树的二叉搜索树

    这个时候，假如我们要查找该二叉树的叶子节点，也就是上图中的节点值为1这个叶子。因为该二叉搜索树只有左子树，节点数为多少深度就为多少，高度就为多少。在这里，其高度为8。

    那么用上面的递归算法去差找这种只有左子树的二叉搜索树，可以发现前两个if语句执行了8次，后面判断if (x< root->_data)的条件语句执行了7次，return _find(root->_left, x)语句也执行了7次，最后一次找到叶子时还要执行一次return root语句，程序总执行步再加1，故总程序步数为2*8+2*7+1=31=4*8-1。同理可以推导出要是深度为n【高度为h=n】，程序执行总步数为4*n-1，故时间复杂度为O(n)。这个O(n)就是二叉搜索树的最差情况。

    对于一棵平衡的二叉搜索树，如下图，我们可以来算下它的高度。

平衡二叉树1

    假设有一颗二叉排序树,总结点数是n, 高度是h, 根结点的高度是1,

    假设也是满二叉树, n与h的关系, 有公式: n = (2^h) - 1

    也就是: h =；

    因此如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为。

    对于一棵轴对称的二叉搜索树，每次比较都能确保减小一半范围。如下图:

平衡二叉树2

    如果我们在该二叉搜素树中查找键值为2的节点，那么我们查找该节点需要的程序执行总步数为4*h-1【h为该节点所处高度】，我们已经算出h=，因此在这里查找键值为2的节点时，其所处高度为h==3，程序执行总步数为4*3-1=11步。

    因此对于一棵平衡二叉搜索树来讲，当其查找节点高度最大，也就是为时，程序的总执行步数最多，为4*-1，时间复杂度就是O()【书本里常记为O(log n)，对于平衡二叉树而言这是最差的情况】。因此对于一棵平衡二叉搜索树来说，它一定能在O()内完成查找。

    其实该查找算法属于分治策略的一种运用，但由于还没有涉及到分治策略，还没提及求解时间复杂度的方法，这里我们就用暂且用程序步去分析，或许不能很好的反映该算法特征，但目前我们可以使用这种方法来分析后续再来改进。

   对于二叉搜索树的插入，删除等算法也是如此，因为在进行插入操作前，有一个查找的过程，就是查找适合该键值插入的节点位置。后面的插入操作其实就是简单的指针指向等的问题，程序执行步骤为常数级别的，故可得到其最差情况下的时间复杂度为O(n)。删除节点也要查找到对应键值的节点。因此，二叉搜索树的查找，插入等性能在O()到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉搜索树。

    接下来，我们来推导二叉搜索树的平均查找长度ASL（Average Search Length），其计算方法就是：第一层元素个数 *1 + 第二层元素个数 *2 + 第三层元素个数 *3+……+第n层元素个数 *n 。：

    对于高度为2,总结点数是3的二叉排序树（满二叉树）,查找成功的平均查找长度为:

满二叉树1

    ASL = (1*1 + 2*2) / 3

    【第一层1个节点，其高度为1；第二层两个节点，每个节点高度为2，总高度为1*1+2*2=5，平均查找长度为5/3】

满二叉树2

    对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:

    ASL = (1*1 + 2*2 + 3*4) / 7

    【第一层1个节点，其高度为1；第二层两个节点，每个节点高度为2，第三层4个节点，每个节点高度为3，总高度为1*1+2*2+3*4=17，平均查找长度为17/7】

    对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:

推导过程

    这就是小编的一点知识总结，有错请指正。