访问链接列表

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)查找。

我不确定这是否符合您的要求（它们没有明确说明），但相当接近。