LINUX.ORG.RU

Дерево, список и соседи

 , ,


0

2

По мотивам: Прикрутить список к элементам уже содержащим ссылки на соседей?

У меня предполагается структура данных, которую можно визуально представить так:

root
|
-> a
   |
   -> b -> c -> d
   |       |
   |       -> h -> i -> j -> k
   |
   -> e -> f -> g

Каким образом я могу обеспечить удобный доступ из любого узла в любой другой узел?

Мыслю так, на примере «a»:

Добавить в список только потомков «b» и «e», а так же указать этим «b» и «e» что их родитель это «a».

Затем, «скрепить» соседей «b» и «c» и соседей «c» и «d», указав для «c» и «d», что их родитель тоже «a».

Повторить процедуру скрепления соседей для «e» как для «b».

Повторить процедуру для «c» как для «a».

Таким образом, смотря на любой узел, если левый сосед NULL, значит этот узел в списке родителя, если правый сосед NULL, значит узел в конце «отростка», если список потомков не пуст, то можно провалиться глубже, ну и у каждого узла есть указатель на родителя для подъёма вверх.

Всё ли я предусмотрел? Насколько сложно будет этим разруливать при добавлении, удалении, перемещении узлов? Есть ли более подходящие варианты взаимосвязей для такой структуры данных?

Мне кажется, будет проще сделать просто дерево:

struct Node
  {
	list<Node> children;
	T data;
  }

И тут два варианта минимум: держи в каждом элементе ссылку на корень, от которого можно вести поиск, либо параллельно веди хеш-таблицу вида <имя, Node&> и ищи через неё

XMs ★★★★★ ()
Ответ на: комментарий от deep-purple
struct Node
  {
	list<Node&> children;
	Node &root;
	T data;
	Node &next() { return root.next(*this); }
	Node &next(const Node &node)
	  { return *(find(node) + 1); }
	list<Node&>::iterator find(node)
	  { return find(begin(children), end(children), node); }
  }

Аналогично всё остальное

XMs ★★★★★ ()
Ответ на: комментарий от XMs

С именем понятно, они у меня в мапе валяться будут по уникальному имени. Но то для другого. Тут же, когда они все в одном списке потомков, нужно отличать «первых» в «отростке», чтобы было понятно, что предыдущий отросток закончился и новый начался.

deep-purple ★★★★★ ()

Какое-то соц. извращение: чем отличается «родитель» от «соседа»? Ты сперва определись с иерархией, потом рисуй дополнительные связи - иерархические (соц.) лифты.

anonymous ()
Ответ на: комментарий от deep-purple

чем отличается «родитель» от «соседа»

Ничем. Только уровнем вложенности.

Ты хочешь получить «прошитое дерево» для быстрого обхода всех узлов?

anonymous ()
Ответ на: комментарий от XMs

Там в список к родителю добавляются только первые узлы отростков. И все узлы отростков (включая первые) связываются как prev-curr-next, где предыдущего или следующего может не быть, если узел стоит вначале или в конце отростка.

deep-purple ★★★★★ ()
Ответ на: комментарий от anonymous

для быстрого обхода всех узлов

Не для обхода, а для движения вправо. На примере схемы из стартпоста, движение вправо:

Первый шаг. У «a» два потомка «b» и «e», у них нет потомков, работаем с ними.

Второй шаг. Тут «c» и «f». У «f» нет потомков, а вот у «c» есть — «h», значит работаем с «h» и «f».

Третий шаг. Работаем с «i» и «g».

Четвертый шаг с «j».

Пятый с «k».

deep-purple ★★★★★ ()
Ответ на: комментарий от anonymous

«d» для «c» не потомок, а сосед, он будет рассматриваться, когда шагну вправо.

Да, я очепятался там выше — «d» рассматривается в один шаг вместе с «i» и «g».

deep-purple ★★★★★ ()
Последнее исправление: deep-purple (всего исправлений: 2)
Ответ на: комментарий от deep-purple

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

anonymous ()
Ответ на: комментарий от anonymous

Ок, представь это не деревом, а разветвлёнными рельсами, на которых стоят вагоны. Над вагонами слева направо едет кран-балка. За один шаг разгружаются те вагоны, которые оказались в тот момент под кран-балкой. А «a» и «c» в данном случае, паровозики, которые разгружать не надо.

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

И да. О боже (то есть админ), сделай так, чтобы за редактирование отнимали звездочку. А то есть тенденция непрекращаемого зазвездения даже абсолютных бездарей-редакторов.

anonymous ()
Ответ на: комментарий от deep-purple

Что мне представлять? ЖД-состав с разветвляющейся цепочкой вагонов? У тебя абсолютно выдуманая структура данных, котороя не прошла проверку ни на формальность, ни на реальность. То есть она нерешаема ни формально, ни реально. Тебе никто не поможет из формального или из реального мира. Иди в свой выдуманный мир и проси там помощи.

anonymous ()
Ответ на: комментарий от anonymous

выдуманая структура данных

А другие были не выдуманы и появились раньше человечества?

нерешаема

Я её решил ещё в старт посте. И лишь спросил нет ли более простого и удобного варианта.

deep-purple ★★★★★ ()

посмотри (вроде даже у Кнута в томе где и про В+ и В* деревушки) как бинарным деревом всегда можно представлять n-арные деревья - ну и подтюнь чанкованием по нужной тебе константе.

anonymous ()