二叉查找树最好情况下复杂度_遍历二叉树的时间复杂度

力扣心得 96. 不同的二叉搜索树 Python3 　　有多少种不同的 xxx 的方式，是一种比较典型的“计数型动态规划题”，我们的老朋友。结合搜索二叉树的特性找到递推公式很关键。这一题用动态规划解太妙了。后文我们结合王争老师的数据结构教程内容复习一下二叉树的基础知识。　　一、题干：有多少种不同的二叉搜索树　　

题干力扣 96 　　力扣题解：动态规划 × 二叉树　　力扣　　给定一个有序序列，为了构建出一棵二叉搜索树，我们可以遍历每个数字，将该数字作为树根，将小于它的子序列序列作为左子树，将大于它的子序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。　　上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。　　由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。　　

本质是个二叉树问题　　代码　　这里要格外注意边界条件。提醒自己，这里的动态规划数组的索引，指的是子问题，即用 x 个数字可以构成多少个子序列。建议画图举例，再来写边界条件。　　总结　　有多少种不同的 xxx 方式，是一种比较典型的计数型动态规划题，结合搜索二叉树的特性找到递推公式很关键。下面我们结合王争老师的数据结构教程内容复习一下二叉树的基础知识。　　二、二叉查找树基础知识　　1. 什么是二叉查找树　　二叉查找树，又名二叉搜索树，是一种特殊的二叉树。二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。　　二叉查找树是为了实现快速查找而生的。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树举例图源：王争老师的数据结构课　　2. 二叉（查找树）的优势？　　Q：可散列表也是支持这些操作，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。而二叉查找树在比较平衡的情况下操作的时间复杂度才是 O(logn)。有如此高效的散列表，为什么还需要二叉树？　　A：第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序，而快排的时间复杂度也为 O(nlogn)。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。　　第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。　　第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。　　第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。　　最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。　　综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。　　3. 二叉查找树的插入、查找和删除操作　　如何在二叉查找树中查找一个节点呢？　　首先，我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

二叉查找树查找图源：王争老师的数据结构课　　二叉查找树的插入操作　　新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

二叉查找树进行插入操作图源：王争老师的数据结构课　　二叉查找树的删除操作　　二叉查找树的查找、插入操作都比较简单易懂，但是它的删除操作就比较复杂了。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理：第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

二叉查找树的删除操作图源：王争老师的数据结构课　　不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。

二叉查找树最好情况下复杂度_遍历二叉树的时间复杂度

相关推荐