文章/答案/技术大牛

发布

问Java树集排序算法
EN

Stack Overflow用户

提问于 2013-07-17 02:01:28

回答 1查看 5.3K关注 0票数 1

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

    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

现在的问题是：

为什么把美国比作美国？

2.为什么其他所有人都不能与美国相比？是否设置为Root?？

即使它被设置为root，为什么不能与root进行比较。3.可以有更少的比较，比如zimbabwe可以与不是Britain的东西进行比较(即从一开始就不是)。

java

collections

tree

set

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-07-17 02:07:25

这篇文章可能需要很多润色。你的问题的一般答案是排序树的二进制性质。我们期望一个值，最大值，应该只需要与树中的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比较。你的数据集越大，这种情况就越难创建，尽管很容易创建不平衡的小分支，例如在这种情况下，如果美国是“最低”值，它永远不会被移动。但这棵树的其余部分可以完全平衡。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/17683803

复制

相似问题

问Java树集排序算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java树集排序算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java树集排序算法
EN