Поиск логического решения

[kevgenia]

Кто-то помнит задания на логику?

Есть ряд цифр 12, 6, 2, 1, 4, 3, 5, 8, 7, 9, 10, 11, 14, 13. Они записаны по принципу обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево). Надо постороить из этих цифр обратно двоичное дерево.
Есть такое возможный ответ (другие тоже возможны).

Что нужно делать, чтобы построить это дерево? Как думать логически? Куда смотреть? Ну первая цифра вверху - это ясно. А дальше?

Когда дерево готово, то его расписать на цифры ерунда. Но когда начинаешь строить, то путаешься, то цифр мало, то много! Как надо подходить к задаче? Знаю, что есть правильный ход! мозг кипит

Еще одна задача на логику! КАК получается такой ответ?

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

запись создана: 15.03.2016 в 15:10

@темы: Высшее образование, Наука

Comments

[Пастух Бабочек]

Эммм, может, я не прав, но строили мы так:

Первое число - вершина, второе либо больше, либо меньше. Если оно больше - пишем справа, если меньше, то слева. Третье число проверяется сначала с первым уровнем, потом со вторым (2 меньше 12-ти и меньше шести, значит пишем слева под 6-ю) и так далее.

Но правило такое: проверяются ВСЕ уровни, поэтому число 4-ре находится справа под 2-кой. И если под уровнем есть ветка с новым, то число заносится следующим.

[Седьмая Вода]

