Структура представления данных, где у родителя могут существовать более двух потомков

@yol · Регистрация: 13.10.2012

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

Как представить структуру в виде двоичного дерева, где у родителя могут существовать больше двух потомков.
Необходимо подобрать подходящую структуру, где затраты на поиск (и фильтрацию) будут минимальными. Поэтому принимаются другие структуры представления данных.

@ZaMaZaN4iK · 19.09.2014, 23:42

yol, извините конечно, но двоичное дерево подразумевает под собой именно ДВа потомка. Можете к вершинам прикрутить и больше потомков - кто мешает то?

Просто продумайте правила, по каким вы будете делить своё древо на 3 и более потомков. Есть к примеру квадродерево, link-cut деревья(динамические деревья Слетора-Тарьяна вроде). Почитайте.

Ну а как организовать больше двух сыновей, то это очень просто: в каждой вершине храните ссылки на сыновей и всё

@yol · 19.09.2014, 23:56 **[ТС]**

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

Ну а как организовать больше двух сыновей, то это очень просто: в каждой вершине храните ссылки на сыновей и всё

Да, но я сомневаюсь в эффективности такой структуры при поиске, вставке и прочих операциях.
В принципе, я уже нашел более-менее подходящий вариант: b-tree.

@ZaMaZaN4iK · 20.09.2014, 11:23

yol, почитайте, что оптимальная структура достигается именно за счёт двух сыновей - так отлично достигается логарифм в операциях. А насчёт вашего b-дерева - заметьте, что оно оптимизирует не асимптотику, а записи на жесткие диски, то есть оно минимизирует их за счёт немного худшей сложности.

Новые блоги и статьи Все статьи Все блоги /
Гайд по современным СУБД (небесспорный) Codd 26.06.2025 Когда я только начинал свой путь в IT как рядовой программист, база данных казалась мне чем-то простым и понятным. Ну, серьезно — это же просто место, где лежат данные, верно? Напиши SELECT * FROM. . .	Использование C# с AWS S3: Примеры с AWS SDK для .NET stackOverflow 26.06.2025 Amazon S3 (Simple Storage Service) уже давно стал стандартом де-факто в мире облачного хранения данных. Особенно приятно, что для разработчиков . NET предусмотрен отличный SDK, который значительно. . .	Веб-автоматизация с Python и Selenium AI_Generated 25.06.2025 Selenium с Python — это комбинация, которая выдержала проверку временем. Несмотря на появление новых инструментов вроде Playwright или Puppeteer, связка Python-Selenium остаётся золотым стандартом. . .	CQRS и Event Sourcing на C# ArchitectMsa 25.06.2025 За последние несколько лет сложность корпоративных приложений выросла в геометрической прогрессии. Простые монолитные системы уступили место распределенным микросервисам, а нагрузка на корпоративные. . .	Хак домофона или как открыть дверь по номеру yariko 25.06.2025 Забыли дома ключ. Не проблема. Можно открыть дверь домофона, просто позвонив на свой номер квартиры. Идея состоит в следующем. Внутрь трубки абонента встраивается контроллер, который по звонку сам. . .
Как украсить новогоднюю елку с Q# и Qiskit EggHead 24.06.2025 Что может быть необычнее, чем применить законы квантовой механики для украшения новогодней елки? Пока другие развешивают обычные гирлянды, я решил объединить свою страсть к квантовым вычислениям с. . .	Системы нулевого доверия на C# UnmanagedCoder 24.06.2025 Традиционная архитектура безопасности работает по принципу средневекового замка: создаём высокие стены вокруг корпоративной сети, укрепляем ворота межсетевыми экранами и системами обнаружения. . .	Снова не мой путь. Циклическое среднее, я обеими руками за проверку условия, в ракурсе данной задачи - циклическое среднее в топку. Hrethgir 24.06.2025 Привет. Такой вопрос - нужно выводить среднее математическое между двумя направлениями, интервал значений которых может лежать в диапазоне одного оборота по кругу. Проблема заключается в том, что. . .	Деплой Flask приложения py-thonny 23.06.2025 За годы работы с Flask я натыкался на одни и те же грабли достаточно часто, чтобы наконец научится их обходить. И сегодня хочу поделится опытом, который сбережет вам немало нервных клеток. Начнем с. . .	WebAssembly и контейнеры в .NET Aspire для оркестрации распределенных архитектур ArchitectMsa 23.06.2025 Я наблюдаю, как WebAssembly (или просто WASM) постепенно выходит за рамки своего первоначального предназначения — исполнения кода на стороне браузера. Теперь эта технология проникает в серверную. . .

@yol 11 / 11 / 0 Регистрация: 13.10.2012 Сообщений: 163

	Структура представления данных, где у родителя могут существовать более двух потомков 17.09.2014, 19:22. Показов 858. Ответов 3 Метки нет (Все метки) Как представить структуру в виде двоичного дерева, где у родителя могут существовать больше двух потомков. Необходимо подобрать подходящую структуру, где затраты на поиск (и фильтрацию) будут минимальными. Поэтому принимаются другие структуры представления данных. 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	19.09.2014, 23:42
	yol, извините конечно, но двоичное дерево подразумевает под собой именно ДВа потомка. Можете к вершинам прикрутить и больше потомков - кто мешает то? Просто продумайте правила, по каким вы будете делить своё древо на 3 и более потомков. Есть к примеру квадродерево, link-cut деревья(динамические деревья Слетора-Тарьяна вроде). Почитайте. Ну а как организовать больше двух сыновей, то это очень просто: в каждой вершине храните ссылки на сыновей и всё 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	20.09.2014, 11:23
	yol, почитайте, что оптимальная структура достигается именно за счёт двух сыновей - так отлично достигается логарифм в операциях. А насчёт вашего b-дерева - заметьте, что оно оптимизирует не асимптотику, а записи на жесткие диски, то есть оно минимизирует их за счёт немного худшей сложности. 0