درخت ها (Trees)
«درخت (Tree)» یک ساختار داده سلسله مراتبی است. هر «گره (Node)» مقداری دارد و با «یال (Edge)» به فرزندها وصل می شود. این مدل مثل شاخه های یک درخت پخش می شود.
ایده اصلی درخت ها
درخت شبیه لیست های پیوندی است؛ گره ها داده و لینک دارند. اما بر خلاف ساختارهای خطی، هر گره می تواند چند فرزند داشته باشد. بنابراین مسیرها منشعب می شوند.
ساخت یک درخت ساده در پایتون
یک گره می سازیم که مقدار و فهرست فرزندها را نگه دارد. سپس پیمایش پیش سفری انجام می دهیم و همه مقادیر را چاپ می کنیم.
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(parent, child):
parent.children.append(child)
def preorder(root):
if root is None:
return
print(root.value)
for child in root.children:
preorder(child)
root = Node('R')
left = Node('A')
mid = Node('B')
right = Node('C')
add_child(root, left)
add_child(root, mid)
add_child(root, right)
add_child(left, Node('D'))
add_child(left, Node('E'))
add_child(right, Node('F'))
add_child(right, Node('G'))
preorder(root)
کاربردهای مهم درخت ها
- داده سلسله مراتبی؛ مانند پوشه ها و سازمان ها.
- پایگاه داده؛ بازیابی سریع اطلاعات.
- مسیر یابی شبکه؛ جدول های مسیر.
- مرتب سازی و جستجو؛ الگوریتم های رایج.
- صف های اولویت؛ مثل هیپ دودویی.
انواع درخت ها
درخت دودویی (Binary Tree): هر گره حداکثر دو فرزند دارد؛ چپ و راست.
درخت جستجوی دودویی (BST): چپ کوچک تر است و راست بزرگ تر است. این قانون جستجو را سریع می کند.
درخت AVL: یک BST خودمتوازن است. اختلاف ارتفاع زیر درخت ها حداکثر یک است. توازن با چرخش حفظ می شود.
درخت ها در برابر آرایه و لیست پیوندی
- آرایه: دسترسی مستقیم سریع است؛ درج و حذف کند است.
- لیست پیوندی: درج و حذف سریع است؛ دسترسی داخلی کند است.
- درخت ها: هم دسترسی خوب می دهند و هم درج و حذف مناسب.
گام های عملی
- کلاس Node با فرزندها بساز.
- یک درخت نمونه ایجاد کن.
- پیمایش پیش سفری یا درعرض را پیاده سازی کن.
برای مرور «هش تیبل ها» به هش تیبل ها برو. همچنین بخش لیست های پیوندی را ببین.
جمع بندی سریع
- درخت ها چند شاخه دارند، نه یک مسیر.
- گره مقدار و لینک فرزندها را دارد.
- کاربرد زیاد در جستجو و ساختاردهی دارد.
- تعادل درخت سرعت را پایدار نگه می دارد.