avl樹遍歷

-1

設S是一個整數的動態集合。令n = | S |。將S上的數據結構描述爲支持S上的以下操作，並具有所需的性能保證：avl樹遍歷

•在O（log n）時間內向S插入一個新元素。

•從O（log n）時間的S中刪除元素。

•對於滿足1≤k≤n的任意k，報告O（k）時間中S的k個最小元素。

您的結構必須始終消耗O（n）空間。

我可以簡單地建立一個AVL樹，然後按順序遍歷打印前3個元素？

來源

2016-11-01 101ldaniels

'我可以簡單地構建一個AVL樹並[使用按順序遍歷打印前3個元素？'這需要多少時間來處理一百萬個元素？一百萬？一個[Googolplex]（https://en.wikipedia.org/wiki/Googolplex）？ – greybeard

標準答案是一個平衡的線程二叉搜索樹。這是一個BBST，它在葉節點中使用否則爲空的指針。這些按照排序順序將節點連接到鏈接列表的某個附近。結果是，只有每次插入或刪除O（log n）附加時間（每個節點觸摸的持續時間），您才能維護指針。您可以通過從列表頭開始遍歷O（k）時間列出前k個節點。 http：// adtinfo有一個非常漂亮的實現。org/ – Gene

您的建議解決方案在O（k）時間內不起作用。開始按順序遍歷需要O（log n）時間。即使你在找到一個元素後停下來，你仍然需要先到達最左邊的葉子。

我能想到的兩種解決方案：

使用skip-list，它有O（log n）的插入和刪除以及底層列表進行排序。但是，插入和刪除的時間複雜度是平均的，而不是最壞的情況。
使用修改後的AVL-tree，保留專用指針指向最左邊的節點並在插入和刪除時更新它。此外，節點必須具有指向其父節點的指針，以便您可以從最左邊的節點開始按順序遍歷。或使用threaded tree。

來源

2016-11-01 20:58:00

當內存稀少時，可以使用父代引用的替代方法是[線程樹]（https://en.wikipedia.org/wiki/Threaded_binary_tree） - 添加對左側和/或最右側_node_的引用（不是葉）如所須。 – greybeard

@greybeard謝謝你，編輯你的評論 –

會有這些額外的指針違反空間約束？ – 101ldaniels

使用優先級隊列，它使用O（n）空間。插入和刪除都是O（log n）操作。 Find-min是O（1），接着是remove-min，它是O（k），您可以重複三次。

來源

2016-11-02 00:41:09 user448810

remove min是O（log n ） –

你是對的。我的錯。我會在這裏留下這個答案，以提醒我自己不要愚蠢。 – user448810

-1

IVE決定來存儲和更新在根最左節點指針，和指向前導和後繼在每個節點

從而在每次插入它插入和O（logn）時間收費O（logn）時間+ O （logn）來查找前導和後繼，O（logn）+ O（logn）+ O（logn）= O（logn）

這些指針還允許插入O（1）後更新受影響的節點指針）分別前往前輩或後繼者，並更新那裏的指針也在O（1）

具有指向最左邊節點的指針意味着travell存在O（1），然後遍歷後繼並在O（k）時間內打印前k個節點。

來源

2016-11-02 04:30:34 101ldaniels

回答

相關問題