Поддерево

• Узел — элемент дерева, который может иметь родительский узел и узлы-потомки.
• Корневой узел — узел без родительского узла, являющийся началом дерева.
• Потомки узла — узлы, непосредственно связанные с данным узлом как с родительским.
• Поддерево — дерево, состоящее из узла и всех его потомков.

• Каждый узел в дереве является корнем собственного поддерева.
• Поддерево связано с остальным деревом через свой корневой узел.
• Поддеревья не перекрываются, если они имеют общие узлы.

Рассмотрим древообразную структуру:

В этом дереве, если выбрать узел B, то поддеревом будет узел B вместе со всеми его потомками, например узлами D и E.

• В алгоритмах обработки деревьев поддеревья используются для рекурсивного обхода и манипуляции данными.
• Поддеревья позволяют эффективно выполнять операции поиска, вставки и удаления узлов.
• В анализе данных поддеревья помогают разбивать сложные структуры на более простые для удобства обработки.

• Размер поддерева с корнем в узле n: ${\displaystyle size(n)}$ — количество узлов в поддереве.
• Глубина узла в поддереве: ${\displaystyle depth(n)}$ — количество ребер от корня поддерева до узла n.

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