Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 17

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

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

Коррексия весов производится на этапе ребалансировки дерева, после операций вставки/удаления.
Всего голосов 1: ↑1 и ↓0 +1
Спасибо за комментарий, но у меня не теряется возможность быстрого поиска/вставки/удаления по значению. Можете посмотреть, в статье приведены результаты скорости выполнения для добавления и удаления по ключу. Всё производится за O(log(N)) как по ключу, так и по индексу
Всего голосов 1: ↑1 и ↓0 +1
Есть более простой и элегантный алгоритм(на мой взгляд):
Хранить в каждой ноде размер ее поддерева(считая ее). Назовем cnt.
Как осуществляется поиск:
ищем элемент с номером X:
если у левого поддерева этот cnt >=X — идем туда, если cnt левого= X-1, то это сама нода, где мы находимся, иначе идем искать в правом поддереве, уменьшив X на cnt левого +1
Комментарий пока не оценивали 0

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

Всего голосов 1: ↑1 и ↓0 +1
1. Идея похожа на nested set, но более эффективная при изменении дерева.
2. IMHO, если вам нужно обращаться к узлу дерева по его индексу, то что-то где-то пошло не так, и возможно есть более оптимальный способ хранения данных.
Всего голосов 1: ↑1 и ↓0 +1
Советую обратить внимание на Декартово дерево (treap, cartesian tree). В разделе про «неявные декартовы деревья» описана реализация массива со вставкой в середину за O(log(n)). В том варианте, который там предложен, нет возможности доступа по ключу, только по индексу, но не думаю, что это сложно будет сделать.

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

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

Всего голосов 1: ↑1 и ↓0 +1
в неявном трипе невозможно искать (а не просто сложно реализовать) по значению (в лучшем случае можно просто рядом положить какое-то бинарное дерево по значениям для проверки, но индекс вроде как не получить), т.к. они не упорядочены и обновляются.
Комментарий пока не оценивали 0
Наверно я не с той стороны зашел. Тут уже достаточно много написали про то, что исходная задача (быстрый поиск порядковой статистики) вроде как решается добавлением дополнительного поля в узел, которое отслеживает суммарный размер поддерева с корнем в этом узле, в том числе и обычное декартово дерево. Неявное декартово дерево я больше привел в качестве примера, где эта величина вычисляется и используется.
Комментарий пока не оценивали 0
Не совсем понятно, зачем 2 каунтера, достаточно одного — сколько элементов слева. Ищем индекс N, у вершины слева Z элементов. При N = Z мы нашли нужный, при N > Z идём вправо с индексом N — Z — 1, при N < Z идём влево с индексом N.
Всего голосов 1: ↑1 и ↓0 +1
Каунтер только один — countLefter. Поле add нужно для Lazy Propagation, чтобы не менять каунтеры у всех вершин, которые правее
Всего голосов 1: ↑1 и ↓0 +1
Так в варианте, о котором я говорю, нужно менять каунтер только у вершин на пути, по которому мы нашли элемент и только если мы при этом шли влево. Это же происходит и у вас, только ещё иногда и с полем add. Единственный «сложный» случай — удаление, нужно будет менять ещё и у какой-то из ветвей.
Всего голосов 1: ↑1 и ↓0 +1
Подобной структуры данных я не нашёл, коллеги и друзья, у которых спрашивал, тоже не предложили ничего похожего. Если вам известна реализация подобной идеи, прошу сообщить мне.
Вы на верном пути. Еще несколько шагов и вы изобретёте колесо AVL дерево.
Где для узла храниться только указатели на левы и правый узел и перекос, который поддерживается в диапазоне от -1 до +1.
Комментарий пока не оценивали 0

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

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

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

Публикации

Разблокировать темную тему

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr