class Tree
{
private:
Tree* m_pParent; // родитель
Tree* m_pLeft; // левый ребёнок
Tree* m_pRight; // правый ребёнок
//... дополнительные переменные для поиска
//... прочие атрибуты
public:
Tree* AddLeft(Tree* pNew); // родить левого ребёнка
Tree* AddRight(Tree* pNew); // родить правого ребёнка
Tree* Parent() // получить родителя
{ return m_pParent; }
int ChildrenLeft() const; // посчитать количество детей слева
int ChildrenRight() const; // посчитать количество детей справа
Tree* FindLeft() const; // начать обход левого поддерева
Tree* FindRight() const; // начать обход правого поддерева
Tree* FindNext() const; // продолжить начатый обход поддерева
//... прочие операции
};
Помогите с алгоритмом
Просьба помогите, разобраться с тем как организовать базу и какой
алгоритм использовать для удобной работы.
Задача в следующем, необходимо организовать бинарную структуру
причем необходимо учитывать не только родителя каждого елемента,
но и отслеживать кол-во элементов в правом и левом плече. Причем
при добавлении нового элемента пользователь сам выбирает родителя
и в какое плечо родителя добавляет новый элемент. Ну и конечно
в итоге мы должны иметь возможность быстро и коректно выбирать
всех предков какогото объекта или наоборот всех предков. При етом
должна быть возможность быстро отследить кол-во елементов в
правом и левом плече выбранного елемента. Ну и тд. Буду благодарен
всем кто подскажет как можно решить ету задачу.
алгоритм использовать для удобной работы.
Задача в следующем, необходимо организовать бинарную структуру
причем необходимо учитывать не только родителя каждого елемента,
но и отслеживать кол-во элементов в правом и левом плече. Причем
при добавлении нового элемента пользователь сам выбирает родителя
и в какое плечо родителя добавляет новый элемент. Ну и конечно
в итоге мы должны иметь возможность быстро и коректно выбирать
всех предков какогото объекта или наоборот всех предков. При етом
должна быть возможность быстро отследить кол-во елементов в
правом и левом плече выбранного елемента. Ну и тд. Буду благодарен
всем кто подскажет как можно решить ету задачу.
Цитата:
Originally posted by xelat
Просьба помогите, разобраться с тем как организовать базу и какой
алгоритм использовать для удобной работы.
Просьба помогите, разобраться с тем как организовать базу и какой
алгоритм использовать для удобной работы.
Не понимаю, в чём проблема, и, как видно, никто не понимает...
Для поддержки бинарного дерева можно пользоваться структурой вроде следующей:
Код:
Для обхода дерева пользуемся обычными рекурсивными алгоритмами.
В чём вопрос-то?
br />
class Tree
{
private:
Tree* m_pParent; // родитель
Tree* m_pLeft; // левый ребёнок
...
В чём вопрос-то?
{
private:
Tree* m_pParent; // родитель
Tree* m_pLeft; // левый ребёнок
...
В чём вопрос-то?
Вопрос какраз в том чтоб ефективно работать с базой, т.е. выбрать всех детей, причем сохраняя структуру, кто с лева кто с права. Выбрать всех родителей и тд. Причем хотелось бы чтоб это работало быстро и эфективно. Размер базы предположительно 2-3 000 элементов, и будет расти.
Рекурсией это достаточно долго и затрачивает много ресурсов. Но спасибо за отзыв :), приятно когда люди не равнодушны.
А я кажеться решил эту проблему с помощью алгоритма Nested Sets. Как только придумаю как его написать, на С++ :) сразу поделюсь с общественностью.
Цитата:
Originally posted by xelat
Вопрос какраз в том чтоб ефективно работать с базой, т.е. выбрать всех детей, причем сохраняя структуру, кто с лева кто с права. Выбрать всех родителей и тд. Причем хотелось бы чтоб это работало быстро и эфективно. Размер базы предположительно 2-3 000 элементов, и будет расти.
Вопрос какраз в том чтоб ефективно работать с базой, т.е. выбрать всех детей, причем сохраняя структуру, кто с лева кто с права. Выбрать всех родителей и тд. Причем хотелось бы чтоб это работало быстро и эфективно. Размер базы предположительно 2-3 000 элементов, и будет расти.
Самый эффективный алгоритм этого класса, это метод LoadFromFile() компонента TTreeView Delphi/CBuilder. Чтоб посмотреть как он работает, можно создать дерево, вызвать SaveToFile() и посмотреть на созданный файл в редакторе.
Но для того, чтоб его применить нужно знать теоретическую максимальную глубину дерева. Один уровень=1 байт.
Но для того, чтоб его применить нужно знать теоретическую максимальную глубину дерева. Один уровень=1 байт. [/QUOTE]
Спасибо, попробую этот вариант. Но скорей всего не пройдет :(, так как структура всей базы представляет собой бинарное дерево. Т.е. уровень вложености будет внушительный.
Спасибо, попробую этот вариант. Но скорей всего не пройдет :(, так как структура всей базы представляет собой бинарное дерево. Т.е. уровень вложености будет внушительный.
Цитата:
Originally posted by xelat
Спасибо, попробую этот вариант. Но скорей всего не пройдет :(, так как структура всей базы представляет собой бинарное дерево. Т.е. уровень вложености будет внушительный.
Спасибо, попробую этот вариант. Но скорей всего не пройдет :(, так как структура всей базы представляет собой бинарное дерево. Т.е. уровень вложености будет внушительный.
1 байт=1 уровень это у Borland(у них количество символов TAB в начале строки задает уровень). У меня (:)) в одном байте почти 255 уровней. Если записи хранить не в текстовом файле, а в базе данных, тогда нужно 2 int полей. Первое поле: номер уровня. Второе: индекс элемента при левостороннем обходе дерева(если не ошибаюсь так называется обход при котором сперва посещаются левосторонние сыновья). И записи выбираются и записываются согласно этим двум полям.
Дерево состоящее более чем из 60000 записей загружается в VisualC CTreeCtrl менее чем за секунду.
Допустим есть массив указателей nodePtr[1024].
Сперва считается корень. Добавляется к дереву, указатель на него записывается в nodePtr[0].
При чтении следующих элементов. Например уровень текущего загружаемого элемента = 10.
Тогда добавляется запись к дереву и его родителем считается вершина, на которое указывает nodePtr[9], а сам указатель на вершину нового элемента записывается в nodePtr[10].
P.S. Для этой задачи бинарно-текстовой файл лучше подходит, чем напр. Access таблица. Сохранение элементов при реляционной базе данных может занять некоторое время.
Может кто подскажет тогда какую базу выбрать для работы. Программа пишется на С++ Builder, а вот с базой никак не могу опрделится. Народ кто работает с базами, посоветуйте какая лучьше подойдет для поставленной задачи, а именно хранение и эфективное управление иерархическими данными.
Цитата:
Originally posted by xelat
Может кто подскажет тогда какую базу выбрать для работы. Программа пишется на С++ Builder, а вот с базой никак не могу опрделится. Народ кто работает с базами, посоветуйте какая лучьше подойдет для поставленной задачи, а именно хранение и эфективное управление иерархическими данными.
Может кто подскажет тогда какую базу выбрать для работы. Программа пишется на С++ Builder, а вот с базой никак не могу опрделится. Народ кто работает с базами, посоветуйте какая лучьше подойдет для поставленной задачи, а именно хранение и эфективное управление иерархическими данными.
Бинарно-текстовой файл.
Цитата:
Originally posted by rostyslav
Бинарно-текстовой файл.
Бинарно-текстовой файл.
либо xml
Цитата:
Originally posted by rostyslav
Бинарно-текстовой файл.
Бинарно-текстовой файл.
rostyslav извени, не мог ты по подробней описать работу с этими файломи. Я навичок в этом деле и немного не понимаю что имеется ввиду. И спасибо за помощь
Цитата:
Originally posted by xelat
rostyslav извени, не мог ты по подробней описать работу с этими файломи. Я навичок в этом деле и немного не понимаю что имеется ввиду. И спасибо за помощь
rostyslav извени, не мог ты по подробней описать работу с этими файломи. Я навичок в этом деле и немного не понимаю что имеется ввиду. И спасибо за помощь
Под бин-текстовым файлом я имел ввиду нормальный файл, в которые числа записываются в 16м формате. Обычно (напр. банковские выписки) числа переводятся в строковое представление.
Нашел модуль, который писал, чтоб понять как работает Builder-овский LoadFromFile/SaveToFile. Переделал под этот пример. 10000 записей загружается около за 1 сек. (Visual C CTreeCtrl работает в несколько раз быстрее).
Те переменные, которые нужны для загрузки/сохранения и подсчета дочерных узлов, вместо h-файла находятся в начале cpp файле (чтоб легче было их найти)
Используется структура
Код:
struct Rec
{
int level;
char value[12];
};
{
int level;
char value[12];
};
Если до 10000 записей, то можно бы использовать для сохранения записей и Access или FoxPro. Думаю за 10-15 секунд ожидания user лапы не подбросит.
Но тогда нужна будет структура
Код:
struct Rec
{
int entryid; //что-то типа автоинкремента
int level;
char value[12];
};
{
int entryid; //что-то типа автоинкремента
int level;
char value[12];
};
И при сохранении сперва нужно будет удалить все записи из таблицы.