Способ заполнения N-дерева

[FasterHarder]

Всем хай! Сходу к делу, не теряя ни секундочки драгоценного времени)

Дано некоторое N-дерево. Надо придумать алгоритм его заполнения) Все, вот такое задание.
Вот на самом деле это оказалось для меня не так просто, как я предполагал изначально. С бинарками поиска все четко: либо влево, либо вправо. Здесь непонятки.

Во-первых: нужно выбрать тип данных ключа. Допустим берем целые числа.
Во-вторых: диапазон чисел. Ну, пусть от 1 до 100.
В-третьих: что делать с дубликатами? Допустим, их нужно добавлять куда-то.
В-четвертых: какую взять размерность N? 3, 4, а может 9???
В-пятых: немного подумав (может нужно было подольше) осознал, что не "вижу" четкого алгоритма заполнения такого дерева целыми числами. Вот по какому признаку их распределять по дереву?? Было много идей, но понял, что они строят какие-то все вырожденные деревья) А хочется получать некую сбалансированность, а не вырождение в ЛОС.

Подскажите как быть то??? Как бы вы заполняли ЭН-дерево???
--------------------------------------
была у меня еще идея добавлять узлы РАНДОМНО!! Ну, например, если N = 5 (каждый узел имеет не больше 5 подузлов), то бросаем "кубик" от 1 до 6 и в зависимости от этого направляем движение алгоритма. Тупо, конечно, но ничего др. я не вижу) + в этом случае ПОИСК становится полным перебором)

Сообщение отредактировано: FasterHarder - 05.12.20, 14:27

[AVA12]

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

Если хочется поиграться с сильно ветвящимися деревьями поиска, то B-дерево (B-tree) отлично подойдет.

[FasterHarder]

Цитата AVA12 @ 05.12.20, 16:36

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

но-но, с как обычно вы погорячились. я могу привести свыше, наверное, 100 задач, где оч.четкая постановка...
и в этой задаче тоже все предельно точно сказано

вот ты говоришь, что получить, непонятно, а вот для кого я писал это: "Надо придумать алгоритм его заполнения". Другой момент, а какие будут дальше операции над данными в дереве. Ответ: никаких!

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

[Qraizer]

Цитата FasterHarder @ 05.12.20, 14:22

Вот на самом деле это оказалось для меня не так просто, как я предполагал изначально. С бинарками поиска все четко: либо влево, либо вправо. Здесь непонятки.

Что-то я не пойму. Ну вот у тебя есть понятка, как заполнять бинарное дерево. Либо в влево, либо вправо. Но ведь этого же мало, нужен ещё критерий отбора направления. Это же понятно, проблем нет? Судя по цитате, нет, но тогда откуда непонятка, что делать с N-деревом. Тоже как-то критерий, только выход у него не бинарный, а... ну, пусть будет целый. В каком-то там диапазоне.

[Akina]

Цитата FasterHarder @ 05.12.20, 17:00

Другой момент, а какие будут дальше операции над данными в дереве. Ответ: никаких!

Можно, я не поверю? и даже процитирую одного нашего общего знакомого:

Цитата FasterHarder @ 05.12.20, 14:22

в этом случае ПОИСК становится полным перебором

То есть как минимум поиск по этой фигне, после построения/заполнения, таки будет.

[FasterHarder]

Qraizer, у этого эн-дерева много левых и правых)
ну, например эн = 5: 2 левых, 2 правых и 1 центральный. Центр можно оставить для дубликата, к примеру. Если подается значение меньше ключа, то совать нужно влево (там 2 варианта), по возрастанию придется все это рассчитывать. А если ЭН = 6, то центра уже нет. Кстати про карманное разбиение думал, но чего-то там все как-то не стыкуется), а может просто плохо думал)

Вот даже пример, N = 3. И подается 2 числа: 37 и 50. 37 - корень. А 50 куда ставить. Оно больше 37, т е должно идти вправо. Т е как бы в потомок под №3. Или все-таки №2.

Akina), про поиск я просто так написал, эта операция не нужна. Если что, мне нужно будет там для каждого узла посчитать кол-во детей, но эта операция от конфигурации дерева НЕ зависит, поэтому даже не упоминал ее

Добавлено 05.12.20, 18:40
кстати, я только сейчас подумал, а случаем эти N-деревья не являются поисковыми)
я вот пытаюсь пробить через гугл и 1ая выдача мое сообщение на этом форуме несколько лет назад, лол

если N-деревья поисковые по дефалту, то рандом явно не подходит

Добавлено 05.12.20, 19:11
мне тут дали ссылочку познакомиться с деревьями, какие-то m-ary, так там вообще упорядоченность поуровневая идет, да уж, это ведь в корне меняет все! И почему называется M, а в условии N-дерево. Ладно, не все так просто как обычно)

Сообщение отредактировано: FasterHarder - 05.12.20, 19:11

[amk]

У этого дерева 1 левое, 1 правое и между ними несколько промежуточных.
В бинарном дереве ключ в узле оразделяет значения левого и правого поддеревьев.
В аналогичном N-дереве (N-1) ключей разделяют значения поддеревьев.
поддерево_1 < ключ_1 < поддерево_2 < ключ_2 < поддерево_3 < ключ_3 < поддерево_4
То есть все ключи поддерева 1 меньше ключа 1, все ключи поддерева 2 больше ключа 1 и меньше ключа 2 и т.д.

В твоём случае (родители-дети) обычно используется другая структура - для каждого родителя заводится список детей (список в значении перечень, а не структура данных, можно использовать вектор C++), никаких ключей не используется.

[FasterHarder]

amk, N-дерево в русскоязычной теории и m-ary_tree в англ. - это аналоги??