20. Древовидные структуры данных

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

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

Далее дадим определения, используемые при оперировании древовидными структурами.

Если узел y находится непосредственно под узлом х, то узел y называется непосредственным потомком узла х, а x - непосредственным предком узла у, т. е., если узел хнаходится на i-ом уровне, то соответственно узел y находится на (i + 1) - ом уровне.

Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева - его корень.

Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.

Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.

Если пройти от корня дерева к некоторому конкретному узлу, то количество ветвей дерева, которое при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.

Частным случаем древовидных структур являются бинарные деревья. Это деревья, в которых каждый потомок имеет не более двух потомков, называемых левым и правым поддеревьями. Таким образом, бинарное дерево - это древовидная структура, степень которой равна двум.

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

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

Автор: Цветкова А.В.

<< Назад: Очереди

>> Вперед: Операции над деревьями

Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:

▪ История России. Шпаргалка

▪ Уголовно-исполнительное право. Шпаргалка

▪ Экологическое право. Шпаргалка

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Лабораторная модель прогнозирования землетрясений 30.11.2025

Предсказание землетрясений остается одной из самых сложных задач геофизики. Несмотря на развитие сейсмологии, ученые все еще не могут точно определить момент начала разрушительного движения разломов. Недавние эксперименты американских исследователей открывают новые горизонты: впервые удалось наблюдать микроскопические изменения в контактной зоне разломов, которые предшествуют землетрясению. Группа под руководством Сильвена Барбота обнаружила, что "реальная площадь контакта" - участки, где поверхности разлома действительно соприкасаются - изменяется за миллисекунды до высвобождения накопленной энергии. "Мы открыли окно в сердце механики землетрясений", - отмечает Барбот. Эти изменения позволяют фиксировать этапы зарождения сейсмического события еще до появления традиционных сейсмических волн. Для наблюдений ученые использовали прозрачные акриловые материалы, через которые можно было отслеживать световые изменения в зоне контакта. В ходе искусственного моделирования примерно 30% ко ...>>

Музыка как естественный анальгетик 30.11.2025

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

Алкоголь может привести к слобоумию 29.11.2025

Проблема влияния алкоголя на стареющий мозг давно вызывает интерес как у врачей, так и у исследователей когнитивного старения. В последние годы стало очевидно, что границы "безопасного" употребления спиртного размываются, и новое крупное исследование, проведенное международной группой ученых, вновь указывает на это. Работы Оксфордского университета, выполненные совместно с исследователями из Йельского и Кембриджского университетов, показывают: даже небольшие дозы алкоголя способны ускорять когнитивный спад. Команда проанализировала данные более чем 500 тысяч участников из британского биобанка и американской Программы миллионов ветеранов. Дополнительно был выполнен метаанализ сорока пяти исследований, в общей сложности включавших сведения о 2,4 миллиона человек. Такой масштаб позволил оценить не только прямую связь между употреблением спиртного и развитием деменции, но и влияние генетической предрасположенности. Один из наиболее тревожных результатов касается людей с повышенным ге ...>>

Случайная новость из Архива 247-мегапиксельный датчик Sony IMX811 24.03.2024 Компания Sony представила новый среднеформатных датчик изображения с разрешением 247 Мп. Новинка, получившая наименование IMX811, предназначена для промышленного использования. IMX811 обладает соотношением сторон 3:2 и размерами 53,96 на 35,97 мм (диагональ - 64,84 мм, формат Type 4.1). Это CMOS-сенсор с обратной засветкой, обеспечивающий максимальное разрешение изображения 19200 на 12800 пикселей. Скорость съемки составляет 5,3 кадра в секунду при 16-битной глубине цвета или 12 кадров в секунду при 12-битной глубине цвета. Датчик изображения Sony IMX811 с разрешением 247 мегапикселей представляет собой значительный шаг вперед в мире фототехнологий. Однако его применение в потребительских камерах может стать доступным только для небольшого круга пользователей из-за высокой стоимости.

Другие интересные новости:

▪ Фотосинтетический двигатель для искусственных клеток

▪ HDD продаются все хуже

▪ Вода не менее ценна, чем нефть или газ

▪ Приемопередатчик 32 Гбит/с от Altera

▪ Образ жизни влияет на будущее потомства

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Должностные инструкции. Подборка статей

▪ статья Необходимость самовластья и прелести кнута. Крылатое выражение

▪ статья Где можно прокатиться на подземном троллейбусе? Подробный ответ

▪ статья Работа на автомате для изготовления штуковок. Типовая инструкция по охране труда

▪ статья Простой термометр для дома с двумя датчиками DS18B20. Энциклопедия радиоэлектроники и электротехники

▪ статья Применение твердотельных оптоэлектронных реле средней мощности. Энциклопедия радиоэлектроники и электротехники

Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2025