創建二叉樹的時間複雜性

我試圖從一個源創建一棵樹，該樹提供了：要添加到樹中的2個節點以及應添加這2個新聞節點的節點。爲了找到這個節點在樹中的位置，我使用了一個需要O（n）的inorder遍歷。所以如果樹中有n個節點需要添加，整棵樹的創建將會是O（n^2）。我的約束是它應該只用O（n）來創建樹。創建二叉樹的時間複雜性

來源

2012-03-11 Dan

我真的無法看到如何將n個節點一個接一個地添加到二叉樹中，可以在小於O（n log n）的情況下實現。您的描述中似乎缺少某些內容。另外我認爲這是作業，所以你應該添加正確的標籤。 – Voo 2012-03-11 22:17:51

爲什麼你需要一個inorder遍歷來找到樹中的正確位置？節點的排列方式應使您能夠在O（log（n））平均時間內找到給定的節點。如果你不能有這樣的安排，也許二叉樹不適合你的數據。 – Gigatron 2012-03-11 22:26:01

您可以在HashMap [1]中保留對樹的每個節點的引用，以獲得對每個節點的O(1)訪問權限，而不是樹木典型的O(log(n))。這將使得在O(n)時間內構建樹成爲可能，因爲HashMap允許您直接跳到節點，而不是從樹的根節點遍歷那裏。

[1]關鍵將是源用於唯一標識節點（我假設它是一個整數或字符串）。該值將是對樹中節點的引用。請注意，樹實現必須公開所有節點，因此您可能需要自己編寫樹或找到合適的庫（JDK的樹（如TreeMap）保持其內部結構爲私有，因此它們不會剪切它）。

來源

2012-03-11 22:23:33

雖然這會解決這個問題，但它還會提出另一個問題：爲什麼不把數據存儲在HashMap中，而是完全放棄樹。 – twain249 2012-03-11 22:35:20

twain249：的確如此。如果這是作業，我懷疑是否有任何真正的理由使用樹，除了作業是這樣說的。 :)我可以想到的一個現實的（但很少見的）原因是系統需要在重新啓動後從文件快速恢復其狀態（因此O（n）啓動時間），並且在正常操作期間系統具有嚴格的最壞情況延遲要求（因此散列圖的攤銷O（1）是不可接受的，但是樹的可預測的O（log（n））是需要的）。 – 2012-03-11 22:46:39

給出完美散列函數**或「O（1）平均值」的單詞** O（1）攤銷時間應該更主要地出現在這個答案中:-) – 2015-04-11 07:46:16

仰視在二進制樹中的節點是O(log(n))因爲樹具有log(n)水平（每級保持兩倍它上面的電平）。因此，要創建/插入n元素到二叉樹中，它的格式爲O(nlog(n))。

來源

2012-03-11 22:19:33 twain249

二元搜索樹的時間複雜度爲O（nlogn），當元素未被排序和排序需要O（n^2）。這是因爲要在BST中的排序列表中插入一個元素O（n）時間對於n個元素O（n^2）以及對於平衡或幾乎平衡的二叉搜索樹而言是這樣的，對於插入的最大時間是logn，因此對於n元素是nlogn

來源

2015-09-18 09:44:49 Guest

創建二叉樹的時間複雜性

回答

相關問題