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

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

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

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

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

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