Меню
Что нового?

Постройка нового дерева из исходного

GEN2009

Новичок
Постройка нового дерева из исходного

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

-~{}~ 09.10.06 16:00:

Ок,конкретизирую вопрос как сделать запрос следущего содержания выбрать все непересекающиеся диапазоны в заданном диапазоне с максимальной длины (диапазон в базе задается начальным и конечным значениями)
 

Кром

Новичок
Непонято все равно. Не надо пытаться объяснить задачу одним сложноподчиненным выражением.
Что за дерево, откуда идет выборка, какие запросы используются?
 

GEN2009

Новичок
Дерево категорий, дак вот каждый клиент сайта может выбрать разные категории из этого дерева в совершенно произвольном порядке и мне нужно этому клиенту показать только то дерево, которое получится в результате его выбора категорий, с сохранением логической структуры(которая берется из начального дерева-пример я уже описал в начальном посте),
пока в этом начальном дереве категории хранятся как id parent_id category_name
category_level, но очевидно что такая структура для подобной задачи неудобна, поэтому я решил сделать еще таблицу в которой категории хранятся по интервальному типу
 

Кром

Новичок
Собственно говоря, если тебе нужно сохранить структуру дерева, то ты можешь использовать существующее дерево а клиенту отображать только те категории, которые он выбрал.
Т.е. когда бежишь по дереву при выводе, выводишь только те категории, которые выбрал клиент. Остальные просто не выводишь.
 

GEN2009

Новичок
Автор оригинала: Кром
Т.е. когда бежишь по дереву при выводе, выводишь только те категории, которые выбрал клиент. Остальные просто не выводишь.
Нажмите для раскрытия...
Ты не понял сложности, то что ты говоришь-это очевидно, сложно это реализовать:
у меня есть корневая категория, в ней категории первого уровня, в каждой из них второго, в тех третьего и т.д.
допустим если у меня есть категории первого уровня: "автомобили", "компьютеры", "самолеты"
в автомобилях у меня "наши" и "не наши" в "наши": "ВАЗ","ГАЗ",в "ГАЗ": "Газели" В "компьютерах" у меня "сист блоки", "мониторы", "Комплектующие" в "Комплектующих": "процы", "материнки","память" дак вот допустим человек отметил себе категории: "наши", "самолеты", "Газели", "Мониторы", "память","материнки"
дак вот как должно выглядеть дерево после такого выбора: Первый уровень: "наши", "самолеты","Мониторы", "память","материнки" Второго уровня в "наши": "Газели" т.е. пропущенные категории не считаются, но логическая связь сохраняется.
 

Кром

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

GEN2009

Новичок
Автор оригинала: Кром
Я тебе уже написал как это реализовать. Путем прохода по существующему дереву и выборке только тех узлов, которые выбрал пользователь. Т.е. сначал ты проходишь по ветке автомобили. До того уровня глубины, пока не находишь первый отмеченный узел. Выбираешь его, ставишь на первый уровень и бежишь дальше. И все остальные выводишь по такому же принципу.
Нажмите для раскрытия...
это общие слова, ты думаешь что этого я не понимаю!?
Как ты себе представляешь бежать? по каждому уровню выполнять запрос для данного id если такого не находим то для каждого id этого уровния проводить этот запрос и тд, тогда кол-во запросов от уровня возрастает как степень от уровня(в среднем), ты представляешь как медленно будет работать такой алгоритм на 10 м уровне даже при 100 клиентах!?
я же пишу, что мне нужны КОНКРЕТНЫЕ советы по реализации этого алгоритма, и видимо по оптимальному способу хранения дерева для этого алгоритма..
 

ru_skol

Новичок
Ну ты же сам хотел перейти на множества, в этом случае все элементарно - просто выбирай из базы отмеченные, в нужное дерево оно построится точно так-же как и полное
 

GEN2009

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

ru_skol

