查找兩個二叉搜索樹的常見元素的最佳方法

我有兩個BST由具有唯一ID的元素組成。我想找到這些BST的共同元素。查找兩個二叉搜索樹的常見元素的最佳方法

最簡單的方法是逐個獲取第一個BST的元素，並根據第二個BST檢查它們。但因爲我必須重複這個比較無數次，我正在尋找最快的算法。

2016-12-02 Saeed

說你的兩棵樹分別米和ñ，是規模。您提出的解決方案在時間Θ（n log（m））（或其他方式）工作。你實際上可以及時做到這一點Θ（m + n）。

讓我們從一個相關的問題開始。假設您有兩個清單，每個清單分別排序，大小分別爲m和n。您可以很容易地找到Θ（m + n）中的常見元素的數量。只需放置兩個「指針」，每個列表一個。通過比較這兩個項目，您可以計算出是否增加第一個指針，第二個或兩者（最後一種情況是在找到相同元素時）。（編輯 - 你可以在答案看到這this question）

在次一BST的遍歷概念一樣有序鏈表的遍歷，所以你可以在這裏做同樣的。

來源

2016-12-02 10:56:45

有趣的是，實際上它對我有很大的幫助。謝謝。然而，我正在尋找的想法就像BST中的[Bloom filter]（https://en.wikipedia.org/wiki/Bloom_filter）。最後，我認爲用簡單的排序數組替換所有的AVL樹並使用你提到的算法會更好。因爲我實現我的BST和順序遍歷的方式使我很難使用這種算法。 – Saeed

您可以執行一個BST的遍歷（pre，in或after order），並將這些節點的值存儲在一個散列表中。然後遍歷其他樹，併爲每個遇到的節點增加哈希表中的相應值。散列表中值大於1的任何值都是與二元搜索樹相同的值。

來源

2017-05-03 22:15:37

查找兩個二叉搜索樹的常見元素的最佳方法

回答

相關問題