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

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

0 голосов
/ 10 февраля 2019

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

1 Ответ

0 голосов
/ 10 февраля 2019

Структуры данных Set в Java поддерживаются Map с.Набор хранит элементы в виде ключей на карте и использует статический объект в качестве заполнителя для значений.Следовательно, функции потолка и пола также делегируются на карту.Например; 

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

Таким образом, TreeSet поддерживается TreeMap.

TreeMap - это красно-черное дерево (по крайней мере, в Java 7 и более поздних версиях), которое является самобалансирующимся бинарным деревом поиска.https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

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

...