以隨機順序打印平衡BST的最佳方法？

對不起，如果這看起來像一個隨機問題，但我有一個超過100,000個名稱/值對的數據庫（稱它們爲高分，如果您願意）存儲在AVL風格的平衡二叉搜索樹中。大多數時候，爲了列出分數，我打印了BST，並進行了有序遍歷或逆序遍歷，但是今天我發現需要以隨機（或僞隨機）順序打印樹。有沒有一些可接受的或最佳的方式來做到這一點：一次訪問每個節點，但以不可預知的方式？以隨機順序打印平衡BST的最佳方法？

PS - 我想到了廣度優先遍歷，但是因爲它總是以相同的方式發生，所以它並不是真正的隨機性。必須有一些聰明的方式，或一些理想的面試答案，因爲這似乎是一個普遍的問題;除了僅僅將節點標記爲已訪問或創建外部跟蹤數據結構外，我還沒有想出任何非常聰明的東西。

來源

2012-05-17 Cindeselia

我不知道爲什麼這個答案不僅僅是將BST，線性化，然後打印出來。我想你的擔心是線性化這樣的數據結構可能需要很多內存。如果是這種情況，你可以隨時挑選出件樹，將它們線性化，然後跳轉。隨機遍歷指針並希望能夠順利運行的排序是一個糟糕的主意：您總是會因爲尋找最後一個節點而陷入困境。如果你有一個完整的二叉樹，你可以隨時拿出數字並從根開始（實質上，你可以從樹的完整屬性中免費獲得線性化）。

編輯：

我比我或許應該少明智的，因爲最近我發現這篇文章，雖然它是基於一個功能的實現，它可能對你有用的。我沒有看到這一切，所以我不知道它是如何工作，通過迭代的一切，但如果你只是想獲得一個節點了，那麼你可以使用這個..

http://okmij.org/ftp/Algorithms.html#random-tree-node

來源

2012-05-17 03:38:50

謝謝爲了您的迴應。對，我想我對線性化算法還沒有足夠的認識。你是否只是生成一堆隨機的左遍歷和右遍歷，直到你唯一地覆蓋它們？我知道如何從1：size生成一個隨機的索引排序，但是看起來像這樣我就可以將單個索引轉換爲樹遍歷了。 – Cindeselia

線性化我的意思是使用標準遍歷遍歷樹，將它們粘貼在列表中，然後隨機化列表。即使以懶惰的方式，如果通過隨機指針追蹤的變體實現，您可以使用任何算法執行類似等效的任何操作，您可以獲得大致相當於在所訪問的搜索空間範圍內傳遞Thunk的內容。 –

我明白...但是，有點改變我的問題，因爲標準遍歷是O（n），我不知道我們是否可以有一些索引算法，允許我們隨機訪問O（1）。當然，按照隨機順序打印所有元素仍然需要完整的線性化，但是爲每個節點預分配索引1尺寸的額外步驟可能需要更少的操作來完成一定數量的訪問。對不起，我意識到這確實改變了這個問題。這個評論只適用於我們想要n Cindeselia

以隨機順序打印平衡BST的最佳方法？

回答

相關問題