我剛剛完成了一次求職面試，並且我正在爲這個問題苦苦掙扎，在我看來這是一個很難回答15分鐘面試的問題。從整數流中創建一個平衡的二叉搜索樹
問題是： 編寫一個函數，給定一個整數流（無序），構建一個平衡搜索樹。 現在，你不能等待輸入結束（這是一個流），所以你需要在運行中平衡樹。
我的第一個答案是使用紅黑樹，這當然是工作，但我必須假設他們並不指望我在15分鐘內實施紅黑樹。
那麼，有沒有簡單的解決方案，我不知道這個問題？
感謝，
戴夫
AA Trees比紅黑樹更簡單了一點，但我無法實現一個從我的頭頂。
我認爲這是最好的答案。如果你要將平衡樹算法提交給內存，這是最簡單的一種。這是一個非常好的答案，因爲AA樹的刪除是最複雜的實現，並且問題似乎不需要刪除功能。 –
我個人認爲最好的辦法是去一個隨機二叉搜索樹，如treap。這並不能絕對保證樹會平衡，但很有可能樹會有一個很好的平衡因子。通過用一致的隨機數對樹的每個元素進行擴充，然後確保該樹是關於密鑰的二叉搜索樹，以及關於統一的隨機值的堆。插入到樹枝非常容易：
最後一步是唯一的難題，但如果您有一段時間在白板上工作，我相當確信您可以在面試中實現這一目標。
另一種可行的方法是使用splay tree。這是另一種可以實現的快速BST，假設您具有標準的BST插入功能和執行樹旋轉的能力。重要的是，在實踐中，張開樹是非常快的，並且已知它們（在一個常數因子內）至少與任何其他靜態二叉搜索樹一樣好。
根據「搜索樹」的含義，您還可以考慮將整數存儲在某些結構中，以優化查找整數。例如，您可以使用一個bitwise trie來存儲整數，這些整數支持與機器字中的位數成比例的查找。這可以很好地使用遞歸函數來查看位，並且不需要任何形式的旋轉。如果你需要在15分鐘內完成一個實現，並且如果面試官允許你偏離標準的二叉搜索樹，那麼這可能是一個很好的解決方案。
希望這會有所幫助！
嗯，首先，它確實有幫助:)但我仍然認爲在面試中這是一個很大的要求。這次採訪似乎是一個很好的解決方案，但我不認爲這是面試官的意思。這對BST問題來說是一個非常平常的解決方案，如果你在面試之前不熟悉它（比如我）而不是提出這個問題，這不是一個真實的選擇。至於斜張樹，它又如同提及紅黑樹（儘管它實現起來更簡單）。但是實施它仍然不是微不足道的，對於一個簡短的採訪來說，這似乎是一個很大的問題。 – Dave
我會第二次展開樹木，儘管它們在技術上並不「平衡」，但它們可能足以滿足面試的要求（例如，查看第k個元素或類似的東西）。 – Mikola
我認爲在15分鐘內寫一個樹木或一棵樹可能不太可行。按比特樹是一個很好的，但不知道面試官是否同意：P。 –
最簡單的平衡二叉搜索樹之一是BB（α）-tree。你選擇常數α，它表示樹能得到多少不平衡。在任何時候，#descendants(child) <= (1-α) × #descendants(node)必須持有。你把它當作普通的二叉搜索樹，但是當公式不再適用於某個節點時，你只需從頭開始重新構建該樹的那一部分，以便它完全平衡。
插入或刪除的分期時間複雜度仍然是O（log N），就像其他平衡二叉樹一樣。
你知道什麼關於整數（除了他們未分類的事實）嗎？您是否允許構建BST以迴應某人查看某個元素，或者您是否必須始終提供BST？你可以構建多個不同的BST，還是隻需構建一個？ – templatetypedef
好吧，也許你可以在相當自由的規則解釋下使用紅黑樹。由於15分鐘時間不是很長，如果你可以像使用STL容器和算法那樣做一些傻事，你可以創建一個std :: map，然後直接插入對象（但我必須承認這是基本上是作弊）。 – Mikola
問題是因爲它似乎沒有其他的輸入或使用假設。我只是想，也許有一個共同的算法，我只是沒有意識到這一點。顯然他們想讓我實現一棵平衡的樹，就像我所知道的那樣。祝你好運。 – Dave