Java 中 TreeSet 的 ceiling 和 floor 函数的内部工作

Question

我正在解决一个问题，我需要找到其中差值最多为 k 的对。现在 tree set in java 为我做了这个，但我很想知道它是如何工作的。我假设它创建了某种桶并将该桶与哈希图中的某些值映射。

我检查了 intelliJ 中的定义，但找不到任何解释其工作原理的内容。

我在 Treemap 中找到了这段代码，现在我想了解它的实际工作原理

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 数据结构由 Map 支持。该集合将元素存储为映射中的键，并使用静态对象作为值的占位符。因此，天花板和地板功能也委托给地图。例如;

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

因此 TreeSet 得到了 TreeMap 的支持。

TreeMap是一棵红黑树（至少在Java7及以后）是一棵自平衡的二叉搜索树。 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

希望对您有所帮助

Java 中 TreeSet 的 ceiling 和 floor 函数的内部工作

Internal working of ceiling and floor function of TreeSet in Java

java

treeset