Подскажите с бинарным деревом
Есть обычное бинарное дерево, понадобилось его сохранить в файл и быстро восстановить обратно.
Узел дерева:
struct Node < void *item; Node* child[2]; >
Погуглил немного, в том числе и по этому сайту, пока ничего работающего не нашёл. Подошёл бы и псевдокод, а то сам что-то никак не соображу 🙁
Может кто делал уже такое на C++, поделитесь?
#1
13:50, 5 фев 2012
// псевдокод void save( Node & n )< save( n.item ); for( int i=0; i2; ++i )< save( bool( n.child[i]!=0 ) ); if( n.child[i]!=0 )< save( *n.node[i] ); > > > void load( Node & n )< load( n.item ); for( int i=0; i2; ++i )< bool e = 0; load( e ); if( e )< n.node[i] = new Node( ); load( *n.node[i] ); > > >
#2
13:57, 5 фев 2012
Вот чёрт, как это я про рекурсию забыл.
Спасибо огромное!
#3
14:31, 5 фев 2012
Danni
> Подскажите с бинарным деревом
Подсказать с кем-то/чем-то.
Я все думаю — это по правилам русского языка или нет? Просто интересно.
#4
14:59, 5 фев 2012
#5
15:04, 5 фев 2012
Danni
Я не об этом. Мне реально интересно. Уже который раз задумываюсь.
#6
15:13, 5 фев 2012
Ну уж если так, то «Помогите с бинарным деревом» — вот это правильно, а выше, согласен, написал чушь. Вот только все же поняли 🙂
#7
19:00, 5 фев 2012
Если дерево строго бинарное, то нет никакого смысла хранить указатели на детей — это лишний оверхед на нелокальность данных и обращения к памяти. Проще и эффективнее хранить все узлы в линейном массиве, при этом для узла номер i детьми будут 2i и 2i + 1. Сериализуется и десериализуется такое дерево тоже как линейный массив.
#8
17:17, 7 фев 2012
А можно поподробнее? В рамках этой задачи не важна скорость, но для общего развития пригодится.
То-есть просто хранить всё дерево в массиве, тогда динамический массив нужно пересоздавать при добавлении детей, или я не так понял?
- satan claws
- Постоялец
#9
18:29, 7 фев 2012
> Проще и эффективнее
> А можно поподробнее
организация дерева в линейном виде создает больше проблем, чем решает
во-первых, для хранения (2^N) + 1 элементов необходимо выделять 2^(N+1) памяти, в т.ч. реаллоцироваться при росте
во-вторых, для каждого элемента необходимо хранить bool is_valid; чтобы помечать занятые и свободные ячейки
в-третьих, операция удаления внутреннего узла становится огромной попоболью
в-четвертых, такой же попоболью становится операция перебалансировки дерева
учитывая вышеизложенное, понимаем, что такое дерево имеет выгоду (по сравнению с нормальным) только для хранения каких то достаточно статичных данных, для которых мы хотим получить O(log N) при поиске, ну и локальность данных ляляля — ну и напрашивается вывод, какого хера мы не используем для этих целей тупо отсортированный массив?
#10
18:52, 7 фев 2012
satan claws
> учитывая вышеизложенное, понимаем, что такое дерево имеет выгоду (по сравнению
> с нормальным) только для хранения каких то достаточно статичных данных, для
> которых мы хотим получить O(log N) при поиске
это неверно. такая структура данных подходит для любого бинарного дерева, единственное условие — сбалансированность.
satan claws
> какого хера мы не используем для этих целей тупо отсортированный массив?
удали или добавь в отсортированный массив за O(log n) элемент.
- satan claws
- Постоялец
#11
19:40, 7 фев 2012
Suslik
> удали или добавь
удали в своем линейном дереве за O(log n) корень дерева, а я посмотрю
можно было бы подумать, что единственное преимущество над отсортированным массивом в этом случае — простое добавление элемента, но это преимущество имеет смысл, только когда у тебя всё еще есть свободное место в хвосте выделенной области памяти
когда этого места нет, нужна та же реаллокация
кроме того, как я уже показал, необходимо хранить места под все ячейки, а не только те, которые заняты
поэтому добавь в заполненное дерево элемент за O(log n), а я посмотрю
соответственно, при высоте дерева 10 тебе необходимо аллоцировать 2^11 ячеек, хотя на самом деле тебе нужно хранить, возможно, в 2 раза меньше, плюс вместо накладных расходов из 2 указателей тебе тоже надо хранить накладные расходы — признак занятости ячейки
вывод — если нужно частое добавление или удаление из структуры данных, линейный массив будет примерно так же плох, как и такая организация дерева
раз в структуру редко добавляют и редко удаляют, но нужен поиск за log n — берем отсортированный массив, а не изобретаем велосипед, открывая глаза на оверхед и локальность доступа к памяти
#12
20:55, 7 фев 2012
ради бога. тебе виднее.
Как сохранить дерево в файл, а после его загрузить?
Если дерево нормально сбалансировано: пишем корень, прямо как есть. далее обходим дерево и пишем все проходимые узлы в направлении движения вниз. всегда придерживаемся одного правила движения, например сначала идем налево, по возвращении — направо. все указатели в файле особого смысла не имеют. Но по потому, что они не NULL при чтении можно будет понять, что в данной точке мы более не углублялись. А зная это мы можем прочитать блоки в точно таком порядке как писали. При чтении меняем все указатели на новые
25 ноя 2018 в 16:20
@Mike: А как это связано с тем, сбалансировано дерево или нет?
Как сохранить и считать бинарное дерево из файла?
Формат д. б. задан, о каках-либо стандартах не наслышан Более того, должен существовать API для чтения. В противном случае результат неопределён.
Источник: otvety. google. ru/otvety/thread?tid=1dda846b59d69523
Федор ШляпаПрофи (706) 11 лет назад
Отлично, это то, что надо.
Остальные ответы
есть такая штука — fstream
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Как сохранить бинарное дерево в файл c
Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
30.11.05 19:56: Перенесено из ‘C/C++. Прикладные вопросы’
Re: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 25.11.05 15:11 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
1) xml или любой другой деревянный язык
2) обход дерева в глубину (parent-left-right) :
Рекурсивная запись и рекурсивное же чтение. Поскольку некоторые дочерние узлы могут отсутствовать, то нужно записывать признаки их наличия (2-битовое поле на один родительский узел или по булеву признаку каждому индивидуально).
3) обход дерева из глубины (left-right-parent) :
Фактически, в файле оказывается программа для стекового автомата: взять два указателя на узлы (возможно, нулевые) со стека, прочитать данные из файла, сконструировать родительский узел и запихать в стек.
3) поперечный обход дерева (left-parent-right) : надо подумать.
Плюс состоит в том, что даже на несбалансированном дереве будут затраты O(1) на глубину стека как при записи, так и при чтении. Минус — в нетривиальности.
Перекуём баги на фичи!
Re[2]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 25.11.05 16:01 |
| Оценка: |
1) Это нужно написать на С++.
2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?
3) Дерево не сбалансированно.
А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?
Re: Сохранение и востановление дерева в файл.
| От: | diro |
| Дата: | 25.11.05 16:16 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
Вопрос как дерево хранится . Например можно хранить его в массиве, где left, right указывают на индекы в этом массиве ( -1 читай, никуда не указывают ). Нулевой элемент — это всегда node. Т.е. тогда возьмешь и массив в файл сдампиш — и дело с концом. Ну там еще размер куда — нить сунуть придется. Возможно, что это можно использовать как некий переходник.
struct TreeItem
TreeData data;
int left, right;
>;
Re[2]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 25.11.05 17:23 |
| Оценка: |
Здравствуйте, diro,
Вот дерево
template class T> class CTree_Item < private: struct TItem < T Data; int left; int right; >Item; CTree_Item *left_child; CTree_Item *right_child; CTree_Item *parent; CTree_Item(T const &d, int l,int r, CTree_Item *lchild, CTree_Item *rchild, CTree_Item *p); CTree_Item(CTree_Item *copy); public: T const& Get_Data(); int const& Get_Left(); int const& Get_Right(); void Set_Data(T &d); void Set_Left(int const &x); void Set_Right(int const &x); . friend CTree; >; template class T> class CTree < private: CTree_Item *Root; void Redefintion(CTree_Item *p, int x, bool bl); public: CTree(); ~CTree(); void Add_Item(int lt, T d); T Delete_Item(int lt, int rt); void Save_to_file(char file[255]); void Load_from_file(char file[255]); . >Для оформления С++ного кода пользуйся тэгом [c]-[/c]. Кодт
Re[3]: Сохранение и востановление дерева в файл.
| От: | Кодт | |
| Дата: | 25.11.05 23:56 | |
| Оценка: | +1 | |
Здравствуйте, AndreyGor, Вы писали:
AG>Здравствуйте, Кодт,
AG>1) Это нужно написать на С++.
Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.
AG>2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?
Если узла нет, то пишешь маркер «здесь узла нет». А если есть, то «здесь узел есть, читай дальше». Например.
Можно и другими способами — скажем, для поперечного обхода можно просто указывать глубину каждого узла — по ней (и по порядку следования) дерево восстанавливается однозначно.
AG>3) Дерево не сбалансированно.
Не имеет значения.
AG>А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?
Открой файл заранее и передай его хэндл или ссылку на его объект внутрь рекурсивной функции.
struct TreeNode < Some data; shared_ptrleft, right; >; // рекурсивные функции - operator> для чтения - принимают ссылки на потоки ostream& operator << (ostream& ost, shared_ptrnode) < if(!node) ost '-'; // маркер "здесь узла нет" else ost '+' // маркер "здесь узел есть" data left // мы твёрдо знаем, что сперва запишем (возможно, отсутствующий) левый узел right; // а затем - правый. return ost; > istream& operator >> (istream& ist, shared_ptr &node) < char exist; ist >> exist; // сперва прочтём маркер if(!exist) node = shared_ptr(); // нулевой указатель else < node = shared_ptr(new TreeNode); ist >> node->data >> node->left // читаем левый узел (возможно, что он будет нулевым. ) >> node->right; // читаем правый узел. > return ist; > // "лицевые" функции создают потоки внутри и вызывают рекурсивные функции, передавая туда ссылки void save_tree(string filename, shared_ptr root) < ostream ost(filename); ost void load_tree(string filename, shared_ptr& root) < istream ist(filename); ist >> root; >Перекуём баги на фичи!
Re[4]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 26.11.05 16:53 |
| Оценка: |
Здравствуйте, Кодт, Вы писали:
К>Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.
Нужно примерно следующее:
реализовать родовой класс бинарного дерева с указателями на производные узлы.
Класс должен поддерживать типовые для работы с деревьями функции.
Под типовыми для работы с деревьями понимаются следующие функции:
1. Создание пустого дерева
2. Включение нового узла в структуру дерева
3. Удаление узла из структуры дерева
— с уничтожением производных узлов
— без уничтожения производных узлов
4. Обход дерева и распечатка структуры дерева
5. Поиск узла с заданным значением в информационном поле
6. Запись дерева в файл
7. Чтение дерева из файла
8. Уничтожение дерева
Реализовать нужно на VS в виде консольного приложения.
В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!
Re[5]: Сохранение и востановление дерева в файл.
| От: | Кодт | |
| Дата: | 26.11.05 19:34 | |
| Оценка: | 4 (1) | |
Здравствуйте, AndreyGor, Вы писали:
AG>Нужно примерно следующее:
AG>реализовать родовой класс бинарного дерева с указателями на производные узлы.
Просто чтобы договориться о терминах.
Что такое родовой класс? Generic, что ли?
Производные узлы — имеется в виду, что элементы дерева могут быть производных классов, или это просто дочерние узлы?
AG>Класс должен поддерживать типовые для работы с деревьями функции.
AG>Под типовыми для работы с деревьями понимаются следующие функции:
AG>1. Создание пустого дерева
AG>2. Включение нового узла в структуру дерева
AG>3. Удаление узла из структуры дерева
AG> — с уничтожением производных узлов
AG> — без уничтожения производных узлов
AG>4. Обход дерева и распечатка структуры дерева
Есть несколько разных обходов:
— нисходящий (родитель-дети)
— восходящий (дети-родитель); например, так вычисляются формулы
— поперечный (левый-родитель-правый); если дерево упорядочено, то такой обход сохраняет порядок элементов
— в ширину (корень, дети, внуки, правнуки. )
и т.п.
Интересно, что для первых трёх видов обхода не нужна ни рекурсия, ни дополнительные коллекции. Достаточно, чтобы дочерний узел ссылался на родителя.
AG>5. Поиск узла с заданным значением в информационном поле
Если дерево не упорядочено, то поиск сводится к обходу.
AG>6. Запись дерева в файл
AG>7. Чтение дерева из файла
AG>8. Уничтожение дерева
AG>Реализовать нужно на VS в виде консольного приложения.
AG>В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!
Пример рекурсивной функции, сохраняющей дерево в нисходящем обходе, я уже привёл. Можешь доработать его напильником (ну или кувалдой), и будет щасте.
Если дерево несбалансировано, то глубина рекурсии может оказаться непозволительно большой. Поэтому стоит задуматься о том, чтобы написать нерекурсивную версию функций записи, а главное, чтения.
Интересный этюд для программирования
Перекуём баги на фичи!
Re[6]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 27.11.05 08:34 |
| Оценка: |
Здравствуйте, Кодт, Вы писали:
К>Просто чтобы договориться о терминах.
К>Что такое родовой класс? Generic, что ли?
К>Производные узлы — имеется в виду, что элементы дерева могут быть производных классов, или это просто дочерние узлы?
Родовой класс — это шаблон.
Производные узлы — это просто дочерние узлы.
По поводу обхода дерева: это все понятно, спасибо. Не понимаю как после записи в файл восстановить его структуру в точности такой какой она была.
Re[7]: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 28.11.05 13:06 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>По поводу обхода дерева: это все понятно, спасибо. Не понимаю как после записи в файл восстановить его структуру в точности такой какой она была.
А вот и подумай, как
Будем считать, что отсутствующий дочерний узел (нуль) — это фиктивный лист.
Выполняем обход PLR. Почему именно его: в нём родительские узлы появляются до своих дочерних, так что при чтении будем сразу наращивать финальное дерево, а не держать ничего в уме.
При записи: встречаем нормальный узел, пишем маркер «есть» и данные узла; встречаем фиктивный — пишем «нет».
При чтении: держим в уме предыдущий посещённый узел. Читаем маркер (и данные, если «есть»), создаём новый узел (либо нуль, если «нет») и прикрепляем его к дереву туда, где он должен был появиться при обходе. Переходим на него (или перескакиваем, если он фиктивный — как обычно).
Единственная тонкость — как отличать свеже-подцепленный фиктивный узел от ещё не подцепленного. (При обходе).
Можем выполнить обход LRP. В этом случае дерево будет строиться из поддеревьев, и потребуется стек полуфабрикатов (в худшем случае — линейной глубины). С помощью одного хитрого хода (правда, ценой гораздо бОльшего времени работы при записи) можно сократить его до логарифмической глубины. А именно, нужно писать сперва более глубокие поддеревья. И указывать, в каком порядке следовали дочерние узлы свежесоздаваемого родителя — L,R или R,L.
Я ещё не знаю решения (но знаю подходы), и расцениваю эту задачу как этюд. Попробуй решить её сам.
Перекуём баги на фичи!
Re: Сохранение и востановление дерева в файл.
| От: | eao197 | http://eao197.blogspot.com |
| Дата: | 28.11.05 13:13 | |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
SObjectizer: Агентно-ориентированное программирование на C++.
Re[2]: Сохранение и востановление дерева в файл.
| От: | eao197 | http://eao197.blogspot.com |
| Дата: | 28.11.05 13:19 | |
| Оценка: | 23 (1) | |
Здравствуйте, eao197, Вы писали:
AG>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
E>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
SObjectizer: Агентно-ориентированное программирование на C++.
Re[3]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 28.11.05 14:46 |
| Оценка: |
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, eao197, Вы писали:
AG>>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
E>>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
E>Например, вот здесь: http://it.kgsu.ru/C_DIN/din_0065.html
Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей. А я не уверен, что у меня будет именно так!
Re[4]: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 30.11.05 14:06 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG> Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей. А я не уверен, что у меня будет именно так!
А ты используй фиктивные листья!