Внутренняя обработка потолка и напольная функция TreeSet в Java

Question

Я работаю над проблемой, где мне нужно найти пару, в которой разница значений не превышает k. Теперь дерево, установленное в 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

Set структуры данных в Java поддерживаются 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

Надеюсь это поможет