درخت ریشه‌دار

در نظریهٔ گراف، یک درخت ریشه‌دار (به انگلیسی: rooted tree) به درختی گفته می‌شود که یک رأس در آن به عنوان ریشه برچسب خورده باشد. درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است.

نمونه‌ای از یک درخت ریشه‌دار

رأس‌هایی که به طور مستقیم به رأس دیگری متصل اند بچه‌های آن نامیده می‌شوند. مثلاً در شکل بالا ${\displaystyle E}$ و ${\displaystyle H}$ بچه‌های ${\displaystyle B}$ هستند و ${\displaystyle B}$ پدر آنهاست. همچنین اگر یک رأس بچه‌ای نداشته باشند به آن برگ می‌گویند.(مانند گره ${\displaystyle G}$ )

چند نمونه از درخت ریشه‌دار: درخت جستجوی دودویی، درخت قرمز و سیاه، درخت مبنایی

تعداد درخت‌های ریشه دار با ${\displaystyle n}$ رأس بر اساس دنباله روبرو است: ۱, ۱, ۲, ۴, ۹, ۲۰, ۴۸, ۱۱۵, ۲۸۶, ۷۱۹, ۱۸۴۲, ۴۷۶۶,...^[1]

مثال‌هایی از استعمال

فایل سیستم‌ها درخت‌های ریشه دار هستند

فایل سیستم‌ها درخت‌های ریشه دار هستند. برای نمونه درایو شکست در تجزیه (پاسخ نامعتبر MathML همراه SVG یا PNG جایگزین (توصیه شده برای مرورگرهای مدرن و ابزارهای کمکی) ("Math extension cannot connect to Restbase.") از سرور "http://localhost:6011/fa.wikipedia.org/v1/":): {\displaystyle C } در کامپیوتر یک ریشه است. در این درخت ریشه دار فایل‌ها و پوشه‌ها رأس‌ها هستند. این رأس‌ها توسط لینک‌هایی در هارد مشخص می‌شوند.

پانویس

1. Weisstein, Eric W. "Rooted Tree". mathworld.wolfram.com (به انگلیسی). Retrieved 2023-12-16.

پیوند به بیرون

• www.cs.nott.ac.uk