訪問鏈接列表

Question

我的程序包含二進制搜索樹和單個鏈接列表。 其中每個操作都是對兩個數據結構完成的。 我有問題： 1）鏈接兩個數據結構，以使兩個數據結構點的當前點都是相同的元素。 2）排序節點 3）最後也是最困難的一個是在鏈表log（n）中獲得搜索性能，因爲它在bst中。我不能有更多的複雜性。 我使用其他數據結構的選項是none。 btw我使用java作爲編程語言。

Answer 1

1）鏈接兩個數據結構，使兩個數據結構點的當前點都是同一個元素。

您可以創建共享元素的樹和鏈接列表。我想這就是你的意思。

2）挑選節點

無法排序樹。樹的節點是自然排序的，如果您在不同的比較器中重新排序它們，則樹不再有效。

3）最後也是最困難的一個就是在鏈表log（n）中獲得搜索性能，因爲它在bst中。

您無法搜索O(logN)中的無序列表。這在數學上是不可能的。您可以搜索O(logN)中的有序數組（或數組列表），但這取決於能夠索引O(1)中的數組/列表，這對於鏈表是不可能的。

---

但是...您可以同時實現既是樹又是鏈表的混合數據結構。你會用那個看起來是這樣的一個節點類型開始什麼：

private class Node <T> { 
    private Node<T> next; 
    private Node<T> prev; 
    private Node<T> left; 
    private Node<T> right; 
    private T value; 
    ... 
    } 

然後建立使用left和right領域的樹木，並使用next和prev領域的鏈表。

數據結構的列表方面可以用一個Comparator進行排序，該數據結構的樹方面可以使用第二Comparator責令 ...允許基於第二Comparator的排序O(logN)查找。

我不確定這是否符合您的要求（它們沒有明確說明），但相當接近。