algorithm - 要执行的最大比较次数以搜索根本不存在的节点

Question

对于这个二叉搜索树，搜索一个根本不存在的节点要执行的最大比较次数是多少。

标签： algorithmbinary-search-tree

Answer 1

使用二叉搜索树存储数据的优点是确定元素是否存在所需的最大比较次数仅取决于最大树高度。在上述情况下，最大树高为 5，因此最多需要 6 次比较。

我们通常希望二叉搜索树是完整的，因为这会降低树的高度，从而减少必要的比较次数。被选为根的节点决定了二叉搜索树最终的完整性，从而决定了结果树的高度。

二叉搜索树的美妙之处在于节点的隐式排序，即节点左侧的值必须更小，而右侧的值必须更大。在处理普通二叉树时，确定一个元素是否存在于树中所需的比较次数是由于缺乏排序不变量而在最坏情况下树中的节点数。