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