Member 14836053 Ответов: 1

Что такое устойчивые узлы?


What is a sustabable nodes?


У меня есть узлы g (зеленый) и b (черный.
Вот вам поручение:

This exercise is about rooted binary trees. Each node x has fields x.parent, x.left and x.right denoting the parent, left
child, and right child of x. The root of the tree is denoted by root and root.parent = null. Furthermore, each node x also
has a field x.color, called the color of x, that can be either green or black. Throughout the exercise, we let n denote the
size of the input tree.

2.1 (2 %) A node x is sustainable if the color of x is green and the color of all descendants of x is also green. Consider
the tree below. Nodes with a g are green and nodes with a b are black. Mark all sustainable nodes in the tree. Do so
directly on the vertices in the tree.


Что я уже пробовал:

Я никогда не слышал об устойчивых узлах, как это должно работать?

OriginalGriff

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

1 Ответов

Рейтинг:
2

OriginalGriff

Спасибо за обновление - это помогает дать нам информацию, даже если это всего лишь ваш фактический вопрос домашнего задания!

Поэтому внимательно прочитайте этот вопрос - он точно указывает, что такое "устойчивый узел" :

Цитата:
Узел x устойчив, если цвет x зеленый и цвет всех потомков x также зеленый.

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

Поэтому создайте свое дерево, заполните его соответствующими данными и выполните поиск по дереву, чтобы определить устойчивые узлы.

Подсказка: я бы начал с того, что установил все узлы как неустойчивые и пересек дерево снизу вверх. Попадание в черный узел предотвращает устойчивость всех узлов над ним, поэтому нет смысла пересекать их.


Maciej Los

5ed!

Member 14836053

Спасибо это имело смысл ;-)

OriginalGriff

Всегда пожалуйста!