Комментарии 26
gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds
да и вообще я не верю, что не нашлось ни одной подходящей библиотеки, откуда можно скопипастить код. Классическая задача же.
www.cyberforum.ru/ms-access/thread60797-page3.html
У Вас это «вес», у меня «уровень». Конечно сейчас я уже пользуюсь схемой без связи по
уровню, но главная проблема — это когда данные меняются, и необходимо вставлять
в элемент разветвленного дерева, которой ближе к корню, элемент большего веса. Увеличивать вес этого элемента и всех родителей-не выход, потому как может оказаться,
что предлагают заглотить «папу».
это когда данные меняются, и необходимо вставлять
в элемент разветвленного дерева, которой ближе к корню, элемент большего веса
Не очень понял, что здесь имеется ввиду. Вставка поддерева?
Ни разу не похоже на декартово дерево
Декартово дерево по неявному ключу
Идея как раз в том, чтобы хранить вспомогательную величину, которую автор называет «вес», и на ее основе получать порядковый номер элемента. Использовать декартово дерево оказывается удобно для балансировки и поддержания инварианта весов.
Заметим, что фактически в данном случае ключ для какой-то вершины — это количество вершин, меньших неё.
Красивая формулировка, как раз так вот и сделал.
Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое поддерево — накапливаемая сумма не меняется, а если идём в правое — увеличивается на cnt(t->l)+1.
Все умное до меня уже было написано )
У меня какое-то дежавю.
https://habr.com/ru/post/479142/
Повторю свой комментарий оттуда — чем ваша идея отличается от дерева порядковой статистики, которое давным-давно описано в Кормене?
Почитал Кормена. Идея ни чем, но мое дерево не красно-черное.
От соседнего поста отличается реализацией. У меня нет доп. поля:
- Для всех вершин, которые на одну правее вышеупомянутых, увеличить add на 1
Когда искал как такое реализовать, не нашел подходящей структуры. И это статьи то же не было.
Если у вас не сбалансированное ДДП, то тогда и сложности операций у вас будут в худшем случае линейные (в среднем все равно логарифмические).
Балансирую на вставке.
При удалении тоже надо балансировать, иначе можно поудалять листья таким образом, что дерево будет иметь линейную высоту.
Кроме того, попробуйте вставить в ваше дерево последовательно числа от 1 до 1000 — если я правильно понял ваш код, то высота в вашем дереве будет в районе 250 вместо ожидаемой 10-20
Ок, если сервер с виртуалками на работе на НГ не выключили, то гляну.
Проверил, балансирует как надо.
При удалении тоже надо балансировать
Я бы поспорил, на счет необходимости. Список мы конечно можем получить таким образом (если заполним дерево и будем только удалять), но при 1-ой же вставке дерево отбалансируется.
Насчет проверки моего примера — согласен, я ошибся, и думал, что балансируется по весу, а не по высоте на его основе. Меня не покидало ощущение, что что-то не так: вроде у вас похожее с АВЛ-деревом условие (высоты левого и правого деревьев отличаются не более чем на единицу), но при этом у вас только 1 поворот на операцию, а в АВЛ их может быть два.
Вот пример: {8, 4, 30, 2, 6, 10, 36, 9, 12,38, 13, 14, 15 };
https://ideone.com/recc7a
При его последовательной вставке в ваше дерево получится справа высота два, слева — 5. Явно нарушается ваш предполагаемый инвариант про баланс высот. Хотелось бы иметь формальное доказательство, что у вас там действительно логарифмическая высота — не факт, что найденый мой пример делает самый худший дизбаланс, наверняка можно похуже найти.
Насчет удаления — не согласен. У вас же после 1 поворота идет выход из цикла, значит при вставке отбалансируется только самый нижний кусочек.
Такая структура хорошо подходит для хранения и обновления рейтингов по какому-либо параметру.
Уже есть insert()
Если нужен доступ по номеру, то «std::map::begin() + k»
А имея итератор на позиции уже можно применить erase() или extract()
Везде все тот же log(N). Зачем заново изобретать велосипед?
std::map::begin() + k
Так там нельзя. К it = std::map::begin() можно только применять ++, и пройти по всему map за время O(N)
Индексируемое бинарное дерево