4551
правка
Сжатие и индексация дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Нотация и основные факты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
'''Базовые навигационные запросы''': предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. | '''Базовые навигационные запросы''': предок вершины u, i-й потомок вершины u, степень вершины u. Если дерево <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. | ||
'''Усложненные навигационные запросы''': потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом <math>\mathcal{T}</math>. Если <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. Примеры других операций см. в [2, 11]. | '''Усложненные навигационные запросы''': потомок вершины u j-го уровня, глубина вершины u, размер поддерева u, самый низкий общий предок пары вершин, i-я вершина согласно некоторому упорядочению вершин над деревом <math>\mathcal{T}</math>. Если <math>\mathcal{T}</math> является помеченным, эти операции могут быть ограничены получением некоторой метки <math>c \in \Sigma \;</math>. Примеры других операций см. в [2, 11]. | ||
Запросы о подпути: пусть дан помеченный подпуть | '''Запросы о подпути''': пусть дан помеченный подпуть <math>\Pi \;</math>, запрос ищет количество occ вершин дерева <math>\mathcal{T}</math>, являющихся непосредственными потомками <math>\Pi \;</math>. Каждое вхождение подпути может встречаться в дереве где угодно (т.е. он необязательно должен начинаться от корня). | ||