Упс, у меня получилось, что от 9 не две ветки идут - 10 и 11, а одна правая с ними обоими. А такое, как в "возможном ответе", не знаю, по какому принципу и строить (

[Пастух Бабочек]

Седьмая Вода, у меня так же выходит, а то не логично как-то получается, с чего вдруг 9 стало больше 10

[yako-kaede]

двоичное дерево может быть двух видов: выровненное и невыровненное.
Существует правило обхода двоичного дерева: сверху вниз, слева направо.
Поэтому:
Невыровненное дерево строить просто:
первый элемент становится корнем.
Следующий входящий элемент сравнивается с корнем. Если он меньше - уходим в левую (относительно нас на рисунке) ветвь, если больше - в правую.
На следующем уровне опять же тупо сравниваем наш элемент с узлом и уходим ниже, в левую ветвь этого узла либо в правую - и т.д., пока наш элемент не займёт место в последнем уровне.

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

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

[yako-kaede]

ЗЫ: а с 10 и 11 под девяткой - имхо, ошибка рисовавшего картинку.
если не менять стандартные правила построения дерева, то 10 никак не может оказаться слева под 9, она будет слева под 11, на новом уровне.
Может, конечно, тот, кто составлял задачу, считает, что можно сделать доп.правило, что последний элемент из заданных в задаче можно запихивать, куда получится, если есть свободное место на текущем уровне, но на практике такое послабление правил ничего, кроме проблем, не принесёт - т.к. в реале двоичные деревья используются для индексирования (и, соответственно, ускорения поиска) данных, а в реале новые данные могут добавляться постоянно - и если какой-то элемент дерева будет нарушать стандартное правило, то вся канитель окажется бесполезной - поиск по дереву начнёт сбиваться и глючить.

[CD_Eater]

12, 6, 2, 1, 4, 3, 5, 8, 7, 9, 10, 11, 14, 13

разбиваем на 3 группы - сначала одно число, потом все меньше его, потом все больше его
(12) L=(6, 2, 1, 4, 3, 5, 8, 7, 9, 10, 11) R=(14, 13)

и так далее, применяя тот же алгоритм для каждой подпоследовательности (пока чисел больше 1)
6, 2, 1, 4, 3, 5, 8, 7, 9, 10, 11
(6) L=(2, 1, 4, 3, 5), R=(8, 7, 9, 10, 11)

14, 13
(14) L=(13) R=()

когда всё сделаем, рисуем (L = левая ветка, R = правая)

[kevgenia]

Седьмая Вода, Пастух Бабочек, yako-kaede, вы уловили, что меня смущает - если это бинарное дерево (где левый и правый ребенок или больше или меньше родителя), то почему внизу эта путаница с 9,10 и 11?

Еще вопрос - в описании бинарного дерева стоит только "имеет максимум два ребенка". Как быыыыы в самом определении бинарного дерева нет указания на то, что...

двоичное дерево может быть двух видов: выровненное и невыровненное.

Так что в принципе, если по условию просто двоичное дерево без указания "упорядоченное", то цифры вообще можно писать как хочется, не оглядываясь на то, что что-то там меньше или больше родителя.
CD_Eater, отличная схема, должна ускорить работу. Еще бы реально понятно - какое именно дерево должно получится в итоге и почему в самом примере ошибка(?), будет замечательно

[yako-kaede]

kevgenia,
я вот ещё что нашла - "двоичную кучу" (мы такое то ли не изучали, то ли я просто забыла начисто из-за неиспользования на практике). В ней как раз и узлы формируются сортировкой, и для последнего ряда делается отступление от правила - "заполняется слева направо"
Очень похоже, что на рисунке таки она:
двоичная куча

[kevgenia]

yako-kaede, Спасибо за ссылку. Википедия спасает всегда, когда нужна короткая инфа по делу.
Самое глупое, что двоичная куча есть еще в других задачках и там прямо написано - получить из ряда чисел heap. А в этой задаче указано - бинарное дерево должно получится в итоге ((

[yako-kaede]

kevgenia,

бинарное дерево должно получится в итоге

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

[kevgenia]

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

да вот как сказать задание звучит Die Preorder-Traversierung eines Binärbaums ergibt folgende Ausgabe: 12, 6, 2,
1, 4, 3, 5, 8, 7, 9, 10, 11, 14, 13. Zeichnen Sie den zugehörigen Binärbaum
Я при переводе ничего не добавляла.

[yako-kaede]

"при обходе двоичного дерева был получен следующий результат --- нарисуйте соответствующее двоичное дерево."

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

[kevgenia]

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

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

[kevgenia]

либо "двоичная куча" без ошибки

нет, это не может быть двоичной кучей. Я только что про нее почитала. У нее классически условия

Значение в любой вершине не меньше, чем значения её потомков. - но тут больший элемент стоит не в корне, 12 меньше 14, значит условие не выполнено
Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.- это я вообще не догнала
Последний слой заполняется слева направо. - да, это есть

[yako-kaede]

Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.- это я вообще не догнала

это значит, что если у левой ветви максимальное количество уровней Р,
то у правой оно может быть Р-1, Р или Р+1

Кстати, я вот прикинула, как бы я решала такую задачу "с нуля" (если бы не было привычки, из-за которой сразу же подумалось о сортировочном дереве) - то есть, без оглядки на то, что значения в узлах должны как-то соотноситься друг с другом, а просто тупо "двоичное дерево".
я бы начала с того, что определила количество уровней в моём дереве: пересчитала элементы - тут их 14, и прикинула по степеням двойки, сколько для них нужно уровней, чтоб все поместились - тут получается 4.
А потом бы начала рисовать дерево с максимальным уровнем 4 по тем же правилам, по которым деревья обходят: сверху вниз, слева направо.
Сначала вниз влево до самого низа, потом правый элемент от предыдущего узла, потом снова на узел вверх - и добавить его правый элемент, а от него вниз - и т.д.
Дерево в итоге получается совсем другое (но вроде бы - если я ничего не путаю - его обход даёт нужную последовательность):

[kevgenia]

Дерево в итоге получается совсем другое (но вроде бы - если я ничего не путаю - его обход даёт нужную последовательность):

Мне все больше кажется, что задания ужасно сформулированы. Я обновила пост еще одной задачей.

[yako-kaede]

kevgenia,

Я обновила пост еще одной задачей.

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


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


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