درخت ریشهدار
پرش به ناوبری
پرش به جستجو
در نظریهٔ گراف، یک درخت ریشهدار الگو:انگلیسی به درختی گفته میشود که یک رأس در آن به عنوان ریشه برچسب خورده باشد. درخت ریشهدار یک ساختار داده کلیدی در علوم کامپیوتر است.
رأسهایی که به طور مستقیم به رأس دیگری متصل اند بچههای آن نامیده میشوند. مثلاً در شکل بالا و بچههای هستند و پدر آنهاست. همچنین اگر یک رأس بچهای نداشته باشند به آن برگ میگویند.(مانند گره )
چند نمونه از درخت ریشهدار: درخت جستجوی دودویی، درخت قرمز و سیاه، درخت مبنایی
تعداد درختهای ریشه دار با رأس بر اساس دنباله روبرو است: ۱, ۱, ۲, ۴, ۹, ۲۰, ۴۸, ۱۱۵, ۲۸۶, ۷۱۹, ۱۸۴۲, ۴۷۶۶,...[۱]
مثالهایی از استعمال
فایل سیستمها درختهای ریشه دار هستند. برای نمونه درایو در کامپیوتر یک ریشه است. در این درخت ریشه دار فایلها و پوشهها رأسها هستند. این رأسها توسط لینکهایی در هارد مشخص میشوند.