Comments 22
P.S.: Коллекцию можно ещё больше ускорить за счёт использования красно-чёрного дерева вместо бинарного.
Красно-черное дерево — это реализация сбалансированного бинарного дерева поиска.
. При выборе TreeSet или TreeMap мы будем иметь O(log(n)) для вставки и поиска, но для поиска и удаления минимального будем иметь всего лишь O(1).
В стандартнах классах java.util.TreeMap#getFirstEntry работает за O(log n)
Вам на самом деле нужно не дерево, а min-heap. И прикрутить к нему HashMap который будет запоминать индекс в Heap для возможности работы с произвольным элементом.
Я думал насчет использования min-heap вместо бинарного дерева, но мне показалось, что использование обычного дерева позволит использовать для сравнения любые наборы данных. К тому же, что и min-heap и бинарное дерево имеют одинаковую асимптотику. Использование стандартной коллекции же не даст высокой производительности так как они реализованы для наиболее общих случаев и не используют дополнительные знания о структуре элементов. Что касаемо TreeMap, getFirstEntry наверное и имеет асимптотику O(log n), а вот getFirstKey должен иметь асимптотику как и у TreeSet, т.е. O(1), хотя я могу и ошибаться(чего очень хотелось бы ведь тогда я имею выигрыш в производительности и по этому методу).
2. Чтобы асиптотика операций над вашим деревом была логарифмической, высота дерева должна быть логарифмический, что из вашего кода не очевидно, в то время как TreeMap/TreeSet гарантируют логарифмическую сложность.
Кроме того
3. Если вы используете хеш, то не должны ли вы предусмотреть возможность коллизий? Или просто использовать HashSet, который уже умеет это делать.
4. Ваша функция connectNodes выглядит как-то странно, допустим вы хотите объединить два узла, у которых есть дети (в зависимости от реализации getElemeInArray, которую вы нигде не упоминаете, это может произойти при удалении элемента по значению), тогда посмотрим на этот код в самом начале функции:
if (compare(node, parent) < 0) {
node.left = parent;
parent.parent = node;
parent = node;
return parent;
}
вы проверяете, что один из них меньше и подцепляете больший к меньшему в качестве левого ребенка теряя все что там было в левом поддереве. Это особенно странно, потому что ваш connectNodes может быть вызван для братьев, но при этом работает для них как-то не симметрично, если один из них меньше, то вы тут же возвращаетесь из функции, а если другой меньше то вы идете в цикл.
Перед тем как заниматься сравнением производительности, не могли бы вы показать более или менее формально, что:
1. ваша структура данных вообще кооректно работает
2. что ваша асимптотика такая, как вы заявляете?
Для матрицы m на n такая функция без коллизий выглядит как i*n + j и хеш-функцией не является.
Просто функцией, вычисляющей индекс.
Хеш-таблицы — это вполне определенный класс структур данных, в которых самое трудное — это борьба с коллизиями. Ваша же структура данных на самом деле называется "массив" и изучается в школе.
"Я написал хеш-таблицу… без коллизий" звучит так же как и "я сам построил дом… для кошки".
Я реализовал дерево, в котором каждый узел может быть получен из массива на основании ключа — в моём случае хэш-кода элемента.
Ну и вконце-концов я не хэш-таблицу написал.
Действительно, для такого случая легко создать подходящую функцию, но если вы затачиваетесь только под этот случай, то зачем вообще переопределять хеш? Его можно забить внутри класса.
Почему вместо этого просто не параметризовать вашу структуру ассоциативным контейнером? Можно будет использовать простой массив, если возможно, а можно хеш-таблицу. И не нужно будет делать странных оговорок про хеш без коллизий.
public K firstKey() {
return key(getFirstEntry());
}
Здесь вызов key(entry) действительно работает за единицу, а вот getFirstEntry() работает за logN:
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
Куча, она же пирамида, имеет при той же асимптотике намного меньшую скрытую константу нежели сбалансированное бинарное дерево.
Просто за счет простоты алгоритма и локальности обращений к памяти.
PS а чтобы getFirstEntry работало за константное время, дерево должно быть прошитым
"Хэш-функция без коллизий" это примерно то же, что и первичный ключ сущности. Строил так дерево категорий по записям из базы. Сначала делаем массив объектов, индексированный по category.id, затем обращаемся по индексу category.parent_id и добавляем текущий объект в свойство children.
— 1, 10, 2 (тут мы получаем дерево высоты 2, в корне 1 в левом поддереве 2, в правом 10)
— 9 (9 станет левым ребенком 2, потому что 9 больше 1 и 2 в левом поддереве, но меньше 10, значит по коду идем в левое поддерево, где вставка уже делается очевидным образом)
— 3 (3 станет левым ребенком 2 как раньше было с 9, а 9 станет правым ребенком 2)
— 8 (8 станет левым ребенком 3)
— 4 (4 станет левым ребенком 3, а 8 станет правым)
— 7 (7 станет левым ребенком 4)
— 5 (5 станет левывм ребенком 4, а 7 станет правым)
Если я правильно понял, тот такой паттерн вырождает ваше дерево практически в бамбук, и при этих вставках
поле k вообще не проверяется. Мне серьезно кажется, что гораздо проще просто использовать TreeSet/TreeMap и после каждого обновления переискивать минимальный элемент.
Реализация на Java хешированного бинарного дерева