Как получить по индексу элемент из бинарного дерева за приемлемое время?

[phantom-code]

Я точно не помню название этой структуры данных, но по сути вы переизобрели augmented binary tree, хранящее в каждом узле количество дочерних узлов (вес). Такая структура данных позволяет производить поиск/вставку/удаление узлов по индексу за O(log(N)), однако теряется возможность быстрого поиска/вставки/удаления по значению (сами данные).

Алгоритм поиска узла в таком дереве простой:
— Если искомый индекс меньше веса левого поддерева, переходим к левому дочернему узлу.
— Если искомый индекс больше или равен весу левого поддерева + 1, вычитаем из нашего индекса вес левого поддерева + 1 и переходим к правому дочернему узлу.
— Иначе мы нашли наш узел.

Коррексия весов производится на этапе ребалансировки дерева, после операций вставки/удаления.

[AlexanderUsatov]

Спасибо за комментарий, но у меня не теряется возможность быстрого поиска/вставки/удаления по значению. Можете посмотреть, в статье приведены результаты скорости выполнения для добавления и удаления по ключу. Всё производится за O(log(N)) как по ключу, так и по индексу

[Ketovdk]

Есть более простой и элегантный алгоритм(на мой взгляд):
Хранить в каждой ноде размер ее поддерева(считая ее). Назовем cnt.
Как осуществляется поиск:
ищем элемент с номером X:
если у левого поддерева этот cnt >=X — идем туда, если cnt левого= X-1, то это сама нода, где мы находимся, иначе идем искать в правом поддереве, уменьшив X на cnt левого +1

[Pand5461]

А почему теряются операции по значению? Кажется, если по индексу разрешить только поиск и удаление, то поиск/вставку/удаление по значению также быстро можно оставить.

[mobi]

1. Идея похожа на nested set, но более эффективная при изменении дерева.
2. IMHO, если вам нужно обращаться к узлу дерева по его индексу, то что-то где-то пошло не так, и возможно есть более оптимальный способ хранения данных.

[malkovsky]

Советую обратить внимание на Декартово дерево (treap, cartesian tree). В разделе про «неявные декартовы деревья» описана реализация массива со вставкой в середину за O(log(n)). В том варианте, который там предложен, нет возможности доступа по ключу, только по индексу, но не думаю, что это сложно будет сделать.

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

P. S. Чтобы понять, о чем вообще эта статья, нужно заглянуть под кат. Не надо так писать. Публикация — это не просто изложение потока мыслей.

[Ketovdk]

в неявном трипе невозможно искать (а не просто сложно реализовать) по значению (в лучшем случае можно просто рядом положить какое-то бинарное дерево по значениям для проверки, но индекс вроде как не получить), т.к. они не упорядочены и обновляются.

[malkovsky]

Наверно я не с той стороны зашел. Тут уже достаточно много написали про то, что исходная задача (быстрый поиск порядковой статистики) вроде как решается добавлением дополнительного поля в узел, которое отслеживает суммарный размер поддерева с корнем в этом узле, в том числе и обычное декартово дерево. Неявное декартово дерево я больше привел в качестве примера, где эта величина вычисляется и используется.

[411]

Не совсем понятно, зачем 2 каунтера, достаточно одного — сколько элементов слева. Ищем индекс N, у вершины слева Z элементов. При N = Z мы нашли нужный, при N > Z идём вправо с индексом N — Z — 1, при N < Z идём влево с индексом N.

[AlexanderUsatov]

Каунтер только один — countLefter. Поле add нужно для Lazy Propagation, чтобы не менять каунтеры у всех вершин, которые правее

[411]

Так в варианте, о котором я говорю, нужно менять каунтер только у вершин на пути, по которому мы нашли элемент и только если мы при этом шли влево. Это же происходит и у вас, только ещё иногда и с полем add. Единственный «сложный» случай — удаление, нужно будет менять ещё и у какой-то из ветвей.

[kovserg]

Подобной структуры данных я не нашёл, коллеги и друзья, у которых спрашивал, тоже не предложили ничего похожего. Если вам известна реализация подобной идеи, прошу сообщить мне.

Вы на верном пути. Еще несколько шагов и вы изобретёте колесо AVL дерево.
Где для узла храниться только указатели на левы и правый узел и перекос, который поддерживается в диапазоне от -1 до +1.

[AlexanderUsatov]

Про АВЛ-дерево я знаю)

[Lofv]

В любом случае, мне кажется, если человек смог изобрести «колесо», то это тоже не плохо. Его изобретали многие тысячи лет. Вдруг, он изобретет после этого колесо в колесе :)

[ov7a]

Еще в Кормене описано подобное как дерево порядковой статистики.
https://books.google.ru/books?id=UVg1LPacgRcC&pg=PA366&lpg=PA366&dq=дерево+порядковой+статистики&source=bl&ots=_VcQMlhYFC&sig=ACfU3U2jkcg12kdbh8ql4p9_S4f4iCmTrw&hl=ru&sa=X&ved=2ahUKEwjHuImmhqnmAhWlw8QBHTrHDNAQ6AEwBnoECAoQAQ#v=onepage&q=дерево%20порядковой%20статистики&f=false
Чем ваше решение отличается?

[malkovsky]

e-maxx.ru/bookz/files/cormen.pdf
исключительно в образовательных целях

[WASD1]

В похожей ситуации хранил значение (указатель на структуру данных) в двух коллекциях.

Плюсы: ничего не надо придумывать.
Минусы: не достойно статьи на Хабре.