二叉樹複雜度

Question

我想知道二叉搜索樹的一些複雜性。

我找不到完整的信息。我想知道在二叉搜索樹

1. ，增加了對以下操作的複雜性/插入元素
2. 刪除元素
3. 找到一個元素（因爲我知道這個人是O(log(n))）

Answer 1

插入，刪除，並在二叉搜索樹搜索是：

• O(N)在最壞的情況下;
• O(log(N))在一般情況下。

Answer 2

如果你有平衡二叉樹，所有三個複雜性將是O(log(N))。如果你不平衡樹，它可能是O(N)。

Answer 3

搜索有效。但是，不平衡的結構（通常是這種情況）會導致O（N）用於搜索/插入/刪除操作。這就是爲什麼二進制堆或其他類型的平衡樹優先於O（log n）。 。