Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Hard_Club, Вы писали:
H_C>>помогите написать для собеседования функцию обхода бинарного дерева:
К>Эхъ, молодёжжж...
эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);
тут же способ быстрого удаления элементов из дерева. tree[idx].valid = 0. если операций удаления немного, то это хороший способ правда есть риск, что после множества удалений под конец дерево на 99% будет состоять из удаленных элементов, но на этот случай пишем сборщик мусора, удаляющий уже по науке.
ЗЫ, понятно, что задача предполагает обход именно по науке, но если дерево не задано явно, то можно и через for его обойти как массив, хотя зачтут ли такое решение -- вот тут я не знаю.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
К>>Эхъ, молодёжжж... М>эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);
Эх, практики... Ну и какой будет порядок обхода этого дерева?
Вот, например, двоичная куча, классически размещается в массиве. Линейному обходу массива соответствует обход дерева вширь (нулевой ярус, первый ярус, второй ярус и т.д.)
А сделать любой обход вглубь (поперечный, восходящий или нисходящий) — тут уже помощник нужен.
Кстати, этюд.
Пусть куча размером N размещена в массиве arr[0..N-1].
У узла k дочерние узлы — 2k и 2k+1.
Написать функцию j(i), соответствующую одному из обходов вглубь: т.е. пробегаем по arr[j(0)], arr[j(1)], ...
— аналитическое выражение
— итерационное, — j(i) как функция от j(i-1)
Рассмотреть варианты, когда дерево насыщено (N=2^h-1) и ненасыщено.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, мыщъх, Вы писали:
К>>>Эхъ, молодёжжж... М>>эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);
К>Эх, практики... Ну и какой будет порядок обхода этого дерева?
не понял. O(N). куда уж быстрее? (если под обходом понимается посещение всех узлов дерева).
понятно, что задача обхода поддерева так уже не решается (в общем случае).
К>Кстати, этюд. К>Пусть куча размером N размещена в массиве arr[0..N-1]. К>У узла k дочерние узлы — 2k и 2k+1.
... К>Рассмотреть варианты, когда дерево насыщено (N=2^h-1) и ненасыщено.
стоп! давайте все-таки ближе к практике. у математиков время доступа к любому элементу массива -- постоянно. на практике чтение от 0 до N-1 может быть в разы быстрее, чем чтение в разброс. а может отличаться и больше чем на два порядка, особенно если мы выпадаем в своп.
последовательное чтение массива даже в случае если он заполнен от силы на 10% не обязательно выполняется за большее время, чем обход дерева в порядке родства узлов. а потому с инженерной точки зрения абстрактное математическое решение не предсталяет никакого интереса и этот интерес тем меньше, чем больше дерево. для дерева с размеров в несколько гигов смысл насыщенности теряется. все равно читаемы мы сектор (в лучшем случае!). даже если в этом секторе у нас всего несколько узлов, а остальное -- пустота, время обработки пустоты — навряд ли ухудшит производительность. дерево может быть насыщено менее чем на 1%, но обрабатываться за тоже время, что и 100% насыщенное.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
А возможно ли сделать обратный линейный обход без дополнительной памяти?
Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...
Здравствуйте, Кодт, Вы писали:
> У узла k дочерние узлы — 2k и 2k+1.
бред (с)
1) если у нас есть функа трансляции узлов и эта функа задана заранее — зачем вообще нам такое дерево? дерево же вырождается...
2) для узла 0 получаем дочерей 0 и 1. мабуть вы хотели сказать: 3k+1 и 3k+2 ?
3) вообще идея массива в том, что в жизни у дерева есть узел q, у него дочки w и e, причем, q, w и e физически расположнены очень далеко друг от друга. (в начале, середине и конце файла, в котором хранится дерево). со всеми отсюда вытекающими...
4) еще про обход дерева -- как насчет (не)выделения доп. памяти, запрета на рекурскию и т.д.?
сравнивать одно решение с другим только через сложность -- не самая лучшая идея, т.к. как уже говорилось выше даже если k << n (<< — сильно меньше), то не нужно забывать о том, что последовательное чтение сильно быстрее чтения вразборс (и оно _точно_ сильно быстрее). потому в задаче о ненасыщенность придется юлить.
как уже писалось, если минимальная единица чтения порции информации содержит хотя бы один элемент, то в рамках этой минимальной единицы -- время обработки это константа. выиграть при "умном" обходе можно только когда в массиве есть единцы чтения, в которых вообще нет ни одного элемента, но тогда можно (и не так уж сложно) создать карту затяных областей или использовать массив списка массивов. и массив списка массивов это все равно проще обхода по "науке"
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, silent_bob, Вы писали:
_>А возможно ли сделать обратный линейный обход без дополнительной памяти? _>Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...
вот-вот. и учитывая специфику ЭВМ давайте добавим к этюду: без выделения доп. памяти и посещая каждый узел не более одного раза.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, Кодт, Вы писали: К>Здравствуйте, Hard_Club, Вы писали: H_C>>помогите написать для собеседования функцию обхода бинарного дерева: К>Эхъ, молодёжжж... H_C>>- слева-направо; H_C>>- справа-налево; H_C>>- сверху-вниз; H_C>>- снизу-вверх. К>Поперечные, нисходящий и восходящий порядки обхода. К>Подсказка: К>На самом деле, они делаются совершенно одинаковым способом! К>Попробуй сам сообразить, что же такого одинакового... К>
Здравствуйте, мыщъх, Вы писали:
К>>Эх, практики... Ну и какой будет порядок обхода этого дерева? М>не понял. O(N). куда уж быстрее? (если под обходом понимается посещение всех узлов дерева).
Ага, у любой задачи есть решение — красивое (for(i=0;i!=n;++i)), быстрое (O(n))... и неправильное.
Топикстартеру нужно сделать обходы вглубь (поперёк, поперёк, нисходящий и восходящий).
А ты предлагаешь — как попало, в порядке размещения узлов в массиве.
Вот тебе два примера.
1) я уже назвал, пирамида (которая из heap_sort)
2) отсортированный массив, порядок совпадает с поперечным обходом любого двоичного дерева поиска
Теперь сделай на отсортированном массиве восходящий или нисходящий обход. (Какого именно дерева? Их там C(n) штук).
Здравствуйте, мыщъх, Вы писали:
>> У узла k дочерние узлы — 2k и 2k+1. М>бред (с) М>1) если у нас есть функа трансляции узлов и эта функа задана заранее — зачем вообще нам такое дерево? дерево же вырождается...
Но это же всё равно дерево. В список не вырожденное.
М>2) для узла 0 получаем дочерей 0 и 1. мабуть вы хотели сказать: 3k+1 и 3k+2 ?
М>4) еще про обход дерева -- как насчет (не)выделения доп. памяти, запрета на рекурскию и т.д.?
Это всё время-деньги.
Например, для обхода произвольного дерева вширь нам потребуется или очередь узлов, ожидающих посещения, или мы можем совершить H+1 обходов дерева вглубь, спускаясь каждый раз на ярус h=0..H, где H — высота дерева.
То есть, или линейная память, или квадратное время.
М>сравнивать одно решение с другим только через сложность -- не самая лучшая идея
Заметь, это была твоя идея.
Здравствуйте, silent_bob, Вы писали:
_>А возможно ли сделать обратный линейный обход без дополнительной памяти? _>Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...
Если дерево двусвязное, т.е. есть функция parent(node) — например, в виде указателя на родительский узел, — то безо всякого стека и нахрапа.
Немножко покурить на мой рисунок, и всё станет ясно.
И заодно станет ясно, сколько времени требуется на полный обход любого двоичного дерева, вне зависимости от его сбалансированности.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, мыщъх, Вы писали:
К>Ага, у любой задачи есть решение — красивое (for(i=0;i!=n;++i)), быстрое (O(n))... и неправильное. К>Топикстартеру нужно сделать обходы вглубь (поперёк, поперёк, нисходящий и восходящий). К>А ты предлагаешь — как попало, в порядке размещения узлов в массиве.
я ж сразу сказал, что юмора не поймут и не зачтут
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.