在Java中TreeSet中的天花板和地板功能的内部工作

Question

我的工作，我需要找到对其中的值的差为至多为k的一个问题。现在树在java中设置确实对我来说，但我很想知道这是怎么工作的。我假设它创造某种桶和地图与一个HashMap中的一些值是桶。

我查了一下定义的IntelliJ但无法找到任何这也解释了它是如何工作的。

我发现这个代码在树状图，现在我想了解它是如何实际工作

final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }

Answer 1

Java中的Set数据结构由Maps支持。所述一组存储元件中的地图密钥，并使用静态对象作为值的占位符。因此，天花板和地板的功能也被委派到地图中。例如;

public E ceiling(E e) {
   return m.ceilingKey(e);
}

所以TreeSet由TreeMap支持。

该TreeMap是红黑树（至少在Java 7中及以后），这是一个平衡树。 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

希望这可以帮助