鏈表
鏈表的插入時間復雜度在實際操作中是O(1)，但是需要O(n)的時間才能遍歷到合適的位置。大多數在線資源將鏈表的平均插入時間列為 O(1)。
BST
二叉搜索樹的插入需要遍歷節點，花費 O(log n) 時間。
問題
Am I mistaken to believe that insertion in a BST also takes O(1) time for the actual operation?
類似于鏈表的節點，在 BST 中插入節點只會將當前節點的指標指向插入節點，而插入節點將指向當前節點的子節點。
If my thinking is correct, why do most online resources list the average insert time for a BST to be O(log n), as opposed to O(1) like for a linked list?
似乎對于鏈表，列出了實際插入時間，但對于 BST，列出了遍歷時間。
uj5u.com熱心網友回復：
二叉搜索樹是有序的，并且它通常是平衡的（以避免O(n)最壞情況下的搜索時間），這意味著當您插入一個值時，必須進行一定量的改組以平衡樹。這種重新平衡需要平均O(log n)操作，而鏈表只需要在您找到在節點之間插入專案的位置后更新固定數量的指標。
uj5u.com熱心網友回復：
要插入鏈表，您只需要維護鏈表的結束節點（假設您在最后插入）。
要插入二叉搜索樹 (BST)，并在插入后維護BST，您無法做到這一點O(1)- 因為樹可能會重新平衡。這個操作不像插入鏈表那么簡單。
在此處查看一些示例。
uj5u.com熱心網友回復：
鏈表的插入時間實際上取決于您插入的位置和鏈表的型別。
例如，考慮以下情況：
- 您正在使用單個鏈表，并且要在末尾/中間插入，您將有 O(n) 的運行時間來遍歷串列直到結束節點或中間節點。
- 您正在使用雙鏈表（兩個指標第一個指標指向頭元素，第二個指標指向最后一個元素）并且您將在最后插入，這次您仍然需要 O(n) 時間復雜度使用第一個或第二個指標遍歷到串列的中間。
- 您正在使用單鏈表并且您將在串列的第一個位置插入，這次您的復雜度為 O(1)，因為您根本不需要遍歷任何節點。雙鏈表和插入位置在串列末尾也是如此。
所以你可以看到在最壞的情況下，鏈表將采用 O(n) 而不是 O(1)。
現在，在 BST 的情況下，如果您的 BST 是平衡且不偏斜的，您可以想出 O(log n) 時間。如果您的 TREE 是傾斜的（其中每個元素都大于 prev 元素），這次您需要遍歷所有節點以找到插入位置。例如，考慮您的樹是1->2->4->6并且您要插入節點9，因此您需要訪問所有節點以找到插入位置。
1
\
2
\
4
\
6 (last position after which new node going to insert)
\
9 (new insertion position for the new node)
因此，您可以看到您需要訪問所有節點才能找到合適的位置，如果您有 n 個節點，則運行時間復雜度為 O(n 1) => O(n)。
但是如果你的 BST 是平衡的而不是傾斜的，情況就會發生巨大的變化，因為每一步你都可以消除不符合條件的節點。
PS：我的意思是not comes under the condition你可以把這個當作作業！
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313536.html
上一篇：清理字串僅包含字母字符的問題