二叉搜索樹問題

Question

我正在考慮實現二叉搜索樹。我已經實現了一些非常基本的操作，例如搜索，插入，刪除。

請分享您的經驗，我可以在二叉搜索樹上執行所有其他操作，以及在任何給定情況下每次都需要執行一些實時操作（基本）..我希望我的問題很明確..

謝謝。

Answer 1

至少，二叉搜索樹應該有插入，刪除和搜索操作。任何其他操作將取決於你打算如何處理你的樹，儘管一些通用的建議是：返回給定節點的父節點，查找給定節點的左側和右側子節點，返回根節點，預先排序，中間排序和後序遍歷，以及廣度優先遍歷。

Answer 2

嘗試遍歷操作（例如，按順序將樹中的元素作爲List返回），並確保在插入/刪除元素時樹保持平衡。

Answer 3

如果這是功課，祝你好運！

如果這是好奇，玩得開心！

如果你想要在生產代碼中實現這一點，甚至不知道基本操作，不要這樣做！

http://www.boost.org/doc/libs/1_38_0/boost/graph/detail/array_binary_tree.hpp

Answer 4

如果你真的只是想的東西的清單可能有用或有趣的實現...

1. 反向樹一切的秩序。這是O（N）我想？
2. Subtree，x和y之間的元素作爲二叉搜索樹本身 - 應該是O（log N）我認爲？
3. 最小，最大？是的，微不足道，但我沒有想法！

Answer 5

你可能想看看返回樹的不同方式：

• 深度優先（打算一路下跌的一個分支和備份，重複）
• 在順序（在樹的周圍）
• 級別順序（每個級別如圖所示）
• 作爲平面數組返回。

如果您感覺特別冒險，可以採用數組並將其作爲樹導入。有一個特定的格式，這就像（1（2（3）），（5） - 這個例子是不平衡的，但你得到的想法，它在維基百科上

Answer 6

你可能也想執行旋轉操作A rotation在不改變元素順序的情況下更改結構，通常用於平衡樹（以確保葉子全部接近相同深度），也可用於將根改爲一個給定的元素，如果你知道它會更頻繁地出現在搜索中。

我的ASCII藝術不是很大，但是旋轉可以把這個樹：

 f 
    d  g 
    b e   
a c 

成樹：

 d 
    b  f 
    a c e g 

第二棵樹被平衡將使搜索f和g慢，並且在e保持不變的情況下更快地搜索d，a，b，c。

Answer 7

我想我看過某處「地圖」操作。當您用單調函數更改樹的所有元素時。即（f（x + dx）> = f（x））或始終下降（f（x + dx）< = f（x））的函數。在一種情況下，您需要將該函數應用於其他節點，您還需要鏡像樹（交換「左」和「右」節點），因爲結果值的順序將被顛倒。