1

只是出于好奇，我想知道 TreeSet 是如何维持秩序的。当然，通过元素对象的比较器或任何自定义比较器比较新元素以添加到以前的元素。但是可能有比比较所有更好的方法。让我们看一些代码：

    TreeSet<String> tset= new TreeSet<>(new comparator<String>());
    tset.add("america");
    tset.add("britain");
    tset.add("india");

    tset.add("checksolvakia");
    tset.add("china");
    tset.add("sri_lanka");
    tset.add("zimbabwe");

    for(String str:tset){
        System.out.println(str);
    }

在上面的代码new comparator<String>()中只是一个自定义比较器，用于进行正常的字符串比较。

The output drom above code is:
 i have been called times:1
values America America
 i have been called times:2
values Britain America
 i have been called times:3
values india America
 i have been called times:4
values india Britain
 i have been called times:5
values checksolvakia Britain
 i have been called times:6
values checksolvakia india
 i have been called times:7
values china Britain
 i have been called times:8
values china india
 i have been called times:9
values china checksolvakia
 i have been called times:10
values sri_lanka Britain
 i have been called times:11
values sri_lanka china
 i have been called times:12
values sri_lanka india
 i have been called times:13
values zimbabwe Britain
 i have been called times:14
values zimbabwe china
 i have been called times:15
values zimbabwe india
 i have been called times:16
values zimbabwe sri_lanka
america
britain
checksolvakia
china
india
sri_lanka
zimbabwe

现在的问题是：
1. 为什么将美国与美国相提并论？
2.为什么其他人都没有与美国相提并论？是否设置为Root？
即使它被设置为 root 为什么不与 root 比较。3.say zimbabwecould be compare to something not Britain(即不是从一开始)的比较可能会更少。

4

1 回答 1

3

这篇文章可能需要大量润色。您的问题的一般答案是排序树的二元性质。假设一个平衡的树，我们期望一个值，在最大值，只需要与树中的 Log(N) 条目进行比较，就可以找到它的正确位置。仅这一事实就回答了你所有的问题，除了第一个问题。不应将值与自身进行比较，插入树中的第一个值应设置为根，但在平衡树中，重要的是要注意，这并不意味着它将永远是根节点。根节点是“中间”值。为什么将美国与自身进行比较可能是您的比较器的边缘情况，以及一棵空树的行为，我喜欢路易斯对这个问题的评论。

在此处输入图像描述

如果您想插入 12，需要进行多少次比较？他们会有什么比较？如果树是平衡的，这将如何变化？当您可以回答这些问题时，您将回答您自己的问题，在此之前，文字描述可能没有帮助。

下面是树的内容，在每个单独的插入之后。 

America

America
    Britain

    Brit
Amer    Indi

    Brit
Amer        Indi
        Chec    

            Brit
Amer                Chin
              Chec          India
                                SriLanka        

            Brit
Amer                Chin
              Chec          SriLanka
                        India       Zimbabwe

请注意，我们正在尽最大努力通过使用所谓的“旋转”来保持平衡。这意味着我们永远不会完全“重新平衡”树（一项非常昂贵的操作），但是当我们可以通过在插入点移动节点来避免创建一个长“分支”时，我们会这样做。因此，我们有美国在那边，一旦它在树的左侧独立存在，就永远不会与任何事物相提并论。本质上，一旦一个对象有两个孩子，它就被固定在石头上，永远不会被移动。因此，我们所拥有的是“平均”Log(N) 比较，但我们仍然可以得到轻度不平衡的树，并最终在更糟糕的情况下进行 N/2 比较的情况下结束。你的数据集越大，这个场景就越难创建，尽管创建不平衡的小分支相当容易，例如在这种情况下，如果美国是“最低”价值，它永远不会被移动。但是树的其余部分可以完全平衡。

于 2013-07-16T18:07:25.020 回答