algorithm - 在二叉搜索树中插入一个新值

Question

使用算法 Tree-Insert(T, v)插入一个新值 v进入二叉搜索树 T ，以下算法通过将数组给定部分中的每个值重复插入树中来生成二叉搜索树:

<b>Tree-Grow(A, first, last, T)</b><br/>
1 for i ← first to last<br/>
2 do Tree-Insert(T, A[i])<br/>


1. 若树初始为空，且数组部分(即last-first+1)的长度为n，则上述算法的最佳情况和最坏情况渐近运行时间分别是多少，分别？

2. 当 n = 7 时，给出算法的最佳情况实例(作为包含数字 1 到 7 的数组，按特定顺序)和最坏情况实例(以相同的形式)。

3. 如果数组已排序并且所有值都不同，请找到一种修改 Tree-Grow 的方法，以便它始终构建最短的树。

4. 修改算法的最佳情况和最坏情况渐近运行时间分别是多少？

Answer 1

请用homework 标记标记家庭作业问题。为了在期末考试中取得好成绩，我建议你实际学习这些东西，但我不是来评判你的。

1) 从头到尾迭代需要O(n)。插入二叉树需要 O(lg n)，因此您展示的算法在最佳情况下需要 O(n lg n)。

插入二叉树的最坏情况是树很长，但不是很茂密；类似于链表。在那种情况下，插入需要 O(n)，因此在最坏的情况下需要 O(n^2)。

2) 最好的情况:[4, 2, 6, 1, 3, 5, 7]，最坏的情况:[1, 2, 3, 4, 5, 6, 7]

3) 使用 n/2 索引作为根，然后对数组的左侧和右侧递归执行此操作。

4) O(n lg n) 在最好和最坏的情况下。

希望对您有所帮助。