2个元素的二叉树

计算科学 算法
2021-12-13 16:04:19

我想了解由 1,2 组成的 2 元素列表的二进制搜索。我画了一棵树,如下所示。这是正确的吗?

在此处输入图像描述

如果我想搜索元素 2,它将进行 2 次比较。如果我想搜索元素 22,它也会进行 2 次比较。但是根据公式 Θ(lg n),当 n=2 时,在最坏的情况下应该只进行一次比较。我无法将这两个事实联系起来。请帮我。

1个回答

在您的示例中,二叉树是正确的,因为右节点大于父节点,但它不是最优的,因为搜索树不会平衡。根节点为 1 的事实意味着对于第一次比较,搜索算法将向右导航。

发生的事情是您示例中的二叉搜索树充当时间复杂度为 Θ(n) 的链表。

这可以在此处的“搜索”中看到:https ://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html