java - 插入二叉搜索树的运行时间是 n^2？

Question

书上说插入二叉搜索树的最差运行时间是n^2

我真的不明白。

我的意思是如果你有 1, 2, 3, 4, 5, 6, 7, 8, 9

哪个是最坏情况，最坏情况运行时间不是O(n)吗？

(如果值 < node.data，向左，如果 > node.data 向右)

谁能解释一下？我真的很感激!

---

我想我现在得到了答案!因为你需要回去看看是否有新号码从一开始就变大或变小。

但我现在有另一个问题，构建 AVL 树的最坏情况运行时间是多少？

书上说构建和排序二叉搜索树是n(log n)

AVL树的最差深度是log n

它从来没有说整个 AVL 树的插入时间是多少。

有人知道吗？

Answer 1

这不是 O(n)，因为在每次插入时，您都需要遍历整个树以找到放置新节点的合适位置。

例如，首先您在节点的头部放置一个 1。然后，要放置 2，您需要查看头部的 1 并决定将 2 添加到头部的右侧。然后，添加3的时候，需要再看那个1，决定往右走，再看2，把3放在2的右节点上。

所以基本上，每个最坏情况下的插入都是 O(k)(其中 k 是树中已有的元素数)。要构建树，您需要进行 n 次插入，因此整个操作需要 1+2+3+4+5+6...+n 操作，即 O(n^2/2) --> O(n^2).