Построить N-арное дерево: не могу понять принцип размещения элементов

@Sergey0088 · Регистрация: 02.09.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте, нужно построить n-арное дерево. Алгоритм постоени бинарного мне полностью понятен, но тут не могу сообразить принцип размещения элементов. Гугл не помог. Буду очень признателен за ссылочку, название литературы или краткое изложение принципа на словах.

IGPIGP · 07.09.2016, 21:46

Сообщение от Sergey0088

Алгоритм постоения бинарного мне полностью понятен, но тут не могу сообразить принцип размещения элементов.

Неустранимое противоречие в данной фразе не даёт уразуметь вопрос. Давайте, излагая алгоритм подойдём к месту, где построение конфликтует с концепцией размещения, может?

@_Ivana · 07.09.2016, 22:06

А чем 2 принципиально отличается от другого числа, больше го единицы?

@Sergey0088 · 07.09.2016, 22:06 **[ТС]**

В бинарном, если элемент больше — он отправляется в одну сторону, иначе — в другую. Как быть тут, на основании чего элемент размещать в дереве? Понятно, что всесто двух указателей, будет массив указателей, но всё-равно не ясень принцип размещения нового элемента)

@_Ivana · 07.09.2016, 22:10

Сообщение от Sergey0088

В бинарном, если элемент больше — он отправляется в одну сторону, иначе — в другую

Вигвам, как говорится. Это в сбалансированном бинарном так.

@Sergey0088 · 07.09.2016, 22:14 **[ТС]**

То есть, поиск в n-арном в любом случае будет медленнее или я чего то не так понял?

@_Ivana · 07.09.2016, 22:19

Какой поиск? Там могут лежать элементы, которые даже сравнение на равенство не поддерживают, не то что на больше меньше

@Sergey0088 · 07.09.2016, 22:28 **[ТС]**

Какой в нём тогда вообще смысл?)

IGPIGP · 07.09.2016, 22:37

Сообщение от Sergey0088

Какой в нём тогда вообще смысл?)

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

@_Ivana · 07.09.2016, 22:41

Сообщение от Sergey0088

Какой в нём тогда вообще смысл?)

Как, вы разве не знаете про древовидную иерархическую структуру объектов с паритетными связями?

@gazlan · 07.09.2016, 23:23

Сообщение от _Ivana

Как, вы разве не знаете про древовидную иерархическую структуру объектов с паритетными связями?

Не по теме:

:-)

@Sergey0088 · 08.09.2016, 00:49 **[ТС]**

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

IGPIGP · 08.09.2016, 09:24

Сообщение от Sergey0088

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

Не должен. Но может. Ориентированное, сбалансированное дерево содержит упорядоченные уровни. N в данном контексте ограничивает размер уровня. Строится оно как и двоичное ориентированное. Если сравнивать с построением упорядоченного списка, то это похоже на пасьянс, который складывает престарелый, склеротичный граф. То есть граф с рекурсивно зацикленным поведением. Там где нужно бы вставить карту B между картами A и С он забудется опустится по A на уровень ниже. И так пока карты не закончатся. Ищет потом также. Причём быстрее, чем в линейном, сортированном, списке. Вот что значит правильная ориентация.

@Sergey0088 · 08.09.2016, 19:26 **[ТС]**

Интересно, нужно попробовать построить такое) Не посоветуете, где про это можно поподробнее почитать?
Но основный принцип, я вроде уловил: если мы находимся на определённом уровне, мы сначала смотрим, есть ли возможность для вставки на этом уровне (если реально количество потомком меньше N), если же её нет, то ищем самый близкий элемент по знчению к вставляемому и опускаемся от него на уровень ниже. А сами элементы на уровне храним в упорядоченном состоянии

IGPIGP · 08.09.2016, 22:21

Сообщение от Sergey0088

Не посоветуете, где про это можно поподробнее почитать?

Я бы и сам почитал, если честно. Только боюсь, самое сложное в таких вещах, как и в случае с бинарным деревом, это балансировка. И почему-то кажется, что балансировать такое дерево ещё труднее. Надо у _Ivana, спросить. Он знает.

@gazlan · 09.09.2016, 04:02

Угу. Multiway Trees. Часто используемая структура - B-tree

Немного по теме есть у Роберт Седжевик "Алгоритмы на С++: анализ структуры данных, сортировка, поиск, алгоритмы на графах".

У Jan Jannink была в свое время статья (и крайне глючная имплементация) B++Tree, ссылка сдохла, но есть нечто сходное: STX B+ Tree C++ Template Classes

@Sergey0088 · 09.09.2016, 16:56 **[ТС]**

Благодарю)

@Сруль · 04.12.2016, 18:59

Если вас интересует тема дерева,
то посетите, пожалуйста мой блог
http://srulbond.blogspot.co.il
там есть некоторые разъяснения и ссылка на скачивание готовой программы.
Бесплатной.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22

	Построить N-арное дерево: не могу понять принцип размещения элементов 07.09.2016, 21:16. Показов 4778. Ответов 17 Метки нет (Все метки) Здравствуйте, нужно построить n-арное дерево. Алгоритм постоени бинарного мне полностью понятен, но тут не могу сообразить принцип размещения элементов. Гугл не помог. Буду очень признателен за ссылочку, название литературы или краткое изложение принципа на словах. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	07.09.2016, 22:06
	А чем 2 принципиально отличается от другого числа, больше го единицы? 0

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	07.09.2016, 22:06 [ТС]
	В бинарном, если элемент больше — он отправляется в одну сторону, иначе — в другую. Как быть тут, на основании чего элемент размещать в дереве? Понятно, что всесто двух указателей, будет массив указателей, но всё-равно не ясень принцип размещения нового элемента) 0

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	07.09.2016, 22:14 [ТС]
	То есть, поиск в n-арном в любом случае будет медленнее или я чего то не так понял? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	07.09.2016, 22:19
	Какой поиск? Там могут лежать элементы, которые даже сравнение на равенство не поддерживают, не то что на больше меньше 1

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	07.09.2016, 22:28 [ТС]
	Какой в нём тогда вообще смысл?) 0

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	08.09.2016, 00:49 [ТС]
	Спасибо, я то думал, что там должен быть какой-то сложный алгоритм вставки и последующего быстрого поиска) 0

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	08.09.2016, 19:26 [ТС]
	Интересно, нужно попробовать построить такое) Не посоветуете, где про это можно поподробнее почитать? Но основный принцип, я вроде уловил: если мы находимся на определённом уровне, мы сначала смотрим, есть ли возможность для вставки на этом уровне (если реально количество потомком меньше N), если же её нет, то ищем самый близкий элемент по знчению к вставляемому и опускаемся от него на уровень ниже. А сами элементы на уровне храним в упорядоченном состоянии 0

@Sergey0088 0 / 0 / 0 Регистрация: 02.09.2016 Сообщений: 22
	09.09.2016, 16:56 [ТС]
	Благодарю) 0

@Сруль 0 / 0 / 0 Регистрация: 04.12.2016 Сообщений: 8
	04.12.2016, 18:59
	Если вас интересует тема дерева, то посетите, пожалуйста мой блог http://srulbond.blogspot.co.il там есть некоторые разъяснения и ссылка на скачивание готовой программы. Бесплатной. 0