Блог

Я могу найти элемент в отсортированном наборе (с поддержкой BST) в O(logN) . Теперь я хотел бы получить индекс этого элемента. Например, в set {1, 3, 4, 10} индекс 4 равен 2 , а индекс 1 0 равен в.

Очевидно, что я могу просто выполнить итерацию по набору, поэтому тривиальным решением является O(N) . Можем ли мы добиться большего успеха, вероятно, используя свойства BST и / или вспомогательные структуры данных?

С помощью простого BST, где порядок вставки элементов задан случайным образом, у вас есть способ определить, на сколько точно элементов меньше заданного элемента, не переходя по дереву.

Если бы у вас было сбалансированное дерево, такое как красно-черное дерево, то вы могли бы, по крайней мере, установить нижнюю и верхнюю границы индекса из-за ограничений на высоту дерева. Если порядок вставки элементов в BST неслучаен, то опять же, вы могли бы сказать что-нибудь о высоте дерева, не обходя его, и дать некоторую оценку приблизительного индекса.

Что касается вспомогательных структур данных, вы могли бы создать вспомогательный словарь, который сопоставляет элементы с их индексом. Однако построение этого индекса занимает O (N), и индекс устаревает при добавлении новых элементов в BST, так что это хорошо работает только для BST с нечастыми обновлениями.

Другим решением является расширение узлов BST двумя свойствами: index и count. Индекс показывает, сколько элементов меньше, чем в этом узле, в дереве. Количество указывает, сколько элементов было в BST, когда вы в последний раз обновляли индекс этого узла. С помощью относительно простых изменений в вставке, удалении и поиске в BST, которые не влияют на эти базовые операции за пределами постоянного времени, и могут получить индекс элемента непосредственно в O (1).

По сути, когда вы вставляете новый узел, для каждого узла, который вы проходите по вашему пути вниз, если новый элемент меньше (т. Е. ваш следующий шаг — к левому дочернему элементу), увеличивайте как индекс, так и количество этого узла. Когда вы находите место нового элемента, вы присваиваете ему количество, основанное на его родительском элементе, и индекс, основанный на его родительском элементе и левом дочернем элементе. В результате элементы большего размера, чем новый, будут иметь неправильный индекс, но вы можете легко обновить его при поиске элемента, обратившись к значению count родительского элемента — разница между count родительского и дочернего элементов говорит вам, сколько вставок меньших элементов произошло с момента последнего обновления дочернего индекса, поэтому вы просто добавляете эту разницу к индексу.