Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

PostgreSQL

Войти
Регистрация
Восстановить пароль
 
Уф
339 / 330 / 144
Регистрация: 13.07.2015
Сообщений: 1,097
Завершенные тесты: 1
#1

Сортировка хитрого дерева - PostgreSQL

24.11.2016, 13:30. Просмотров 300. Ответов 5
Метки нет (Все метки)

Есть табличка
Oracle 11 SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE TABLE test
(
  KEY INTEGER NOT NULL,
  data text,
  ord INTEGER,
  CONSTRAINT test_pk PRIMARY KEY (KEY)
);
INSERT INTO test(KEY,data,ord)
VALUES  ('0','1','0'),
    ('1','1.1','1'),
    ('2','1.2','2'),
    ('3','1.1.1','2'),
    ('4','1.3','4'),
    ('5','1.2.1','3'),
    ('6','1.2.2','4')
В ней первое это ключ, второе иерархия(для наглядности, на самом деле там другие данные, а её нет), третье это на сколько выше надо подняться чтобы найти родителя по ключу( то есть из собственного key отнимаем ord, получаем ключ родителя.
Задачка вывести данные в правильном порядке.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.11.2016, 13:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка хитрого дерева (PostgreSQL):

Создание хитрого Масива - C++
Ну в общем надо вычислить сумму и кол-во элементов масива по модулю не превышающих 8 и парных, если размер масива 3х4. ( пжалста решите...

Есть ли на хитрого пользователя таймер с винтом? - Assembler
Доброго дня! Если верить народной мудрости, то на каждую заднюю часть с хитринкой есть передняя часть с винтом. Вот именно такую часть с...

Как сделать отчет хитрого вида (+) - MS Access
Вид такой: 01.01.2004 02.01.2004 ... Далее неделя 1 (03.04 .. 07.04) User1 x x x x x x User2 x x x x ...

Формирование хитрого отчета (подскажите новичку) - MS Access
Добрый день. Подскажите как сформировать хитрый отчет. Внешний вид отчета: Менеджер: Иванов Петров Сидоров ...

Операции над бинарными деревьями: построение дерева, обход дерева, вставка и удаление элемента дерева - Pascal
Пожалуйста кто сможет, помогите составить программу: Организация по трудоустройству населения сохраняет резюме клиентов в виде бинарного...

Сортировка Двоичного дерева - Pascal ABC
Всем добрый день , может кто нибудь пожалуйста помочь. Выполнить сортировку дерева в прямом порядке (Двоичное дерево).

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
grgdvo
558 / 494 / 140
Регистрация: 02.09.2012
Сообщений: 1,443
24.11.2016, 16:13 #2
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
WITH RECURSIVE "SrcData"("Key", "Data", "Ord") AS (
VALUES  
    (0,'1',0),
    (1,'1.1',1),
    (2,'1.2',2),
    (3,'1.1.1',2),
    (4,'1.3',4),
    (5,'1.2.1',3),
    (6,'1.2.2',4)
), "Obhod" ("Key", "Data", "Ord", "Level") AS (
    SELECT "Key", "Data", "Ord", 0 FROM "SrcData" WHERE "Key"=0
  UNION ALL
    SELECT sd."Key", sd."Data", sd."Ord", o."Level" + 1 FROM "Obhod" AS o, "SrcData" AS sd 
      WHERE sd."Key" <> 0 AND o."Key" = sd."Key" - sd."Ord"
)
SELECT o."Key", o."Data", o."Ord" FROM "Obhod" AS o
ORDER BY o."Level", o."Ord"
обход дерева в ширину получился, это правильный порядок??
для деревьев еще существует обход в глубину, но я сейчас не готов его воспроизвести,
думать надо над правильной сортировкой,
рекурсивный CTE для этого не совсем подходит, так чтобы сходу написать.
0
Уф
339 / 330 / 144
Регистрация: 13.07.2015
Сообщений: 1,097
Завершенные тесты: 1
24.11.2016, 16:44  [ТС] #3
интересный метод, но порядок не верный. надо чтобы было
Код
0;"1";0
1;"1.1";1
3;"1.1.1";2
2;"1.2";2
5;"1.2.1";3
6;"1.2.2";4
4;"1.3";4
узлы которые оказались равнозначными потомками сортируем просто по ключу( т.е. порядку добавления в базу)
А если знаешь что у дерева всегда не больше трех уровней это упрощает задачу?
0
grgdvo
558 / 494 / 140
Регистрация: 02.09.2012
Сообщений: 1,443
25.11.2016, 14:35 #4
Вроде так должно работать. Есть, правда, слабое место в порядке сортировки sd."Key", которое может не сработать, если
меньший по порядковому номера узел дерева, будет с большим идентификатором ключа. Тогда будет неверный порядок.

SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
WITH RECURSIVE "SrcData"("Key", "Data", "Ord") AS (
VALUES  
    (0,'1',0),
    (1,'1.1',1),
    (2,'1.2',2),
    (3,'1.1.1',2),
    (4,'1.3',4),
    (5,'1.2.1',3),
    (6,'1.2.2',4),
    (7,'1.1.2',6),
    (8,'1.3.1',4)
), "Obhod" ("Key", "Data", "Ord", "Level", "NodeId") AS (
    SELECT "Key", "Data", "Ord", 0, '{1}'::INT[] FROM "SrcData" WHERE "Key"=0
  UNION ALL
    SELECT sd."Key", sd."Data", sd."Ord", o."Level" + 1, o."NodeId" || (ROW_NUMBER() OVER (PARTITION BY o."Key" ORDER BY sd."Key"))::INT FROM "Obhod" AS o, "SrcData" AS sd 
      WHERE sd."Key" <> 0 AND o."Key" = sd."Key" - sd."Ord"
)
SELECT o."Key", o."Data", o."Ord" FROM "Obhod" AS o
ORDER BY o."NodeId";
0
Уф
339 / 330 / 144
Регистрация: 13.07.2015
Сообщений: 1,097
Завершенные тесты: 1
25.11.2016, 15:58  [ТС] #5
Работает, только обязательно в 13 строке надо указывать первый элемент? а то у меня несколько деревьев в таблице и у них первый элемент с Ord 0, получится ли их вывести друг за другом?
0
grgdvo
558 / 494 / 140
Регистрация: 02.09.2012
Сообщений: 1,443
26.11.2016, 00:21 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Уф Посмотреть сообщение
обязательно в 13 строке надо указывать первый элемент?
Обязательно. Запрос рекурсивный, с 13 строки все начинает раскручиваться.
Перепишите его так под ваши данные, чтобы выбиралось сразу несколько корней с проставлением нумерации через ROW_NUMBER, то есть, чтобы NodeId было массивом с одним элементов {1}, {2} ....
Остальная часть запроса должна сработать как есть.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2016, 00:21
Привет! Вот еще темы с ответами:

1C 8.x Сортировка дерева значений - 1С
В регистре сведений есть дерево значений с колонками: наименование и код. При открытии формы, дерево сортируется по наименованию, а мне...

Сортировка бинарного дерева - Delphi
Помогите, пожалуйста, с задачей. Создать сбалансированное бинарное дерево. Разработать процедуру сортировки пузырьком элементов дерева. ...

Сортировка методом бинарного дерева - VBA
Простенькая сортировка методом бинарного дерева: Private Sub CommandButton1_Click() Dim arr() As Variant, dr() As Variant, vix() As...

Сортировка массива с помощью дерева - Visual Basic
Помогите сделать лабу. Сортировка массива с помощью дерева Цель выполнения заданий: освоение алгоритмов и методов построения...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.11.2016, 00:21
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru