Войти
ПрограммированиеФорумОбщее

структура данных: над дерево

#0
20:34, 3 сен. 2019

Всем привет!

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

Теперь мы берем любую ветку этого дерева, и перемещаем, нужно эффективно перевязать "красные/зеленные" указатели в новом дереве.

Спасибо!


#1
(Правка: 21:10) 21:09, 3 сен. 2019

IROV..
У тебя ссылки только у родителя на детей и у этих детей на родителя?
Тут все просто, берешь корневой узел веки и удаляешь его из родителя. Дальше присваиваешь другому узлу этот узел в дочерний и прописываешь ему нового родителя.

Или если нужно перевести детей, то аналогично, но уже с каждым ребенком в отдельности.

#2
21:26, 3 сен. 2019

foxes
> У тебя ссылки только у родителя на детей и у этих детей на родителя?
Нет, дву направленное дерево

struct Node
{
  Node * parent;
  vector<Node *> children;
}

попробую показать примерную конечную структуру

struct SuperNode
{
  Node * normal;
  Node * reds;
  Node * greens;
}

есть такой супер узел, у которого есть всегда указатель на "нормальную" ноду - белое дерево.
опционно у него есть компонент красный узел - который связывает его в красном дереве.
и так же зеленый если он зеленный.

одновременно он может быть и красным и зеленым, но всегда белый.

проблема в том что когда мы берем "белый" узел, и перетаскиваем, у него в детях детей детей могут быть зеленые которые указывают на пра пра прадедов, и вот его нужно будет переставить, по сути нужно будет искать вверх пока не найдем зеленое дерево и тд.

Но это не сложно, ад начинается когда эти ноды должны оставить свой порядок после "ребалансировки"

задача легко решается если все дерево заново перестраивать :)

#3
21:53, 3 сен. 2019

IROV..
> Нет, дву направленное дерево
Это тоже самое что я описал, только в связке между родителем и детьми.
IROV..
> есть такой супер узел
Все эти указатели - это указатели на родителя?

#4
23:56, 3 сен. 2019

foxes
Эти указатели это компоненты, при инициализации если нужно создать красный узел выделяется под него память и он участвует в структуре. Считай это как бы Н узлов в одном узле, где только нормал всегда обязан присутствовать

#5
0:04, 4 сен. 2019

На него ни кто не ссылается, он просто содержит некие ноды из разных деревьев?

#6
(Правка: 0:15) 0:13, 4 сен. 2019

foxes
Нет, его якорем является нода нормал. Дерево по сути одно, просто его узлы имеют цвета. Некоторые красные некоторые зеленые, многие не имеют цветов.

#7
0:28, 4 сен. 2019

IROV..
Каким образом SuperNode встраивается в само дерево? Она выглядит безучастным, учитывая что она не наследуется от Node. Сама структура дерева не меняется и держится только на Node.

#8
(Правка: 2:39) 2:37, 4 сен. 2019

foxes
Можешь унаследовать вместо Node * normal. Это вопрос вкуса ;)

Но согласен скорее нужно так

struct SuperNode : Node
{
  NodeRed * red;
  NodeGreen * green;
}

Где ноды ред и греен похожи по сути с ноде

#9
3:04, 4 сен. 2019

Не, не знаю :)

#10
3:36, 4 сен. 2019

IROV..
попробуй нарисовать минимально возможное дерево до и после перемещения с проблемой и как должно быть, а то подобное:

проблема в том что когда мы берем "белый" узел, и перетаскиваем, у него в детях детей детей могут быть зеленые которые указывают на пра пра прадедов, и вот его нужно будет переставить, по сути нужно будет искать вверх пока не найдем зеленое дерево и тд.

не объясняет сути проблемы.
#11
20:23, 6 сен. 2019

Aroch
https://docs.google.com/document/d/1Y9ddN6-yNDy-4VyM4HdPB61zn0_Kj… F3SgUTIg/edit

#12
(Правка: 21:06) 21:04, 6 сен. 2019

IROV..
> https://docs.google.com/document/d/1Y9ddN6-yNDy-4VyM4HdPB61zn0_Kj…
> F3SgUTIg/edit
когда у поддерева меняется предок, просто опускаешься от его корня обходом в ширину до тех пор, пока не найдёшь первый ненулевой указатель на зелёный узел, для него переприсваешь родителем первый зелёный узел-родитель (тоже рекурсией находится).

но, вообще говоря, бинарные деревья так никто не хранит. бинарные деревья хранятся в массиве без явного хранения указателей, а дети вершины с номером i хранятся в элементах 2 * i и 2 * i + 1. в таком виде оба дерева можно вообще хранить отдельно друг от друга и во время переназначения родителя поддерева, задача сводится к тому, чтобы просто найти то же самое поддерево в обоих деревьях.

#13
(Правка: 22:50) 22:47, 6 сен. 2019

IROV..
то есть тебе нужно найти детям ближайшего предка того же цвета.

prev_node - узел от которого передвигаем поддерево.
new_node - узел куда перенесли поддерево.

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

+ Показать

далее делаем рекурсивно обход для перемещенного поддерева:

+ Показать

#14
15:45, 8 сен. 2019

Suslik
То уже способ хранения дерева, проблема возникает тогда когда дочерние "сердечка" нужно воткнуть не в конец или начало списка детей рута, а в середину

Aroch
> то есть тебе нужно найти детям ближайшего предка того же цвета.
Да

Спасиб, почитаю код

ПрограммированиеФорумОбщее