Новичок
Автор оригинала: GEN2009
Да но тогда я не знаю как сделать следущее "выбрать все непересекающиеся диапазоны в заданном диапазоне с максимальной длиной (диапазон в базе задается начальным и конечным значениями) "
Нажмите для раскрытия...
ты хоть сам понял что сказал? причем здесь максимальная длина и непересекающиеся?
 

GEN2009

Новичок
это вы чего-то не понимаете..

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

ru_skol

Новичок
Автор оригинала: GEN2009
это вы чего-то не понимаете..

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

автомобили->колеса->камеры и колеса пропущены в выборе, тогрда предком "камер" становятся "автомобили"
Нажмите для раскрытия...
то что вам нужно даст тривиальный

select id, first_child, last_child, caption from tree where id in ( список выбранных id )

собрать полученные данные в дерево проще простого
 

GEN2009

Новичок
в чем логика!? причем здесь "ORDER BY id" ? что такое first_child и last_child????

-~{}~ 11.10.06 23:01:

"собрать полученные данные в дерево проще простого" - как вы это себе представляете интересно!?
 

ru_skol

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

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

по поводу вывода такого дерева: все решается рекурсивной процедурой, пробегающейся по набору... типа такого:
PHP: 
function show_tree(&items, $pos = 0, $limit = 0) {
  if (!$limit) $limit = count($items) - 1;
  $item = $items[$pos];
  level_start(); // echo "<div style='padding-left:20px;'>";
  while ($item && $item['id'] <= $limit) {
        show_item($item); // echo $item['caption'];
        $pos++;
        $pos = show_tree($items,$pos,$item['last_child']);
        $item = $items[$pos];
  }
  level_close(); // echo "</div>";
  return $pos;
}
 

GEN2009

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

ru_skol

Новичок
Автор оригинала: GEN2009
предположим я имею:
автомобили->колеса->камеры->финские, "колеса" пропущены в выборе, тогрда предком "камер" становятся "автомобили", но "финские"-предок "камер", и их выбирать пока не надо, т.к. имеется выбранный более универсальный предок, ваш запрос это разве учитывает?(если сестно не понял его логики, особенно с сортировкой. Зачем выбирать все выбранные айди и смотреть для каждого начальное и конечное значение отрезка??? )
Нажмите для раскрытия...
Что значит более универсальный предок?? Тогда самый универсальный это "автомобили".
давайте объяснятся на пальцах: :)

то о чем я говорю даст:
(звездочками отмечены выбранные)


автомобили*->колеса->камеры*->финские* => автомобили*->камеры*->финские*

автомобили*->колеса->камеры->финские* => автомобили*->финские*

автомобили*->колеса->камеры*->финские => автомобили*->камеры*

автомобили->колеса*->камеры->финские* => колеса*->финские*
 

GEN2009

Новичок
тогда немного перефразирую задачу:
автомобили*->колеса->камеры*->финские*
автомобили*->кузова->новые->красные*
автомобили*->рули*->новые->финские*
хочу получить всех выбранных ближайших предков для автромобилей, т.е. будут только камеры* красные* рули*
 

ru_skol

Новичок
Автор оригинала: GEN2009
тогда немного перефразирую задачу:
автомобили*->колеса->камеры*->финские*
автомобили*->кузова->новые->красные*
автомобили*->рули*->новые->финские*
хочу получить всех выбранных ближайших предков потомков для автромобилей, т.е. будут только камеры* красные* рули*
Нажмите для раскрытия...
еще раз перефразируем и получаем

select max(id) where id < MY_ID and last_child >= MY_ID and id in (...... список ......) - ближайший выбранный предок
или
select count(*) where id < MY_ID and last_child >= MY_ID and id in (...... список ......) - уровень узла в новой иерархии


используя любой из этих запросов как подзапрос для первого можете получить что вам надо
 
Войдите или зарегистрируйтесь для ответа.
Сверху