我正在准备考试,我偶然发现了以下问题:
如果按以下顺序添加数据,则绘制二叉搜索树:
10,9,8,7,6,5,4,3
为什么生成的树不适合高效搜索?
我的答案:
在创建 BST 时,我会认为我们从值 10 作为根节点开始,然后在第一级添加 9 作为左子树值。然后 8 到 9 的左子树,以此类推。我不知道为什么这会导致搜索效率低下。有任何想法吗?
我正在准备考试,我偶然发现了以下问题:
如果按以下顺序添加数据,则绘制二叉搜索树:
10,9,8,7,6,5,4,3
为什么生成的树不适合高效搜索?
我的答案:
在创建 BST 时,我会认为我们从值 10 作为根节点开始,然后在第一级添加 9 作为左子树值。然后 8 到 9 的左子树,以此类推。我不知道为什么这会导致搜索效率低下。有任何想法吗?
由于这些值是按降序排列的,因此它们会在每个级别添加到左侧,实际上给您留下了一个链表,它需要 O(N) 进行搜索,而不是 BST 的首选 O(logN)。
绘画:
10
/
9
/
8
/
7
/
6
/
5
/
4
/
3
这将创建一个链表,因为它只是一系列节点;这是一棵严重不平衡的树。
你应该查查红黑树。它们具有相同的时间复杂度,但它会不断地围绕节点移动,因此它总是形成三角形。这将使树保持平衡。
这是低效的,因为该节点将始终添加到前一个节点的左子树中。对列表中的每个节点进行搜索检查,直到找到结果,即使答案总是在左侧,因此实际上比简单地通过循环搜索列表需要更多的计算。