реализация индекса двоичного дерева дерева с использованием таблиц символов

Question

Я читаю об осуществлении индекса с использованием таблиц символов в книге автора Роберт Седвик в «Алгоритмах на C++».

Ниже фрагмент из книги

Мы можем адаптировать бинарные деревья поиска для построения индексов в точно же образом, как мы обеспечили косвенность для сортировки и куч. Упорядочить ключи, которые нужно извлечь из элементов с помощью ключевого элемента Функция, как обычно. Более того, мы можем использовать параллельные массивы для ссылок , как это было сделано для связанных списков. Мы используем три массива, по одному для элементов, левых ссылок и правильных ссылок. Ссылки являются индексы массива (целые числа), и заменить ссылки на ссылку, такие как

х = х> л

во всем коде со ссылками массивов, таких как

х = л [х] ,

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

Этот способ реализации BSTs, чтобы помочь в поиске больших массивов из элементов иногда полезно, потому что позволяет избежать дополнительных расходов на копирование элементов во внутреннее представление ADT, и накладных расходов распределения и строительство по новым , Использование массивов не подходит, если пространство стоит на высоте, а таблица символов растет и заметно уменьшается, особенно если трудно оценить максимальный размер таблицы символов до . Если нет точного размера прогноз возможно, неиспользованные ссылки могут занимать место в пробе массив.

Моих вопросов по данному тексту являются

1. Что автор подразумевает под «мы можем использовать параллельные массивы ссылок, как мы это делали для связанных списков»? Что означает эта статута и что такое параллельные массивы.

2. Что означает ссылка автора, являются индексами массива, и мы заменяем ссылки, такие как x = x-> l с x = l [x]?

3. Что автор подразумевает под «Другой важной особенностью этого подхода является то, что он позволяет добавлять дополнительные массивы (дополнительную информацию, связанную с каждым узлом) без изменения кода древовидной манипуляции». ?

Answer 1

Вы, кажется, отредактировали текст, чтобы извлечь полезные ссылки. Либо это, либо у вас более ранняя версия текста.

В моем третьем издании указано, что строковые индексы описаны в разделе 9.6, где он охватывает процесс, а параллельные массивы объясняются в главе 3. Параллельные массивы просто хранят полезную нагрузку (ключи и, возможно, данные, которые удерживаемые в дереве) и указатели влево/вправо в трех или более отдельных массивах, используя индекс, чтобы связать их вместе (x = left[x]). В этом случае вы можете получить что-то вроде:

int leftptr[100]; 
int rightptr[100]; 
char *payload[100]; 

и так далее. В этом примере узел # 74 будет иметь свои данные, хранящиеся в payload[74], а левые и правые «указатели» (фактически индексы), хранящиеся в left[74] и right[74] соответственно.

Это в отличие от имеющих один массив структур со структурой холдинга полезной нагрузки и указатели вместе (x = x->left;):

struct sNode { 
    struct sNode *left, right; 
    char payload[]; 
}; 

Таким образом, для ваших конкретных вопросов:

1. Параллельные массивы просто отделяют информацию древовидной структуры от информации полезной нагрузки и используют индекс для связывания информации из этих массивов.

2. Поскольку вы используете массивы для ссылок (и эти массивы теперь содержат индексы массива, а не указатели), вы больше не используете x = x->left для перемещения к левому ребенку. Вместо этого вы используете x = left[x].

3. Управление деревьями интересует только ссылки. Имея ссылки, отделенные от полезной нагрузки (и другой, возможно, полезной информации), код для управления древовидной структурой может быть проще.

Answer 2

Если вы еще не сделали, вы должны перевернуть обратно в книге в раздел о связанных списках, где он говорит, что этот метод был использован ранее (это, вероятно, объясняется там).

Параллельные массивы означают, что у нас нет структуры для хранения информации о узле.

struct node { 
    int data; 
    struct node *left; 
    struct node *right; 
}; 

Вместо этого у нас есть массивы.

int data[SIZE]; 
int left[SIZE]; 
int right[SIZE]; 

Это параллельные массивы, так как мы будем использовать тот же индекс для доступа к данным и ссылки. Узел представлен в нашем коде индексом, а не указателем.Таким образом, для узла 4, данные по

data[4]; 

Левая ссылка на

left[4]; 

Добавление большего количества информации в узле может быть сделано путем создания еще один массив того же размера.

int extra[SIZE]; 

Дополнительные данные для узла 4 будет

extra[4];