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

让我们看一下二进制搜索树的先前搜索算法[小编在原始算法中添加了全局变量计数，以记录程序的总执行步骤]

查找算法

我们知道对于具有n个节点的二叉树，如果它是不平衡的，则其最大深度，即其高度为n，如下图所示:

只有左子树的二叉搜索树

这时，如果要查找二叉树的叶节点，即上图中该节点的叶值是1. 由于二叉搜索树只有一个左子树，因此深度为节点与高度相同. 在这里，它的高度是8.

然后使用上面的递归算法找到只有左子树的二叉搜索树，您可以发现前两个if语句执行了8次，并且条件语句为if（x _ 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）. 计算方法为: 第一层中的元素数* 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，第三层上的四个节点的高度为3，总高度为1 * 1 + 2 * 2 + 3 * 4 = 17，平均搜索长度为17 / 7]

对于高度为h且汇总点为n的二进制排序树（完整的二进制树），成功搜索的平均搜索长度为:

推导过程

这是小编的知识摘要. 如果有错误，请纠正我.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-202045-1.html