Использование дерева для обхода отдельного набора элементов с одинаковыми родительскими / дочерними отношениями

Question

Вот повторение довольно загадочного заглавного вопроса:

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

Единственная разница между Конкретными и Прототипом деревьев - это дополнительные данные в узлах Бетон дерево.Предположим, что каждый узел дерева Concrete имеет указатель / ссылку на соответствующий элемент в дереве Prototype для общей информации об узле, но не имеет собственной родительской / дочерней информации:

Можно ли пройти через Бетонное дерево?

В частности, при наличии начального узла в Бетонном дереве и пути через дерево Прототипов возможно лиэффективно получить соответствующий узел в бетонном дереве?Может быть много бетонных деревьев, поэтому обратная связь с деревом прототипов невозможна.

Даже если мне не нужно оптимизировать вещи до такой степени в моем коде, это все ещеинтересная проблема!

Заранее спасибо!

ПРИМЕЧАНИЕ: Нет ограничений по фактору ветвления дерева - узел может иметь от одного до сотен дочерних элементов.

---

Дополнительные рассуждения / идеи:

Причина, по которой я спрашиваю, состоит в том, что кажется, что было бы бесполезно копировать информацию о родителе / ​​ребенке каждый разсоздается новый экземпляр Бетонного дерева, поскольку эта структура идентична дереву прототипа.В моем конкретном случае дочерние элементы идентифицируются по строковым именам, поэтому я должен хранить хеш-строку-указатель на каждом узле.Может быть много экземпляров Бетонных деревьев, и дублирование этого хеша кажется огромной тратой пространства.

В качестве первой идеи, возможно, путь может быть каким-то образом хеширован в int или что-то ещекоторый компактно идентифицирует элемент (не строку, поскольку он слишком большой), который затем используется для поиска конкретных элементов в хешах для каждого конкретного дерева?

Answer 1

Будет ли когда-либо изменено дерево прототипов (т.е. будут ли когда-либо вставлены или удалены узлы)?

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

Answer 2

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

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

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

Answer 3

Это возможно, когда есть известная зависимость между адресами узлов в оба дерева. В основном это означает, что узлы должны быть фиксированного размера и выделены все сразу. Конечно, также возможно использовать хеш-таблицу для отображения адресов первого дерева узлы для узлов второго дерева, но такая хеш-таблица должна иметь как минимум в 10 раз больше узлов чем первое дерево, иначе отображение будет слишком медленным.

#include <stdio.h>

typedef unsigned char byte;

struct Node1 {
  Node1* child[2];
  Node1() { child[0]=child[1]=0; }
};

struct Node2 {
  int N;
  Node2() { N=0; }
};

int main( void ) {

  int i,j,k,N = 256;

  Node1* p = new Node1[2*N];
  Node2* q = new Node2[2*N];

  // insert
  for( i=0,k=1; i<N; i++ ) {
    Node1* root = &p[0];
    Node1** r = &root;
    for( j=7;; j-- ) {
      if( r[0]==0 ) r[0]=&p[k++];
      if( j<0 ) break;
      r = &r[0]->child[(i>>j)&1];
    }
    q[r[0]-p].N = byte(i+123);
    // ^^^^^ - mapping from p[] to q[]
  }

  // check
  for( i=N-1; i>=0; i-- ) {
    Node1* r = &p[0];
    for( j=7; j>=0; j-- ) r = r->child[(i>>j)&1];
    if( q[r-p].N != byte(i+123) ) printf( "error!\n" );
  }

}

Answer 4

Просто сохраните отношения родитель-потомок в конкретном дереве и забудьте об этом. В лучшем случае это одно значение указателя, в худшем - два значения указателя. В любом случае вам понадобится как минимум столько же, чтобы сохранить связи между деревом прототипа и конкретным деревом.

Answer 5

Вы могли бы иметь конкретный лист для каждого узла-прототипа, но вам нужно было бы выполнить какое-то хеширование для каждого дерева (как вы предлагаете), чтобы разделить разные конкретные деревья. В этот момент вы понесли ту же стоимость хранения, что и совершенно отдельное дерево с избыточными указателями дочерних / родительских элементов. Вы определенно хотите получить ссылку от дерева прототипа на конкретные деревья.

Я вижу, что этот подход полезен, если вы хотите, чтобы структурные изменения в дереве прототипов влияли на все связанные конкретные деревья. Перемешивающие узлы мгновенно влияют на все конкретные деревья. Вы можете понести дополнительные расходы, так как будет невозможно передать одно конкретное дерево без отправки каждого конкретного дерева или выполнения какой-либо операции extract для удаления одного дерева.

Как правило, вы не сможете уникально кодировать путь в int.