alt text

У меня вопросов несколько вопросов, но из-за того, что они все однотипные я решил объединить их в один.
1. Где у дерева на картинке лево и право?
2. Где на рисунке вершины дерева или что такое вершины?

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

UPD: 0.1
Я согласен, что мои вопросы очень странные, но вот почему я их задал...
Я все же нашел алгоритм, который отображает дерево визуально - Алгоритмы построения поуровневого изображения деревьев. Состоит он из четырех глав, три вообще по несколько слов и только 4,2 можно назвать основным разделом. Но я не могу его понять, он меня постоянно путает.
Вот выписка:

Рассмотрим теперь вопрос о том, как реализовать за время O(n) шаг 1. В силу требования об идентичности изображения изоморфных поддеревьев, изображение каждого поддерева не должно зависеть от его положения в объемлющем дереве. Значит, для сравнения координат вершин поддеревьев T' и T'' достаточно рассматривать только координаты вершин, принадлежащих «границе» каждого поддерева. То есть, на каждом уровне можно сравнивать только x-координату самой правой вершины левого поддерева с x-координатой самой левой вершины правого поддерева. Для реализации этой идеи, введем понятие правого и левого контура поддерева.

Определение Левый контур L(T) бинарного дерева Т высоты h - это последовательность вершин v0,..vh , такая, что vi – это самая левая вершина на глубине i.

Правый контур R(T) определяется аналогично. При обходе дерева Т в обратном порядке будем поддерживать инвариант, гарантирующий, что по завершении обработки вершины v правый и левый контур поддерева с корнем в вершине v хранятся в виде связных списков. На Рис. 4.3 корень дерева Т показан черным кружком, а вершины левого и правого контуров показаны желтыми (серыми) кружками.
alt text
Расстояние между T' и T'' однозначно определяется расстоянием между корнями этих поддеревьев dist(r', r''). Для того, чтобы поместить правое поддерево как можно ближе к левому поддереву, надо сравнить позиции правого контура левого поддерева R(T') с позициями левого контура правого поддерева L(T'') для всех уровней, имеющихся в наиболее «коротком» из поддеревьев.

Подскажите мне на моем примере дерева с цифрами, где правый контур левого поддерева, а где левый контур правого поддерева?

UPD: 0.2
Определение гласит, что левый контур дерева состоит из самых левых вершин, а правый из самых правых. Получается, что на картинке левый и правый выделены желтым. А дальше идет

а вершины левого и правого контуров показаны желтыми (серыми) кружками.

Что для меня означает лывые - желтым, правые - серым. Но тогда это противоречит предыдущему определению.
Вот скажите, правый контур левого поддерева и левый контур правого поддерева - это вершины серого цвета? А на моей картинке это 6, 4, 2 и 11, 9, 8?

UPD: 0.3

alt text
alt text
Выше две картинки, одна из которых иллюстрирует координаты относительно своего корня, а вторая абсолютные. И я хочу спросить, как узнать, что левое поддерево нужно сместить на -3 значения относительно корня? ( если можно на моей картинке с номерами ) Ведь нужно считать все правые вершины левого поддерева, каковыми являются 6, 4, 2?

задан 20 Апр '15 14:35

изменен 20 Апр '15 22:13

Вопросы немного странные. На первый из них так и хочется ответить, что "лево" находится слева, а "право" -- справа. Как нарисовано, так и есть. Дело в том, что это свойства не самого графа (абстрактного), а свойства его укладки на (координатной) плоскости.

То же насчёт вершин: они здесь даны -- это числа от 1 до 13, реализованные в виде кружочков.

(20 Апр '15 14:56) falcao

@falcao: обновил ещё раз.

(20 Апр '15 15:43) shatal

@shatal: сейчас уже не успеваю вникнуть во все детали. Мне кажется, тут надо общую идею ухватить, чтобы не следить за всеми мелочами описания. Общая цель мне здесь так или иначе понятна, поэтому я завтра на свежую голову постараюсь что-то ещё добавить.

(21 Апр '15 1:29) falcao
10|600 символов нужно символов осталось
1

Здесь, как понимаю, корневое двоичное дерево хранится в машинной памяти, и далее его надо изобразить на плоскости. Начальный адрес (ячейка) хранит расположения корня дерева. Пусть это будет 1, как на исходном рисунке. По этому адресу можно узнать, какая вершина считается левым "потомком", и какая правым. У корня дерева это 2 и 8. Далее в ячейке 2 хранится информация, что шаг влево ведёт к вершине 3, а шаг вправо -- к вершине 4, и так далее. У концевых вершин (листьев) "потомки" отсутствуют. Также каждая ячейка кроме корневой хранит информацию о том, от кого она "произошла", то есть в какую ячейку надо идти назад (то есть вверх).

Рассмотрим такой известный алгоритма обхода дерева как "правило левой руки". Прежде всего, как он выглядит геометрически? Мы стоим вблизи вершины 1 и левой рукой касаемся "забора" между 1 и 2. Идём вдоль него, не отрывая руку. Регистрируем проход вершины 2. Далее начинается новый "забор", по которому доходим до 3. Далее эту вершину мы гладко огибаем и идём по очередному "забору" от 3 к 2, но уже по его противоположной стороне. И так далее. В какой-то момент мы снова придём в 1. Всё то, что мы посетили, относится к левой части корневого дерева. Далее так же обходим правую часть.

Итоговый порядок вершин при обходе здесь такой: 1-2-3-2-4-5-7-5-4-6-4-2-1-8-9-11-9-12-13-12-9-8-10-8-1 (если нигде не опечатался).

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

Надеюсь, эта информация как-то сможет помочь.

ссылка

отвечен 20 Апр '15 16:09

@falcao: спасибо, мне любая информация поможет. Я неделю пытался реализовать этот алгоритм, но так и не смог, хотя признаю, что отвел на него совсем немного времени. Но больше я не мог, язык которым написано это описание, почему-то не рисует в голове законченную картинку. Было всякое, но таких сложностей ещё не было. Хотел продолжить тему здесь, но наверное правильней будет создать новую тему, хотя сомневаюсь, что этот вопрос вызовет у кого-то сложность или интерес:)

(20 Апр '15 20:19) shatal

@shatal: мне кажется, здесь лучше понять сами идеи, которые лежат в основе того или иного метода. В книгах какие-то простые вещи этого уровня, имеющие понятный и наглядный смысл, приобретают весьма запутанную форму из-за академической манеры изложения. Такие тексты тяжело и излагать, и читать. Я с корневыми двоичными деревьями имел дело довольно часто, и знаю, что в литературе описания могут занимать много страниц, в то время как "на пальцах" там всё легко объясняется, и суть там простая и естественная. Это всё надо один раз хорошо понять, или даже самому придумать, но на стандартном языке.

(20 Апр '15 20:31) falcao

@falcao: я с Вами соглашусь, так как с отдельными частями работы с деревьями, будь то рекурсии или передвижения по дереву короткими путями, у меня сложностей не возникает, а возникают именно из-за восприятия информации.
И ещё маленький вопросик, который хотел спросить в комментах, но он к сожалению не поместился, по этому я его в основном вопросе допишу.

(20 Апр '15 22:09) shatal
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×281

задан
20 Апр '15 14:35

показан
1329 раз

обновлен
21 Апр '15 1:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru