Jessy_James Dec 23 2019 at 16:35

Индексируемое бинарное дерево

4 min

14K

Comments 26

Magikan Dec 23 2019 at 16:50

Один только вопрос к тегам b-tree != Binary tree. Бинарное дерево это когда у любого элемента строго не более 2х дочерних, а семейство B деревьев сильно ветвистые. Ну и сверху ещё много отличий

Jessy_James Dec 23 2019 at 17:53

Сократил так, binary в b. Не сильно в терминологию углублялся, исправлю.

lrrr11 Dec 23 2019 at 16:57

контейнер с нужными свойствами есть например в GNU PBDS
gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds

да и вообще я не верю, что не нашлось ни одной подходящей библиотеки, откуда можно скопипастить код. Классическая задача же.

Jessy_James Dec 23 2019 at 17:52

Это делалось не под конкретную задачу, а от нечего делать. За последние лет 8 я только один раз стэк писал для работы)

tsarevfs Dec 23 2019 at 18:57

У вас получилось что-то очень похожее на «Декартово дерево по неявному ключу».

Bambyrov Dec 23 2019 at 21:34

С чем-то подобным я публиковал сообщение 25.05.2015 на
www.cyberforum.ru/ms-access/thread60797-page3.html
У Вас это «вес», у меня «уровень». Конечно сейчас я уже пользуюсь схемой без связи по
уровню, но главная проблема — это когда данные меняются, и необходимо вставлять
в элемент разветвленного дерева, которой ближе к корню, элемент большего веса. Увеличивать вес этого элемента и всех родителей-не выход, потому как может оказаться,
что предлагают заглотить «папу».

Jessy_James Dec 23 2019 at 21:35

это когда данные меняются, и необходимо вставлять
в элемент разветвленного дерева, которой ближе к корню, элемент большего веса

Не очень понял, что здесь имеется ввиду. Вставка поддерева?

Bambyrov Dec 24 2019 at 16:14

Я имею ввиду, что структуру данных по некой заданной теме должен определять не программист, а пользователь. Поэтому делим данные на 2 типа: Элементы(вес 0) и Сборки (вес > 0). Типа: страница (Элемент вес 0) — Книга (Сборка вес 1), а книги на полках и т.д.Но если некий роман написан в 3х томах (вес романа=2), нужно следить чтобы Польз. не поместил книжную полку, где размещается этот роман ( ее вес=3) в качестве еще главы упомянутого романа. Т.е. в некоторой степени база должна быть готова к решению еще не возникших задач (автор еще и не думает писать 2ю главу). Да, вставка поддерева.

mayorovp Dec 24 2019 at 11:38

Ни разу не похоже на декартово дерево

tsarevfs Dec 24 2019 at 12:00

Я не смотрел как именно автор делает балансировку, и не утверждаю что это декартово дерево. Но прелдагаю вам почитать про структуру данных полное имя которой я привел.
Декартово дерево по неявному ключу
Идея как раз в том, чтобы хранить вспомогательную величину, которую автор называет «вес», и на ее основе получать порядковый номер элемента. Использовать декартово дерево оказывается удобно для балансировки и поддержания инварианта весов.

Jessy_James Dec 24 2019 at 12:11

Заметим, что фактически в данном случае ключ для какой-то вершины — это количество вершин, меньших неё.

Красивая формулировка, как раз так вот и сделал.

Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое поддерево — накапливаемая сумма не меняется, а если идём в правое — увеличивается на cnt(t->l)+1.

Все умное до меня уже было написано )

oleg-m1973 Dec 24 2019 at 13:30

А зачем в функции bntree::balance сделан обмен данными между узлами, при помощи копирования через this->tmb_data? В дереве не должно быть таких операций.

Jessy_James Dec 24 2019 at 13:46

Помню что по быстрому накидал как самый простой вариант. На тот момент в указателях что ли запутался, и ссылку на родителя не хранил еще. Надо переделать.

Jessy_James Dec 24 2019 at 16:10

Поправил.

ov7a Dec 26 2019 at 13:52

У меня какое-то дежавю.
https://habr.com/ru/post/479142/
Повторю свой комментарий оттуда — чем ваша идея отличается от дерева порядковой статистики, которое давным-давно описано в Кормене?

Jessy_James Dec 27 2019 at 10:21

Почитал Кормена. Идея ни чем, но мое дерево не красно-черное.

От соседнего поста отличается реализацией. У меня нет доп. поля:

Для всех вершин, которые на одну правее вышеупомянутых, увеличить add на 1

Когда искал как такое реализовать, не нашел подходящей структуры. И это статьи то же не было.

ov7a Dec 27 2019 at 19:54

Если у вас не сбалансированное ДДП, то тогда и сложности операций у вас будут в худшем случае линейные (в среднем все равно логарифмические).

Jessy_James Dec 27 2019 at 21:59

Балансирую на вставке.

ov7a Dec 28 2019 at 19:36

При удалении тоже надо балансировать, иначе можно поудалять листья таким образом, что дерево будет иметь линейную высоту.
Кроме того, попробуйте вставить в ваше дерево последовательно числа от 1 до 1000 — если я правильно понял ваш код, то высота в вашем дереве будет в районе 250 вместо ожидаемой 10-20

Jessy_James Dec 28 2019 at 20:45

Ок, если сервер с виртуалками на работе на НГ не выключили, то гляну.

Jessy_James Dec 30 2019 at 18:59

Проверил, балансирует как надо.

При удалении тоже надо балансировать

Я бы поспорил, на счет необходимости. Список мы конечно можем получить таким образом (если заполним дерево и будем только удалять), но при 1-ой же вставке дерево отбалансируется.

ov7a Dec 30 2019 at 20:18

Насчет проверки моего примера — согласен, я ошибся, и думал, что балансируется по весу, а не по высоте на его основе. Меня не покидало ощущение, что что-то не так: вроде у вас похожее с АВЛ-деревом условие (высоты левого и правого деревьев отличаются не более чем на единицу), но при этом у вас только 1 поворот на операцию, а в АВЛ их может быть два.
Вот пример: {8, 4, 30, 2, 6, 10, 36, 9, 12,38, 13, 14, 15 };
https://ideone.com/recc7a
При его последовательной вставке в ваше дерево получится справа высота два, слева — 5. Явно нарушается ваш предполагаемый инвариант про баланс высот. Хотелось бы иметь формальное доказательство, что у вас там действительно логарифмическая высота — не факт, что найденый мой пример делает самый худший дизбаланс, наверняка можно похуже найти.

Насчет удаления — не согласен. У вас же после 1 поворота идет выход из цикла, значит при вставке отбалансируется только самый нижний кусочек.

Jessy_James Dec 30 2019 at 21:41

получится справа высота два, слева — 5

Да. Переделал, на полный проход балансировки после вставки:

p = child;
//break;

Попозже почитаю как в 2-ва поворота на балансировке делать.

vladich Dec 28 2019 at 10:03

Такая структура хорошо подходит для хранения и обновления рейтингов по какому-либо параметру.

NooneAtAll Jan 11 2020 at 21:05

А чем вам не понравился std::map?

Уже есть insert()

Если нужен доступ по номеру, то «std::map::begin() + k»

А имея итератор на позиции уже можно применить erase() или extract()

Везде все тот же log(N). Зачем заново изобретать велосипед?

Jessy_James Jan 11 2020 at 21:08

std::map::begin() + k

Так там нельзя. К it = std::map::begin() можно только применять ++, и пройти по всему map за время O(N)