Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи:
1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его.
2. Найти элемент по ключу, и заменить значение этого элемента и парочки соседей с каждой стороны.
Вроде бы не должно быть проблем:
В первом случае находим элемент, запоминаем указатель/итератор и с ним работаем. Т.е. тут надо сделать один поиск.
Во втором — также находим элемент, запоминаем указатель/итератор, после чего по стандартному алгориму обход дерева находим соседей.
В джаве есть встроенное сбалансированное дерево TreeMap, но я не вижу у него подходящих методов.
Поиск по ключу есть (get/replace), но он возвращает значение. Чтобы заменить элемент в дереве, нужно делать еще один поиск.
Также вроде бы нет возможности взять соседний элемент, надо делать еще один поиск.
Да, в худшем случае взятие соседнего элемента имеет логарифмическую сложность, как и поиск по ключу,
но ведь далеко не каждый случай худший.
Я просто не вижу нужных методов, или их действительно нет по какой-то причине?
Здравствуйте, bzig, Вы писали:
B>merge — в любом Map теперь есть
Спасибо. Не заметил его
B>TreeMap реализует интерфейс https://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html, там есть нужные методы
И что это за методы?
Там есть пачка методов, которые возвращают Map.Entry — но от этой entry нет никакой навигации.
Еще есть ceilingEntry/floorEntry, но они принимают значение ключа, а не итератор, а значит, делают обычный логарифмический поиск.
Здравствуйте, f95.2, Вы писали:
f> Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи:
А дешевые добавления|удаления эл-тов тебе тоже нужны?
f> 1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его. f> 2. Найти элемент по ключу, и заменить значение этого элемента и парочки соседей с каждой стороны.
f> Вроде бы не должно быть проблем: f> В первом случае находим элемент, запоминаем указатель/итератор и с ним работаем. Т.е. тут надо сделать один поиск.
Это вроде просто floorEntry(key).setValue(newVal)
f> Во втором — также находим элемент, запоминаем указатель/итератор, после чего по стандартному алгориму обход дерева находим соседей.
Если я правильно понял, можно найти интервал и его обработать: subMap(key-1, true, key+1, true)
Здравствуйте, PZI, Вы писали:
PZI> F2>делают обычный логарифмический поиск. PZI> А может и не делают
Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять.
Здравствуйте, ·, Вы писали:
·>Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять.
Ну, я про то, что поиск идет не по значениям ключей. И сложность там вроде О(1) в итоге, не логарифм.
Давно я правда этими глупостями не занимался, может что и забыл.
Там есть tail/head, так что в одну сторону можно получить итерацию. В обе стороны — не вынесено в публичный интерфейс.
Так то у них есть непубличный метод getEntry, который возвращает непубличный TreeMap.Entry, а не Map.Entry. И есть пара непубличных методов successor/predecessor, который от этого TreeMap.Entry могут вперёд и назад ходить. Если прямо невтерпёж как эти методы нужны, то можно или через reflection их вызывать, но этот способ грозят уже окончательно убрать в будущих версиях или откопировать TreeMap целиком к себе и сделать методы публичными.
Здравствуйте, f95.2, Вы писали:
F2>Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи: F2>1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его.
Map.get(key), Map.put(key, value)
F2>2. Найти элемент по ключу
Map.get(key)
F2>и заменить значение этого элемента
Map.put(key, value)
F2>и парочки соседей с каждой стороны.
NavigableMap.lowerKey(key), NavigableMap.higherKey(key), потом Map.put(key, value).
Здравствуйте, PZI, Вы писали:
PZI> ·>Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять. PZI> Ну, я про то, что поиск идет не по значениям ключей. И сложность там вроде О(1) в итоге, не логарифм.
Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать.
PZI> Давно я правда этими глупостями не занимался, может что и забыл.
Глупости, конечно. Вызов дважды (да хоть десять раз!) метода O(log(n)) имеет сложность O(10*log(n)) == O(log(n)) всё равно.
Здравствуйте, ·, Вы писали:
·>Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать.
И начинают искать со сложностью O(log(n)) по всей мапе, да? И именно по значению ключа, а не "ищут" бакет по значению хеша ключа, да?
Или мы про ботаников-идиотов, которые заморачиваются со сложностью на мапе, но делают так, чтоб у них ключи возвращали одинаковый хеш?
Ну и почему ты решил, что там будет именно O(log(n)), а не O(n) тогда? Всегда ли жаба искала по бакету двоичным поиском?
В общем я думаю ты прекрасно понял о чем я, буквоедством заниматься — так себе заниятие.
PZI>> Давно я правда этими глупостями не занимался, может что и забыл. ·>Глупости, конечно. Вызов дважды (да хоть десять раз!) метода O(log(n)) имеет сложность O(10*log(n)) == O(log(n)) всё равно.
Здравствуйте, PZI, Вы писали:
PZI> ·>Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать. PZI> И начинают искать со сложностью O(log(n)) по всей мапе, да? И именно по значению ключа, а не "ищут" бакет по значению хеша ключа, да?
В сабже — TreeMap, там нет никаких бакетов и хешей. Т.е. таки да, O(log(n)) по всей мапе. Или я что-то не знаю.
PZI> В общем я думаю ты прекрасно понял о чем я, буквоедством заниматься — так себе заниятие.
В том-то и дело, что не понял.
Здравствуйте, ·, Вы писали:
·>В сабже — TreeMap, там нет никаких бакетов и хешей. Т.е. таки да, O(log(n)) по всей мапе. Или я что-то не знаю.
офак, да. Что-то у меня хешмап на уме... Соррян, был не прав
·>В том-то и дело, что не понял.
да, мой косяк.