radix trie with rank/select operations

Question

Теперь я реализую trix (также называемый patricia trie) для индексации отсортированных строк символов. Мне нужна операция rank(), чтобы узнать, сколько узлов существует в левой части совпадающего узла. Более формально,

rankT(x) = |{t∈T | t < x}| for T⊆U and x∈U, where T is a radix trie and U is a universe of key. 
meaning that calculation of the number of left leaf nodes in the trie. 

Например, есть три клавиши, такая, что

key set = {"abc", "def", "ghi"}, and index is 0, 1, 2. 

Так что Patricia TRIE хранит эту, как показано ниже:

 root 
    /| \ 
    abc def ghi 

и ранг функция() должна return 1, если ключ «def», и 0, если клавиша «abc».

Мой вопрос в том, как эффективно реализовать операцию rank()? Я думаю, что перерасчет ранга узла после каждой вставки неэффективен.

Экспозиция натальной синтаксического дерева, как показано ниже: http://en.wikipedia.org/wiki/Radix_tree

Благодаря ~

Answer 1

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

Так, например, вы могли бы иметь базисное синтаксическое дерево, как (номер в Paren этого количества слов в поддереве) слова "а", "BCD", "BG" и "DEF"

root 
/| \ 
a(1) | def(1) 
    b(2) 
    / \ 
    cd(1) g(1) 

Чтобы найти rank() словесного "BG". Вы начинаете в узле g(1) и вы идете вверх:

• На узле b(2) вы вы накапливаете значения всех поддеревьев слева от g(1). Установить ранг (bg) = размер (cd)
• На узле root вы накапливаете значения всех поддеревьев слева от b(2). Так ранг (вд) = размер (кд) + размер (а) = 1 + 1 = 2

Чтобы найти rank() слова "DEF"

• На узле root вы вы накапливают значения всех поддеревьев слева от def(1). Так ранг (DEF) = размер (а) + размер (б) = 2 + 1 = 3

Что касается выполнения касается: Для строки x вы можете пройти через корыто len(x) родительских узлов. И на каждом узле может быть не больше |A| детей, где A - ваш алфавит. Таким образом, время выполнения будет O(len(x) * |A|)