درخت (Tree)
مفهوم درخت: ریشه، گره، برگ، ارتفاع و عمق؛ اصطلاحات کلیدی و کاربردهای واقعی درخت در نرم‌افزار
درخت چیست؟
درخت (Tree) ساختاری سلسله‌مراتبی (غیرخطی) است: یک ریشه (root) در بالا و گره‌های فرزند زیر آن. مهم‌ترین ویژگی: اتصالات بدون دور — بین هر دو گره دقیقاً یک مسیر وجود دارد.
اصطلاحات کلیدی
| اصطلاح | معنا |
|---|---|
| ریشه (Root) | گره بالای درخت — بدون والد |
| گره داخلی (Internal) | گره‌ای که حداقل یک فرزند دارد |
| برگ (Leaf) | گره بدون فرزند |
| والد/فرزند (Parent/Child) | رابطه مستقیم بالا-پایین |
| عمق (Depth) | فاصله گره تا ریشه |
| ارتفاع (Height) | بیشترین عمق درخت (فاصله ریشه تا دورترین برگ) |
| زیردرخت (Subtree) | هر گره با تمام فرزندانش، خودش یک درخت است |
مثال ملموس: ساختار پوشه‌ها
ساختار پوشه‌های کامپیوتر دقیقاً یک درخت است: درایو C ریشه، پوشه‌ها گره‌های داخلی و فایل‌ها برگ‌ها. DOM صفحات وب (تگ‌های HTML) هم درخت است!
کاربردهای واقعی درخت
- سیستم فایل: پوشه‌ها و فایل‌ها
- DOM صفحات وب: تگ‌های HTML درخت‌اند!
- پایگاه داده: ایندکس‌های B-Tree
- کامپایلر: درخت نحو انتزاعی (AST)
- هوش مصنوعی: درخت تصمیم و بازی‌ها
- فشرده‌سازی: کد هافمن
نمایش درخت در کد
رایج‌ترین روش، کلاس گره با لیست فرزندان:
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []برای درخت دودویی (حداکثر ۲ فرزند) از left و right صریح استفاده می‌شود — مبحث بعدی.
پیمایش درخت
برخلاف آرایه که ترتیب واضح دارد، درخت را می‌توان به چند ترتیب پیمود:
- سطح به سطح (Level-order): ریشه، بعد سطح ۱، بعد سطح ۲... (با صف/BFS)
- عمق اول (DFS): رفتن تا عمق ممکن در هر شاخه (با پشته/بازگشت)
نکته: چرا درخت؟ چون جستجو در درخت متوازن O(log n) است — مثل آرایه مرتب اما با درج/حذف O(log n) به‌جای O(n)! بهترینِ هر دو دنیا.
جمع‌بندی
- درخت = سلسله‌مراتب بدون دور؛ ریشه، گره داخلی، برگ
- ارتفاع درخت متوازن = log n ← پایه کارایی O(log n)
- همه‌جا حاضر است: فایل‌سیستم، DOM، ایندکس دیتابیس، AI
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.