☝️☝️سری سوم آموزش ساختمان داده: پشته (Stack) و صف (Queue)☝️☝️

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۱: معرفی درخت‌ها

درخت چیست؟ 🌳

درخت یک ساختار داده‌ای غیرخطی است که از مجموعه‌ای از گره‌ها (Nodes) تشکیل شده. هر گره شامل یک مقدار (Value) و ارجاع به گره‌های فرزند خود است. گره‌ای که بالاترین سطح را دارد و هیچ گره‌ای به آن اشاره نمی‌کند، به عنوان ریشه (Root) شناخته می‌شود. سایر گره‌ها می‌توانند فرزند (Child) یا والد (Parent) داشته باشند.

ویژگی‌های اصلی درخت‌ها:
- گره (Node): هر گره شامل یک مقدار و ارجاع به گره‌های فرزند است.
- ریشه (Root): گره‌ای که در بالاترین سطح قرار دارد و نقطه شروع درخت است.
- برگ (Leaf): گره‌هایی که هیچ فرزندی ندارند.
- لبه (Edge): ارتباط بین دو گره (از والد به فرزند).
- سطح (Level): عمق یک گره، یعنی تعداد لبه‌ها از ریشه تا آن گره.
- ارتفاع (Height): بیشترین سطح درخت، یعنی بیشترین تعداد لبه‌ها از ریشه تا برگ.

کاربردهای درخت‌ها در برنامه‌نویسی 💻

درخت‌ها در بسیاری از مسائل و الگوریتم‌ها کاربرد دارن، از جمله:

1. سیستم فایل‌ها: سیستم‌های فایل (مثل NTFS یا FAT) به شکل درختی سازماندهی می‌شن. دایرکتوری‌ها به عنوان گره‌های والد و فایل‌ها به عنوان گره‌های فرزند یا برگ نمایش داده می‌شن.

2. سلسله مراتب سازمانی: نمودارهای سازمانی که سلسله مراتب مدیران و کارکنان رو نمایش می‌دهند، از ساختار درخت استفاده می‌کنن.

3. پایگاه داده‌ها: برخی از انواع پایگاه داده‌ها، به ویژه پایگاه‌های داده سلسله مراتبی، از ساختار درخت استفاده می‌کنن.

4. جستجو و مرتب‌سازی: درخت‌های جستجوی دودویی (Binary Search Trees) یکی از مهم‌ترین ساختارهای داده‌ای برای جستجو و مرتب‌سازی کارآمد هستن.

مثال ساده از یک درخت 📝

فرض کنید ما یک سیستم مدیریت پروژه داریم که شامل یک مدیر کل و چند تیم است. هر تیم نیز شامل چند زیرمجموعه و اعضای مختلف است. این ساختار می‌تونه به شکل یک درخت نمایش داده بشه:

مدیر کل (ریشه)
   ├── تیم ۱
   │   ├── عضو ۱
   │   └── عضو ۲
   ├── تیم ۲
   │   ├── عضو ۳
   │   └── عضو ۴
   └── تیم ۳
       ├── عضو ۵
       └── عضو ۶

در این مثال، "مدیر کل" ریشه درخت است و هر تیم به عنوان یک گره فرزند یا والد عمل می‌کنه. اعضا هم گره‌های برگ هستن که هیچ فرزندی ندارن.

در این پارت، با مفاهیم پایه‌ای درخت‌ها آشنا شدیم و فهمیدیم که چرا این ساختار داده‌ای اینقدر مهم و پرکاربرده. در پارت‌های بعدی به بررسی انواع مختلف درخت‌ها و پیاده‌سازی آن‌ها خواهیم پرداخت. آماده‌اید؟ پس همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۲: درخت‌های دودویی (Binary Trees)

توی پارت قبلی، با مفاهیم پایه‌ای درخت‌ها آشنا شدیم. حالا وقتشه که وارد جزئیات بشیم و یکی از مهم‌ترین انواع درخت‌ها رو بررسی کنیم: درخت‌های دودویی (Binary Trees). این نوع درخت یکی از پرکاربردترین‌هاست و پایه خیلی از مباحث پیشرفته‌تر رو تشکیل می‌ده. بیایید شروع کنیم! 🚀



درخت دودویی چیست؟ 🌳

درخت دودویی یک نوع درخت است که هر گره در آن حداکثر دو فرزند دارد. این دو فرزند معمولاً به عنوان فرزند چپ (Left Child) و فرزند راست (Right Child) شناخته می‌شن.

ویژگی‌های اصلی درخت‌های دودویی:
- گره (Node): هر گره شامل یک مقدار و ارجاع به حداکثر دو گره فرزند است.
- فرزند چپ (Left Child): گره‌ای که در سمت چپ گره والد قرار دارد.
- فرزند راست (Right Child): گره‌ای که در سمت راست گره والد قرار دارد.

انواع درخت‌های دودویی 🌲

درخت‌های دودویی خودشون به انواع مختلفی تقسیم می‌شن:

1. درخت دودویی کامل (Complete Binary Tree):
در این نوع درخت، همه سطوح به جز آخرین سطح، به طور کامل پر شده‌اند و در آخرین سطح نیز همه گره‌ها تا حد امکان در سمت چپ قرار گرفته‌اند.

2. درخت دودویی پر شده (Full Binary Tree):
در این نوع درخت، هر گره یا دقیقاً دو فرزند دارد یا هیچ فرزندی ندارد.

3. درخت دودویی متوازن (Balanced Binary Tree):
در این نوع درخت، تفاوت ارتفاع دو زیر درخت فرزند چپ و راست هیچ‌گاه بیشتر از یک نیست. این نوع درخت به کارآمد بودن عملیات‌های مختلف کمک می‌کنه.

پیاده‌سازی یک درخت دودویی ساده 📝

حالا بیایید یک درخت دودویی ساده رو پیاده‌سازی کنیم. در این مثال، هر گره شامل یک مقدار و ارجاع به دو گره فرزند چپ و راست است.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_value):
        self.root = Node(root_value)

    def insert_left(self, current_node, value):
        if current_node.left is None:
            current_node.left = Node(value)
        else:
            new_node = Node(value)
            new_node.left = current_node.left
            current_node.left = new_node

    def insert_right(self, current_node, value):
        if current_node.right is None:
            current_node.right = Node(value)
        else:
            new_node = Node(value)
            new_node.right = current_node.right
            current_node.right = new_node

مثال از درخت دودویی 🌲

فرض کنید می‌خواهیم یک درخت دودویی بسازیم که ساختارش به این شکل باشه:

      1
     / \
    2   3
   / \
  4   5

می‌تونیم این درخت رو با استفاده از کد زیر پیاده‌سازی کنیم:

# ساخت درخت
bt = BinaryTree(1)

# افزودن گره‌ها
bt.insert_left(bt.root, 2)
bt.insert_right(bt.root, 3)
bt.insert_left(bt.root.left, 4)
bt.insert_right(bt.root.left, 5)

عملیات پایه روی درخت دودویی 🛠️

درخت‌های دودویی شامل عملیات‌های پایه‌ای مثل درج (Insert)، حذف (Delete)، و جستجو (Search) هستن. در این پارت فقط با عملیات درج آشنا شدیم. در پارت‌های بعدی به صورت مفصل‌تر به این عملیات‌ها و روش‌های پیمایش درخت خواهیم پرداخت.

در این پارت، با درخت‌های دودویی و ویژگی‌هاشون آشنا شدیم و یک پیاده‌سازی ساده از اون‌ها رو دیدیم. در پارت بعدی به بررسی روش‌های مختلف پیمایش درخت‌های دودویی می‌پردازیم. همراه ما باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #درخت_دودویی #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۳: پیمایش درخت‌ها 🚶‍♂️🌲

در پارت قبلی، با درخت‌های دودویی و پیاده‌سازی اون‌ها آشنا شدیم. حالا وقتشه که به یکی از مهم‌ترین مباحث مرتبط با درخت‌ها بپردازیم: پیمایش درخت‌ها (Tree Traversal). این مبحث به شما کمک می‌کنه تا بتونید تمام گره‌های یک درخت رو به ترتیب‌های مختلف پیمایش کنید و داده‌ها رو به دست بیارید. پس بزن بریم! 🚀


پیمایش درخت‌ها چیست؟ 🌳

پیمایش درخت به معنای بازدید از همه گره‌های درخت به یک ترتیب خاص است. روش‌های مختلفی برای پیمایش درخت‌ها وجود داره که هر کدوم بسته به نیاز و کاربرد، می‌تونن مفید باشن.

در این پارت، چهار روش اصلی پیمایش درخت‌ها رو بررسی می‌کنیم:

1. پیمایش پیش‌نورد (Preorder Traversal)
2. پیمایش میانوند (Inorder Traversal)
3. پیمایش پس‌نورد (Postorder Traversal)
4. پیمایش سطح به سطح (Level-order Traversal)

1. پیمایش پیش‌نورد (Preorder Traversal) 🥇

در این روش، ابتدا گره ریشه (Root) بازدید می‌شه، سپس به ترتیب زیر درخت چپ و بعد زیر درخت راست بازدید می‌شن.

ترتیب بازدید:
1. گره ریشه
2. زیر درخت چپ
3. زیر درخت راست

مثال:

فرض کنید درخت زیر رو داریم:

      1
     / \
    2   3
   / \
  4   5

پیمایش پیش‌نورد این درخت به این صورت خواهد بود: 1, 2, 4, 5, 3

پیاده‌سازی:

def preorder_traversal(node):
    if node:
        print(node.value, end=' ')
        preorder_traversal(node.left)
        preorder_traversal(node.right)

2. پیمایش میانوند (Inorder Traversal) 📄

در این روش، ابتدا زیر درخت چپ بازدید می‌شه، سپس گره ریشه و در نهایت زیر درخت راست.

ترتیب بازدید:
1. زیر درخت چپ
2. گره ریشه
3. زیر درخت راست

مثال:

پیمایش میانوند درخت بالا به این صورت خواهد بود: 4, 2, 5, 1, 3

پیاده‌سازی:

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value, end=' ')
        inorder_traversal(node.right)

3. پیمایش پس‌نورد (Postorder Traversal) 🕒

در این روش، ابتدا زیر درخت چپ، سپس زیر درخت راست و در نهایت گره ریشه بازدید می‌شن.

ترتیب بازدید:
1. زیر درخت چپ
2. زیر درخت راست
3. گره ریشه

مثال:

پیمایش پس‌نورد درخت بالا به این صورت خواهد بود: 4, 5, 2, 3, 1

پیاده‌سازی:

def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=' ')

4. پیمایش سطح به سطح (Level-order Traversal) 📊

در این روش، گره‌ها به ترتیب سطح از بالا به پایین و از چپ به راست بازدید می‌شن. این روش اغلب با استفاده از یک صف (Queue) پیاده‌سازی می‌شه.

ترتیب بازدید:
1. سطح اول (گره ریشه)
2. سطح دوم (گره‌های فرزند)
3. سطح سوم و ...

مثال:

پیمایش سطح به سطح درخت بالا به این صورت خواهد بود: 1, 2, 3, 4, 5

پیاده‌سازی:

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.value, end=' ')
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

در این پارت، با چهار روش اصلی پیمایش درخت‌ها آشنا شدیم و هر کدوم رو با مثال‌ها و پیاده‌سازی‌های مختلف بررسی کردیم. این روش‌ها برای کار با درخت‌ها بسیار مهم هستن و در خیلی از الگوریتم‌های پیشرفته استفاده می‌شن. در پارت بعدی، با درخت‌های جستجوی دودویی (BST) آشنا خواهیم شد. همراه ما باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #پیمایش_درخت #درخت_دودویی #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۴: درخت‌های جستجوی دودویی (Binary Search Trees - BST) 🔍🌲

توی پارت قبلی، روش‌های پیمایش درخت‌ها رو بررسی کردیم. امروز می‌خوایم با یکی از مهم‌ترین و کاربردی‌ترین نوع درخت‌ها یعنی درخت‌های جستجوی دودویی (Binary Search Trees - BST) آشنا بشیم. این نوع درخت به شما اجازه می‌ده تا داده‌ها رو به صورت کارآمد ذخیره و جستجو کنید. بیایید شروع کنیم! 🚀

درخت جستجوی دودویی (BST) چیست؟ 🤔

یک درخت جستجوی دودویی یک نوع خاص از درخت‌های دودویی است که ویژگی‌های خاصی داره:

1. هر گره دارای یک مقدار (Value) است.
2. تمام گره‌های زیر درخت چپ دارای مقادیری کمتر از مقدار گره ریشه هستند.
3. تمام گره‌های زیر درخت راست دارای مقادیری بزرگتر یا مساوی مقدار گره ریشه هستند.
4. هر زیر درخت خودش یک درخت جستجوی دودویی است.

این ویژگی‌ها باعث می‌شه که عملیات جستجو، درج و حذف در BST به طور کارآمدی انجام بشه.

مزایای استفاده از BST 🌟

- جستجوی سریع: درخت جستجوی دودویی به شما این امکان رو می‌ده که در زمان نسبتاً کوتاهی یک مقدار رو پیدا کنید.
- مرتب‌سازی: داده‌ها در BST به صورت مرتب ذخیره می‌شن، بنابراین می‌تونید به راحتی داده‌ها رو به ترتیب بازخوانی کنید.
- انعطاف‌پذیری: می‌تونید داده‌ها رو به سادگی اضافه و حذف کنید.

عملیات روی BST 🛠️

1. درج (Insertion)
برای اضافه کردن یک مقدار جدید به BST:

- اگر درخت خالی باشه، مقدار جدید به عنوان گره ریشه قرار می‌گیره.
- اگر مقدار جدید کمتر از مقدار گره ریشه باشه، به زیر درخت چپ اضافه می‌شه.
- اگر مقدار جدید بزرگتر یا مساوی مقدار گره ریشه باشه، به زیر درخت راست اضافه می‌شه.

پیاده‌سازی:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    
    return node

2. جستجو (Search)
برای پیدا کردن یک مقدار در BST:

- از گره ریشه شروع می‌کنیم.
- اگر مقدار مورد نظر کمتر از گره ریشه باشه، به زیر درخت چپ می‌ریم.
- اگر بزرگتر باشه، به زیر درخت راست می‌ریم.
- اگر برابر باشه، مقدار پیدا شده.

پیاده‌سازی:

def search(node, value):
    if node is None or node.value == value:
        return node
    
    if value < node.value:
        return search(node.left, value)
    else:
        return search(node.right, value)

3. حذف (Deletion)
حذف یک گره در BST به سه حالت مختلف بستگی داره:

- بدون فرزند: گره به سادگی حذف می‌شه.
- یک فرزند: گره حذف می‌شه و فرزندش جایگزین اون می‌شه.
- دو فرزند: گره حذف می‌شه و کوچکترین مقدار از زیر درخت راست جایگزین اون می‌شه (یا بزرگترین مقدار از زیر درخت چپ).

پیاده‌سازی:

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

def delete(node, value):
    if node is None:
        return node
    
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        
        temp = min_value_node(node.right)
        node.value = temp.value
        node.right = delete(node.right, temp.value)
    
    return node

پیچیدگی زمانی عملیات در BST ⏱️

- جستجو: O(h)
- درج: O(h)
- حذف: O(h)

در اینجا h ارتفاع درخت است. در حالت عادی، ارتفاع درخت در بدترین حالت می‌تونه برابر تعداد گره‌ها (n) باشه، ولی اگر درخت متوازن باشه، ارتفاع برابر log(n) خواهد بود.

اهمیت تعادل (Balance) در BST ⚖️

اگر BST متوازن نباشه، کارایی اون کاهش پیدا می‌کنه و می‌تونه در بدترین حالت به یک لیست پیوندی تبدیل بشه. در پارت بعدی، به بررسی درخت‌های متوازن (Balanced Trees) می‌پردازیم که این مشکل رو حل می‌کنن.


این هم از بررسی درخت‌های جستجوی دودویی! 🌳 توی این پارت با مفهوم BST و عملیات مختلف روی اون آشنا شدیم. در پارت بعدی، به درخت‌های متوازن خواهیم پرداخت که به بهبود کارایی درخت‌های جستجوی دودویی کمک می‌کنن. با ما همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #درخت_دودویی #BST #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۵: درخت‌های متوازن (Balanced Trees) ⚖️🌲

سلام دوستان! 😊 امروز توی پارت پنجم، یکی از مباحث مهم و پیشرفته درخت‌ها رو بررسی می‌کنیم: درخت‌های متوازن (Balanced Trees). متوازن‌سازی درخت‌ها باعث می‌شه که عملیات‌های جستجو، درج و حذف کارآمدتر باشن و درخت همیشه در بهترین حالت عملکرد باقی بمونه. بیایید شروع کنیم! 🚀

درخت متوازن چیست؟ 🤔

یک درخت متوازن، درختیه که در آن ارتفاع دو زیر درخت چپ و راست هر گره تفاوت زیادی با هم نداشته باشن. به عبارت دیگر، اختلاف ارتفاع زیر درخت‌های چپ و راست یک گره نباید از یک مقدار مشخص (معمولاً ۱) بیشتر باشه. این تعادل باعث می‌شه که ارتفاع درخت تقریباً برابر log(n) باشه که n تعداد گره‌های درخته.

چرا متوازن‌سازی مهم است؟ 🌟

اگر درخت جستجوی دودویی (BST) متوازن نباشه، ممکنه در بدترین حالت به یک لیست پیوندی خطی تبدیل بشه، که در این صورت تمام عملیات‌های درج، جستجو و حذف به O(n) می‌رسن. در حالی که اگر درخت متوازن باشه، این عملیات‌ها به O(log n) کاهش پیدا می‌کنن.

انواع درخت‌های متوازن 🌳

چند نوع درخت متوازن معروف وجود دارن که هر کدوم ویژگی‌ها و الگوریتم‌های خاص خودشون رو دارن:

1. درخت AVL 🌲
- تعریف: درخت AVL یکی از اولین انواع درخت‌های متوازن جستجوگره. این درخت طوری طراحی شده که ارتفاع دو زیر درخت چپ و راست هر گره حداکثر ۱ اختلاف داشته باشه.
- عملیات: وقتی یک گره جدید به درخت اضافه یا از درخت حذف می‌شه، ممکنه تعادل درخت به هم بخوره. برای بازیابی تعادل، از چرخش‌های (Rotations) مختلف استفاده می‌کنیم.
- پیچیدگی زمانی: O(log n) برای درج، جستجو و حذف.

2. درخت Red-Black 🎨⚫
- تعریف: درخت Red-Black نوع دیگه‌ای از درخت‌های متوازنه که در اون هر گره به یکی از دو رنگ قرمز یا سیاه رنگ‌آمیزی می‌شه. این درخت قوانین خاصی داره که باعث می‌شه ارتفاع درخت متوازن باقی بمونه.
- ویژگی‌ها: درخت Red-Black همیشه یک درخت نیمه‌متوازنه که تضمین می‌کنه هیچ مسیری درخت بیش از دو برابر مسیر کوتاه‌ترین مسیر نباشه.
- پیچیدگی زمانی: O(log n) برای تمام عملیات‌ها.

پیاده‌سازی ساده درخت AVL 🛠️

در ادامه، یک پیاده‌سازی ساده از درخت AVL رو بررسی می‌کنیم.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    if not node:
        return 0
    return node.height

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    update_height(y)
    update_height(x)

    return x

def rotate_left(x):
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    update_height(x)
    update_height(y)

    return y

def insert(node, value):
    if not node:
        return Node(value)

    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)

    update_height(node)

    balance = get_balance(node)

    if balance > 1:
        if value < node.left.value:
            return rotate_right(node)
        else:
            node.left = rotate_left(node.left)
            return rotate_right(node)

    if balance < -1:
        if value > node.right.value:
            return rotate_left(node)
        else:
            node.right = rotate_right(node.right)
            return rotate_left(node)

    return node

مفهوم چرخش (Rotations) در درخت AVL 🔄

- چرخش به راست (Right Rotation): وقتی یک زیر درخت چپ بیش از حد رشد می‌کنه.
- چرخش به چپ (Left Rotation): وقتی یک زیر درخت راست بیش از حد رشد می‌کنه.
- چرخش دوگانه به راست-چپ و چپ-راست (Left-Right and Right-Left Rotations): برای زمانی که ترکیبی از عدم تعادل در زیر درخت‌ها وجود داره.

این چرخش‌ها کمک می‌کنن که درخت دوباره متوازن بشه و ارتفاع درخت کاهش پیدا کنه.

بررسی پیچیدگی زمانی در درخت‌های متوازن ⏱️

- جستجو: O(log n)
- درج: O(log n)
- حذف: O(log n)

این پیچیدگی‌ها نشان می‌ده که درخت‌های متوازن حتی در بدترین حالت هم عملکرد مناسبی دارن و برای کاربردهای واقعی بسیار مناسب هستن.

این هم از بررسی درخت‌های متوازن! 🌳 توی این پارت با درخت‌های AVL و Red-Black و همچنین چگونگی متوازن‌سازی درخت‌ها آشنا شدیم. در پارت بعدی، یک پروژه عملی رو پیاده‌سازی می‌کنیم تا همه این مفاهیم رو در عمل ببینیم. با ما همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #AVL #RedBlack #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳
پارت ۶: پروژه عملی و تمرین 💻🎓

سلام به همه! 😊 توی آخرین پارت از سری چهارم، می‌خوایم یک پروژه عملی رو با هم پیاده‌سازی کنیم که به ما کمک می‌کنه تمام مفاهیمی که توی پارت‌های قبلی یاد گرفتیم رو به کار ببریم. این پروژه می‌تونه درک شما از درخت‌ها، به ویژه درخت‌های دودویی (Binary Trees) و درخت‌های جستجوی دودویی (BST)، رو به طور قابل‌توجهی عمیق‌تر کنه.


پروژه: سیستم مدیریت مخاطبین با استفاده از درخت جستجوی دودویی (BST) 📱📇

در این پروژه، یک سیستم مدیریت مخاطبین (Contact Management System) رو پیاده‌سازی می‌کنیم که به کاربران اجازه می‌ده مخاطبین رو ذخیره، جستجو، حذف و نمایش بدن. برای مدیریت و ذخیره مخاطبین، از درخت جستجوی دودویی (BST) استفاده می‌کنیم. هر مخاطب بر اساس نامش در درخت ذخیره می‌شه.

مرحله ۱: تعریف کلاس‌های اصلی 🛠️

ابتدا یک کلاس برای نمایندگی هر مخاطب و یک کلاس برای درخت جستجوی دودویی ایجاد می‌کنیم.

class Contact:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone

class TreeNode:
    def __init__(self, contact):
        self.contact = contact
        self.left = None
        self.right = None

class ContactBST:
    def __init__(self):
        self.root = None

مرحله ۲: پیاده‌سازی عملیات درج ➕

برای درج یک مخاطب جدید، باید مکان مناسب رو در درخت پیدا کنیم و مخاطب رو در اونجا اضافه کنیم.

def insert(self, contact):
    if not self.root:
        self.root = TreeNode(contact)
    else:
        self._insert(self.root, contact)

def _insert(self, node, contact):
    if contact.name < node.contact.name:
        if node.left is None:
            node.left = TreeNode(contact)
        else:
            self._insert(node.left, contact)
    else:
        if node.right is None:
            node.right = TreeNode(contact)
        else:
            self._insert(node.right, contact)

مرحله ۳: جستجو در درخت 🔍

حالا باید روشی برای جستجو در بین مخاطبین داشته باشیم. این کار رو با استفاده از نام مخاطب انجام می‌دیم.

def search(self, name):
    return self._search(self.root, name)

def _search(self, node, name):
    if node is None or node.contact.name == name:
        return node
    if name < node.contact.name:
        return self._search(node.left, name)
    return self._search(node.right, name)

مرحله ۴: حذف یک مخاطب 🗑️

برای حذف یک مخاطب، باید سه حالت مختلف رو بررسی کنیم:
1. گره‌ای که حذف می‌شه برگی باشه.
2. گره‌ای که حذف می‌شه یک فرزند داشته باشه.
3. گره‌ای که حذف می‌شه دو فرزند داشته باشه.

def delete(self, name):
    self.root = self._delete(self.root, name)

def _delete(self, node, name):
    if node is None:
        return node

    if name < node.contact.name:
        node.left = self._delete(node.left, name)
    elif name > node.contact.name:
        node.right = self._delete(node.right, name)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left

        min_larger_node = self._get_min(node.right)
        node.contact = min_larger_node.contact
        node.right = self._delete(node.right, min_larger_node.contact.name)

    return node

def _get_min(self, node):
    current = node
    while current.left is not None:
        current = current.left
    return current

مرحله ۵: نمایش مخاطبین (پیمایش درخت) 📜

برای نمایش همه مخاطبین، از پیمایش میانوند (Inorder Traversal) استفاده می‌کنیم که مخاطبین رو به ترتیب حروف الفبا نمایش می‌ده.

def inorder_traversal(self):
    self._inorder_traversal(self.root)

def _inorder_traversal(self, node):
    if node:
        self._inorder_traversal(node.left)
        print(f"Name: {node.contact.name}, Phone: {node.contact.phone}")
        self._inorder_traversal(node.right)

مرحله ۶: استفاده از سیستم مدیریت مخاطبین 📱

حالا می‌تونیم مخاطبین جدید اضافه کنیم، جستجو کنیم، حذف کنیم و لیست مخاطبین رو نمایش بدیم:

maine__ == "__main__":
    contacts = ContactBST()

ادامه کد بالا...

# افزودن مخاطبین
    contacts.insert(Contact("Alice", "123456789"))
    contacts.insert(Contact("Bob", "987654321"))
    contacts.insert(Contact("Charlie", "555666777"))

    # نمایش مخاطبین
    print("All contacts:")
    contacts.inorder_traversal()

    # جستجو
    print("\nSearching for Bob:")
    found = contacts.search("Bob")
    if found:
        print(f"Found: {found.contact.name} - {found.contact.phone}")
    else:
        print("Contact not found.")

    # حذف
    print("\nDeleting Alice:")
    contacts.delete("Alice")

    # نمایش دوباره مخاطبین
    print("\nAll contacts after deletion:")
    contacts.inorder_traversal()

مرحله ۷: تمرین‌ها 📝

1. افزودن قابلیت به‌روزرسانی: برنامه‌تون رو گسترش بدید تا کاربران بتونن اطلاعات یک مخاطب رو به‌روزرسانی کنن (مثلاً تغییر شماره تلفن).
2. افزودن قابلیت جستجوی فازی: قابلیت جستجوی فازی (Fuzzy Search) رو اضافه کنید تا کاربر بتونه با وارد کردن بخشی از نام، مخاطبین مرتبط رو پیدا کنه.
3. گسترش به درخت متوازن: سیستم مدیریت مخاطبین رو به یک درخت متوازن (مثل AVL یا Red-Black) ارتقا بدید تا عملکرد جستجو و درج بهینه‌تر بشه.


این هم از پروژه عملی پارت آخر! 💻 این پروژه به شما کمک می‌کنه که مفاهیم درخت‌ها رو به خوبی درک کنید و بتونید از اون‌ها در برنامه‌های واقعی استفاده کنید. امیدوارم که از این سری لذت برده باشید و اطلاعات مفیدی کسب کرده باشید! 🎉

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #پروژه_پایتون #BST #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۱: معرفی گراف‌ها 🌐

سلام به همه! 😊 در این پارت، به بررسی مبانی گراف‌ها می‌پردازیم. گراف‌ها یکی از ساختارهای داده‌ای پیچیده و قدرتمند هستند که در مسائل مختلف برنامه‌نویسی و الگوریتم‌ها کاربردهای فراوانی دارند. بیایید با هم به بررسی مفاهیم پایه و انواع گراف‌ها بپردازیم. 🚀

گراف چیست؟ 🤔

گراف یک ساختار داده‌ای است که شامل مجموعه‌ای از رئوس (Nodes یا Vertices) و یال‌ها (Edges) است. یال‌ها به رئوس متصل می‌شوند و ارتباطات یا روابط بین آن‌ها را نشان می‌دهند. گراف‌ها می‌توانند مدل‌های پیچیده‌تری از داده‌ها را نسبت به دیگر ساختارهای داده‌ای مثل آرایه‌ها و لیست‌های پیوندی ارائه دهند.

مفاهیم پایه 📚

- راس (Vertex): هر یک از نقاط یا گره‌های گراف که ممکن است نماینده اشیاء یا موجودیت‌های مختلف باشد.
- یال (Edge): ارتباط بین دو راس که می‌تواند وزن‌دار یا بدون وزن باشد.

انواع گراف‌ها 🔍

1. گراف‌های بدون جهت (Undirected Graphs) 🌟
- تعریف: در این نوع گراف‌ها، یال‌ها بدون جهت هستند و ارتباط بین دو راس به صورت دوطرفه است. یعنی اگر یالی بین راس ( A ) و راس ( B ) وجود داشته باشد، ارتباط از ( A ) به ( B ) و از ( B ) به ( A ) برقرار است.
- مثال: شبکه‌های اجتماعی، جایی که دوستان دوطرفه هستند.

2. گراف‌های جهت‌دار (Directed Graphs) 🌟
- تعریف: در این گراف‌ها، یال‌ها دارای جهت هستند و ارتباط بین دو راس یک‌طرفه است. یعنی اگر یالی از راس ( A ) به راس ( B ) وجود داشته باشد، ارتباط از ( B ) به ( A ) برقرار نیست.
- مثال: مسیرهای یک نقشه، جایی که مسیرها یک‌طرفه هستند.

3. گراف‌های وزن‌دار (Weighted Graphs) 🌟
- تعریف: در این گراف‌ها، هر یال دارای یک وزن است که می‌تواند نشان‌دهنده هزینه، مسافت یا هر نوع دیگری از مقادیر عددی باشد.
- مثال: نقشه‌های جغرافیایی، جایی که مسافت بین نقاط مختلف اهمیت دارد.

4. گراف‌های بدون وزن (Unweighted Graphs) 🌟
- تعریف: در این گراف‌ها، یال‌ها هیچ وزنی ندارند و تنها وجود یا عدم وجود ارتباط بین رئوس اهمیت دارد.
- مثال: شبکه‌های ارتباطی ساده، جایی که فقط ارتباط وجود یا عدم وجود اهمیت دارد.

5. گراف‌های متصل و غیر متصل 🌟
- گراف متصل: گرافی که در آن از هر راس می‌توان به سایر رئوس دسترسی پیدا کرد.
- گراف غیر متصل: گرافی که برخی از رئوس به یکدیگر متصل نیستند و به چند بخش جداگانه تقسیم می‌شود.

کاربردهای گراف‌ها 🌍

گراف‌ها در مسائل مختلفی کاربرد دارند، از جمله:

- شبکه‌های اجتماعی: مدل‌سازی ارتباطات دوستان و پیوندهای شبکه‌ای.
- نقشه‌های جغرافیایی: نمایندگی مسیرها و نقاط مختلف جغرافیایی.
- مدیریت پروژه: مدل‌سازی و بررسی وابستگی‌ها و مراحلی که باید به ترتیب انجام شوند.

تصویرسازی گراف‌ها 🎨

برای درک بهتر گراف‌ها، معمولاً از نمودارهای گرافیکی استفاده می‌شود. این نمودارها به نمایش رئوس و یال‌ها و ارتباطات بین آن‌ها کمک می‌کنند و به شما امکان می‌دهند تا ساختار گراف را به صورت بصری مشاهده کنید.


در این پارت، با مفاهیم پایه گراف‌ها و انواع مختلف آن‌ها آشنا شدیم. در پارت بعدی، به بررسی نمایندگی‌های مختلف گراف‌ها و مزایا و معایب هر یک خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#گراف #ساختمان_داده #برنامه_نویسی #آموزش_پایتون #گراف_جهت‌دار #گراف_بدون_جهت #گراف_وزن‌دار

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۲: نمایندگی گراف‌ها 🖼️

سلام به همه! 😊 در این پارت، به بررسی نحوه نمایندگی گراف‌ها در حافظه می‌پردازیم. درک نحوه نمایش گراف‌ها به ما کمک می‌کند تا الگوریتم‌ها را به درستی پیاده‌سازی کنیم و عملکرد آن‌ها را بهتر درک کنیم. 🚀


نمایندگی گراف‌ها 📊

برای نمایش گراف‌ها در حافظه، از دو روش اصلی استفاده می‌شود: ماتریس مجاورت (Adjacency Matrix) و لیست مجاورت (Adjacency List). هر کدام از این روش‌ها مزایا و معایب خاص خود را دارند و مناسب استفاده در موقعیت‌های مختلف هستند.

۱. ماتریس مجاورت (Adjacency Matrix) 📐

- تعریف: ماتریس مجاورت یک ماتریس دو بعدی است که در آن هر عنصر ( (i, j) ) نشان‌دهنده وجود یا عدم وجود یال بین راس‌های ( i ) و ( j ) است. برای گراف‌های وزن‌دار، مقدار عنصر ( (i, j) ) وزن یال است و برای گراف‌های بدون وزن، مقدار آن 1 (وجود یال) یا 0 (عدم وجود یال) است.

- مزایا:
- دسترسی سریع: زمان دسترسی به وجود یا عدم وجود یال بین دو راس ( O(1) ) است.
- ساده‌سازی: پیاده‌سازی و درک آن ساده است.

- معایب:
- حافظه زیاد: نیاز به ( O(V^2) ) حافظه دارد، جایی که ( V) تعداد رئوس است، حتی اگر گراف sparse (کم‌درصد یال‌ها) باشد.
- کارایی پایین: برای گراف‌های بزرگ و sparse می‌تواند ناکارآمد باشد.

- نمونه پیاده‌سازی:

    # پیاده‌سازی ماتریس مجاورت برای گراف بدون وزن
    def create_adjacency_matrix(vertices, edges):
        matrix = [[0] * vertices for _ in range(vertices)]
        for u, v in edges:
            matrix[u][v] = 1
            matrix[v][u] = 1  # اگر گراف بدون جهت است
        return matrix
    

۲. لیست مجاورت (Adjacency List) 🗂️

- تعریف: لیست مجاورت یک آرایه از لیست‌ها است، که در آن هر ایندکس از آرایه نمایانگر یک راس است و لیست‌های مرتبط نشان‌دهنده رئوس مجاور آن راس هستند. برای گراف‌های وزن‌دار، هر یال می‌تواند همراه با وزن آن ذخیره شود.

- مزایا:
- حافظه کمتر: نیاز به ( O(V + E) ) حافظه دارد، جایی که ( E ) تعداد یال‌ها است. برای گراف‌های sparse، حافظه بهینه‌تری نسبت به ماتریس مجاورت استفاده می‌کند.
- عملکرد بهتر برای گراف‌های بزرگ: کارایی بهتر در اضافه کردن یا حذف یال‌ها و پیمایش یال‌ها.

- معایب:
- دسترسی کمتر سریع: زمان دسترسی به وجود یال بین دو راس ( O(V) ) می‌تواند باشد، که ممکن است برای گراف‌های بزرگ کند باشد.
- پیاده‌سازی پیچیده‌تر: مدیریت و پیاده‌سازی آن پیچیده‌تر از ماتریس مجاورت است.

- نمونه پیاده‌سازی:

    # پیاده‌سازی لیست مجاورت برای گراف بدون وزن
    def create_adjacency_list(vertices, edges):
        adj_list = [[] for _ in range(vertices)]
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)  # اگر گراف بدون جهت است
        return adj_list
    

نمودار نمونه 🖼️

- ماتریس مجاورت:

  A B C D
  A 0 1 0 1
  B 1 0 1 0
  C 0 1 0 1
  D 1 0 1 0
  

- لیست مجاورت:

  A: [B, D]
  B: [A, C]
  C: [B, D]
  D: [A, C]
  

در این پارت، نمایندگی گراف‌ها را با استفاده از ماتریس مجاورت و لیست مجاورت بررسی کردیم. در پارت بعدی، به الگوریتم‌های جستجو در گراف‌ها خواهیم پرداخت و نحوه پیمایش در گراف‌ها را بررسی خواهیم کرد. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#گراف #نمایندگی_گراف #ماتریس_مجاورت #لیست_مجاورت #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۳: الگوریتم‌های جستجو در گراف‌ها 🔍

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم اصلی جستجو در گراف‌ها می‌پردازیم: جستجوی عمق‌اول (DFS) و جستجوی پهنای‌اول (BFS). این الگوریتم‌ها ابزارهای اساسی برای پیمایش و تحلیل گراف‌ها هستند. 🚀

الگوریتم‌های جستجو در گراف‌ها 🧩

۱. جستجوی عمق‌اول (Depth-First Search - DFS) 🌲

- تعریف: الگوریتم جستجوی عمق‌اول برای پیمایش یا جستجوی در گراف به روش عمق‌محور عمل می‌کند. این الگوریتم به ترتیب در عمق گراف جستجو می‌کند و تا زمانی که به گره‌ای نرسد که دیگر هیچ گره فرزند نداشته باشد، به پیشروی ادامه می‌دهد.

- ویژگی‌ها:
- پیاده‌سازی: می‌تواند با استفاده از پشته یا بازگشت پیاده‌سازی شود.
- کاربردها: یافتن مسیرها، بررسی اتصال، الگوریتم‌های بازیابی، و حل معماها.

- پیاده‌سازی DFS:

  def dfs(graph, start, visited=None):
      if visited is None:
          visited = set()
      visited.add(start)
      print(start)
      for neighbor in graph[start]:
          if neighbor not in visited:
              dfs(graph, neighbor, visited)
      return visited
  

- مثال:

برای گراف زیر:

  A -- B -- C
  |    |
  D -- E
  

اجرای dfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, C, E, D.

۲. جستجوی پهنای‌اول (Breadth-First Search - BFS) 🌐

- تعریف: الگوریتم جستجوی پهنای‌اول برای پیمایش گراف به روش سطح‌محور عمل می‌کند. این الگوریتم از یک گره شروع کرده و به ترتیب به گره‌های همسایه آن سطح به سطح جستجو می‌کند.

- ویژگی‌ها:
- پیاده‌سازی: با استفاده از صف پیاده‌سازی می‌شود.
- کاربردها: یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن، الگوریتم‌های بهینه‌سازی، و حل معماهای جغرافیایی.

- پیاده‌سازی BFS:

  from collections import deque

  def bfs(graph, start):
      visited = set()
      queue = deque([start])
      while queue:
          vertex = queue.popleft()
          if vertex not in visited:
              print(vertex)
              visited.add(vertex)
              queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
      return visited
  

- مثال:

برای همان گراف:

  A -- B -- C
  |    |
  D -- E
  

اجرای bfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, D, C, E.

مقایسه DFS و BFS 🔍

- DFS:
- مزایا: می‌تواند مسیرهای طولانی و پیچیده را سریعاً پیدا کند.
- معایب: ممکن است گراف‌های بزرگ را به صورت عمیق جستجو کند و به حافظه زیادی نیاز داشته باشد.

- BFS:
- مزایا: مناسب برای یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن.
- معایب: ممکن است حافظه بیشتری نسبت به DFS نیاز داشته باشد به دلیل ذخیره‌ی تمام گره‌های سطحی.


در این پارت، الگوریتم‌های جستجو در گراف‌ها یعنی DFS و BFS را بررسی کردیم. در پارت بعدی، به الگوریتم‌های جستجوی کوتاه‌ترین مسیر در گراف‌ها خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#جستجوی_عمق_اول #جستجوی_پهنای_اول #DFS #BFS #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۴: الگوریتم‌های کوتاه‌ترین مسیر 🛤️

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم مهم برای پیدا کردن کوتاه‌ترین مسیر در گراف‌ها خواهیم پرداخت: الگوریتم دیکسترا (Dijkstra) و الگوریتم فلوید-وارشال (Floyd-Warshall). این الگوریتم‌ها در مسائل مختلف مسیریابی و تحلیل گراف کاربرد دارند. 🚀

الگوریتم‌های کوتاه‌ترین مسیر 🧭

۱. الگوریتم دیکسترا (Dijkstra’s Algorithm) 🚗

- تعریف: الگوریتم دیکسترا برای یافتن کوتاه‌ترین مسیر از یک گره مبدأ به تمام گره‌های دیگر در گراف‌های وزن‌دار و غیرمنفی طراحی شده است. این الگوریتم از گره مبدأ شروع کرده و مسیرهای کوتاه‌ترین فاصله را به گره‌های دیگر محاسبه می‌کند.

- ویژگی‌ها:
- محدودیت: فقط برای گراف‌های با وزن‌های غیرمنفی مناسب است.
- پیاده‌سازی: می‌تواند با استفاده از ساختار داده‌های مختلف مانند صف اولویت یا بنیاد هِپ پیاده‌سازی شود.

- پیاده‌سازی دیکسترا:

  import heapq

  def dijkstra(graph, start):
      # Initialize distances and priority queue
      distances = {vertex: float('infinity') for vertex in graph}
      distances[start] = 0
      priority_queue = [(0, start)]

      while priority_queue:
          current_distance, current_vertex = heapq.heappop(priority_queue)

          # Nodes can only be added once to the priority queue
          if current_distance > distances[current_vertex]:
              continue

          for neighbor, weight in graph[current_vertex].items():
              distance = current_distance + weight

              # Only consider this new path if it's better
              if distance < distances[neighbor]:
                  distances[neighbor] = distance
                  heapq.heappush(priority_queue, (distance, neighbor))

      return distances
  

- مثال:

برای گراف زیر:

  A --(1)-- B --(4)-- C
  |         |
  (2)       (6)
  |
  D
  

اجرای dijkstra(graph, 'A') ممکن است فواصل کوتاه‌ترین مسیر از A به سایر گره‌ها را به صورت زیر ارائه دهد:
- A → B: 1
- A → C: 7
- A → D: 2

۲. الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) 🌐

- تعریف: الگوریتم فلوید-وارشال برای پیدا کردن کوتاه‌ترین مسیر بین تمام جفت گره‌ها در گراف‌های وزن‌دار (چه مثبت و چه منفی) طراحی شده است. این الگوریتم قادر است ماتریس کوتاه‌ترین مسیرها را برای تمامی جفت گره‌ها محاسبه کند.

- ویژگی‌ها:
- محدودیت: می‌تواند با وزن‌های منفی کار کند اما نباید دورهای منفی وجود داشته باشد.
- پیاده‌سازی: با استفاده از ماتریس پیاده‌سازی می‌شود.

- پیاده‌سازی فلوید-وارشال:

  def floyd_warshall(graph):
      # Initialize distances
      vertices = list(graph.keys())
      distances = {vertex: {v: float('infinity') for v in vertices} for vertex in vertices}
      
      for u in vertices:
          distances[u][u] = 0
          for v, weight in graph[u].items():
              distances[u][v] = weight

      # Compute shortest paths
      for k in vertices:
          for i in vertices:
              for j in vertices:
                  if distances[i][j] > distances[i][k] + distances[k][j]:
                      distances[i][j] = distances[i][k] + distances[k][j]

      return distances
  

- مثال:

برای همان گراف:

  A --(1)-- B --(4)-- C
  |         |
  (2)       (6)
  |
  D
  

اجرای floyd_warshall(graph) ممکن است ماتریس کوتاه‌ترین مسیرها را به صورت زیر تولید کند:
- A → B: 1
- A → C: 7
- A → D: 2

مقایسه دیکسترا و فلوید-وارشال ⚖️

- دیکسترا:
- مزایا: سریع‌تر برای گراف‌های بزرگ و فقط یک منبع.
- معایب: تنها برای گراف‌های غیرمنفی مناسب است.

- فلوید-وارشال:
- مزایا: مناسب برای گراف‌هایی با وزن‌های منفی و برای یافتن کوتاه‌ترین مسیرها بین تمام جفت گره‌ها.
- معایب: کندتر برای گراف‌های بسیار بزرگ به دلیل پیچیدگی زمانی (O(V^3)).

در این پارت، الگوریتم‌های دیکسترا و فلوید-وارشال را بررسی کردیم. در پارت بعدی، به بررسی الگوریتم‌های درخت‌های پوشا خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#الگوریتم_دیکسترا #الگوریتم_فلوید_وارشال #کوتاه‌ترین_مسیر #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۵: الگوریتم‌های درخت‌های پوشا (Minimum Spanning Tree) 🌳

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم مهم برای یافتن درخت پوشای کمینه (Minimum Spanning Tree - MST) در گراف‌ها خواهیم پرداخت: الگوریتم کرُسکل (Kruskal) و الگوریتم پرایم (Prim). این الگوریتم‌ها در مسائل مختلفی مانند طراحی شبکه و بهینه‌سازی ساختارها کاربرد دارند. 🚀

الگوریتم‌های درخت‌های پوشا کمینه (MST) 🌟

۱. الگوریتم کرُسکل (Kruskal’s Algorithm) 🌲

- تعریف: الگوریتم کرُسکل برای یافتن درخت پوشای کمینه در یک گراف وزن‌دار طراحی شده است. این الگوریتم از انتخاب یال‌های کمترین وزن و افزودن آن‌ها به درخت تا زمانی که همه گره‌ها پوشش داده شوند، استفاده می‌کند.

- ویژگی‌ها:
- روش: گراف را با یال‌های وزن‌دار مرتب می‌کند و یال‌ها را به ترتیب اضافه می‌کند تا یک درخت پوشا کمینه تشکیل شود.
- پیاده‌سازی: با استفاده از ساختار داده‌ی مجموعه‌های پیشرفته (Union-Find) برای جلوگیری از ایجاد حلقه‌ها (Cycles).

- پیاده‌سازی کرُسکل:

  class UnionFind:
      def __init__(self, n):
          self.parent = list(range(n))
          self.rank = [0] * n

      def find(self, u):
          if self.parent[u] != u:
              self.parent[u] = self.find(self.parent[u])
          return self.parent[u]

      def union(self, u, v):
          rootU = self.find(u)
          rootV = self.find(v)
          if rootU != rootV:
              if self.rank[rootU] > self.rank[rootV]:
                  self.parent[rootV] = rootU
              elif self.rank[rootU] < self.rank[rootV]:
                  self.parent[rootU] = rootV
              else:
                  self.parent[rootV] = rootU
                  self.rank[rootU] += 1

  def kruskal(vertices, edges):
      union_find = UnionFind(len(vertices))
      mst = []
      edges = sorted(edges, key=lambda x: x[2])

      for u, v, weight in edges:
          if union_find.find(u) != union_find.find(v):
              union_find.union(u, v)
              mst.append((u, v, weight))

      return mst
  

- مثال:

برای گراف با یال‌ها و وزن‌های زیر:

  A --(1)-- B
  |         |
  (3)       (4)
  |
  C
  

اجرای kruskal(vertices, edges) ممکن است درخت پوشای کمینه به شکل زیر باشد:
- A → B با وزن 1
- A → C با وزن 3

۲. الگوریتم پرایم (Prim’s Algorithm) 🌳

- تعریف: الگوریتم پرایم برای یافتن درخت پوشای کمینه از یک گره شروع می‌کند و به تدریج یال‌های کمترین وزن را به درخت اضافه می‌کند تا تمامی گره‌ها به درخت اضافه شوند.

- ویژگی‌ها:
- روش: از یک گره شروع می‌کند و یال‌های کمترین وزن را به درخت اضافه می‌کند تا همه گره‌ها پوشش داده شوند.
- پیاده‌سازی: با استفاده از داده‌های ساختار اولویت برای انتخاب یال‌های کمترین وزن.

- پیاده‌سازی پرایم:

  import heapq

  def prim(graph, start):
      mst = []
      visited = set()
      min_heap = [(0, start)]
      total_weight = 0

      while min_heap:
          weight, u = heapq.heappop(min_heap)
          if u in visited:
              continue

          visited.add(u)
          total_weight += weight
          if weight > 0:
              mst.append((prev, u, weight))

          for v, w in graph[u].items():
              if v not in visited:
                  heapq.heappush(min_heap, (w, v))
                  prev = u

      return mst, total_weight
  

- مثال:

برای همان گراف:

  A --(1)-- B
  |         |
  (3)       (4)
  |
  C
  

اجرای prim(graph, 'A') ممکن است درخت پوشای کمینه به شکل زیر باشد:
- A → B با وزن 1
- A → C با وزن 3

مقایسه کرُسکل و پرایم ⚖️

- کرُسکل:
- مزایا: مناسب برای گراف‌های پراکنده با تعداد یال‌های کم.
- معایب: پیچیدگی در استفاده از Union-Find.

- پرایم:
- مزایا: مناسب برای گراف‌های چگال با تعداد یال‌های زیاد.
- معایب: نیاز به استفاده از ساختار داده‌های اولویت.


در این پارت، الگوریتم‌های کرُسکل و پرایم را بررسی کردیم. در پارت بعدی، به بررسی پروژه‌های عملی و تمرین‌ها برای تثبیت مفاهیم خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۶: تمرین و پروژه عملی 🚀

سلام به همه! 🌟 در این پارت، به پیاده‌سازی یک پروژه عملی و حل تمرین‌ها برای تثبیت مفاهیم گراف‌ها خواهیم پرداخت. این تمرینات به شما کمک می‌کند تا مفاهیم یادگرفته شده را به صورت عملی پیاده‌سازی کنید و درک عمیق‌تری از گراف‌ها پیدا کنید.

پروژه عملی: مسیریابی در نقشه 🗺️

توضیحات پروژه:
هدف این پروژه پیاده‌سازی یک سیستم مسیریابی در نقشه است. در این پروژه، از گراف برای مدل‌سازی نقشه و یافتن کوتاه‌ترین مسیر بین دو نقطه استفاده خواهیم کرد. همچنین، از الگوریتم‌های جستجو و مسیریابی که در این سری آموختیم، بهره خواهیم برد.

مراحل پروژه:

1. تعریف گراف:
- مدل‌سازی نقشه به عنوان گراف با گره‌ها (مکان‌ها) و یال‌ها (مسیرها).
- هر یال دارای وزن خواهد بود که نشان‌دهنده طول یا هزینه مسیر است.

2. پیاده‌سازی نمایندگی گراف:
- استفاده از لیست مجاورت برای نمایندگی گراف.
- تعریف کلاس برای گراف و اضافه کردن گره‌ها و یال‌ها.

   class Graph:
       def __init__(self):
           self.graph = {}

       def add_vertex(self, vertex):
           if vertex not in self.graph:
               self.graph[vertex] = {}

       def add_edge(self, u, v, weight):
           if u not in self.graph:
               self.add_vertex(u)
           if v not in self.graph:
               self.add_vertex(v)
           self.graph[u][v] = weight
           self.graph[v][u] = weight  # برای گراف بدون جهت
   

3. پیاده‌سازی الگوریتم‌های مسیریابی:
- استفاده از الگوریتم دیکسترا برای یافتن کوتاه‌ترین مسیر بین دو نقطه.
- پیاده‌سازی الگوریتم دیکسترا:

   import heapq

   def dijkstra(graph, start):
       distances = {vertex: float('infinity') for vertex in graph.graph}
       distances[start] = 0
       priority_queue = [(0, start)]

       while priority_queue:
           current_distance, u = heapq.heappop(priority_queue)

           if current_distance > distances[u]:
               continue

           for neighbor, weight in graph.graph[u].items():
               distance = current_distance + weight

               if distance < distances[neighbor]:
                   distances[neighbor] = distance
                   heapq.heappush(priority_queue, (distance, neighbor))

       return distances
   

4. اجرای پروژه:
- تعریف گراف با مکان‌ها و مسیرها.
- یافتن کوتاه‌ترین مسیر بین دو نقطه با استفاده از الگوریتم دیکسترا.

   # تعریف گراف
   g = Graph()
   g.add_edge('A', 'B', 1)
   g.add_edge('A', 'C', 4)
   g.add_edge('B', 'C', 2)
   g.add_edge('B', 'D', 5)
   g.add_edge('C', 'D', 1)

   # یافتن کوتاه‌ترین مسیر از 'A' به سایر نقاط
   distances = dijkstra(g, 'A')
   print(distances)
   

5. نتیجه‌گیری:
- بررسی نتایج و تحلیل عملکرد الگوریتم.
- افزودن قابلیت‌های اضافی مانند نمایش مسیر کوتاه‌تر.


تمرین‌های تکمیلی ✏️

1. مسئله کوتاه‌ترین مسیر:
- پیاده‌سازی الگوریتم فلوید-وارشال برای یافتن همه‌به‌همه مسیرها در گراف.

2. مدیریت شبکه اجتماعی:
- طراحی سیستمی برای مدیریت شبکه اجتماعی با قابلیت‌های جستجو و نمایش روابط بین کاربران با استفاده از گراف.

3. گراف‌های جهت‌دار:
- پیاده‌سازی و تحلیل الگوریتم‌های جستجو و مسیریابی برای گراف‌های جهت‌دار.


با تکمیل این پروژه و تمرین‌ها، درک شما از گراف‌ها و الگوریتم‌های آن‌ها بهبود خواهد یافت. برای هر سوال یا نیاز به راهنمایی بیشتر، خوشحال می‌شویم که کمک کنیم. موفق باشید! 🌟

(برای بیشتر یاد گفتن اینجا کلیک کن)

#گراف #مسیریابی #الگوریتم_دیکسترا #پروژه_عملی #ساختمان_داده #برنامه_نویسی #آموزش_پایتون

سری پنجم از آموزش ساختمان داده (گراف ها)(graphs)☝️☝️

سری ششم: هشینگ (Hashing) و جداول هش (Hash Tables)
پارت ۱: معرفی هشینگ و توابع هش 🔢

سلام به همه! 👋 در این پارت از سری آموزش‌ها، به مبحث هشینگ (Hashing) و توابع هش (Hash Functions) خواهیم پرداخت. هشینگ یکی از تکنیک‌های کلیدی در ساختارهای داده‌ای است که کاربردهای زیادی در زمینه‌های مختلف دارد. بیایید با هم این مبحث مهم و کاربردی را بررسی کنیم.

هشینگ چیست؟ 🤔

هشینگ فرآیندی است که به وسیله آن داده‌های ورودی با اندازه متغیر به یک مقدار خروجی با اندازه ثابت، که به آن کد هش یا مقدار هش گفته می‌شود، نگاشت می‌شوند. این مقدار خروجی معمولاً به صورت عددی است که نشان‌دهنده مکان یا شاخصی در یک ساختار داده‌ای (مثل آرایه) است.

چرا هشینگ اهمیت دارد؟

- سرعت بالا: یکی از دلایل اصلی استفاده از هشینگ، سرعت بالا در دسترسی، درج و حذف داده‌هاست.
- توزیع یکنواخت داده‌ها: توابع هش تلاش می‌کنند تا داده‌ها را به صورت یکنواخت در فضای خروجی توزیع کنند تا برخوردها (Collisions) به حداقل برسد.
- کاربرد گسترده: هشینگ در بسیاری از مسائل مثل جستجو، مدیریت داده‌های بزرگ، و امنیت اطلاعات کاربرد دارد.

توابع هش چیست؟ 🧮

یک تابع هش، یک الگوریتم یا تابع ریاضی است که داده‌های ورودی (معمولاً یک کلید) را به یک مقدار عددی ثابت تبدیل می‌کند. این مقدار عددی می‌تواند به عنوان شاخصی در یک آرایه یا جدول استفاده شود.

ویژگی‌های یک تابع هش مناسب:

1. سرعت بالا: تابع هش باید سریع باشد تا عملکرد کلی سیستم تحت تاثیر قرار نگیرد.
2. توزیع یکنواخت: یک تابع هش خوب داده‌ها را به طور یکنواخت در فضای خروجی توزیع می‌کند تا از بروز برخوردها جلوگیری کند.
3. تصادفی بودن: خروجی تابع هش باید به گونه‌ای باشد که به سختی بتوان الگوی مشخصی در آن یافت.

مثال‌هایی از توابع هش معروف:

1. تابع هش مدولار (Modulo Hash Function):
- ساده‌ترین و رایج‌ترین نوع تابع هش.
- فرض کنید کلید ما عدد k باشد. تابع هش برابر با k % m است که m اندازه آرایه است.
- مثال: اگر k = 50 و m = 10 باشد، مقدار هش برابر با 50 % 10 = 0 خواهد بود.

2. تابع هش ضربی (Multiplicative Hash Function):
- از یک مقدار ثابت برای ضرب کلید و سپس استفاده از مدولار برای کاهش مقدار استفاده می‌کند.
- این نوع تابع معمولاً توزیع یکنواخت‌تری دارد.

3. توابع هش رمزنگاری (Cryptographic Hash Functions):
- توابعی مثل SHA-256 که در امنیت اطلاعات استفاده می‌شوند.
- این توابع تضمین می‌کنند که حتی تغییرات کوچک در ورودی، تغییرات بزرگی در خروجی ایجاد می‌کند.


کاربردهای توابع هش 💡

- جداول هش (Hash Tables): استفاده از توابع هش برای دسترسی سریع به داده‌ها در جداول هش.
- جستجو و ذخیره‌سازی: در پایگاه‌های داده و سیستم‌های فایل برای مدیریت سریع داده‌ها.
- امنیت اطلاعات: در رمزنگاری و امضای دیجیتال برای تضمین امنیت و صحت داده‌ها.



هشینگ و توابع هش، ابزارهای قدرتمندی برای مدیریت داده‌ها در سیستم‌های مختلف هستند. در بخش‌های آینده، به بررسی ساختار جداول هش و پیاده‌سازی آن‌ها خواهیم پرداخت و خواهیم دید که چگونه می‌توان از هشینگ برای حل مسائل پیچیده‌تر استفاده کرد.



⚠️کلیک کن تا بیشتر یاد بگیری⚠️

#هشینگ #توابع_هش #جداول_هش #برنامه_نویسی #ساختمان_داده #آموزش_پایتون

سری ششم: هشینگ (Hashing) و جداول هش (Hash Tables)
پارت ۲: جداول هش (Hash Tables) 📊

سلام به همه! در این پارت از سری آموزشی، به بررسی جداول هش (Hash Tables) خواهیم پرداخت. این ساختار داده‌ای یکی از سریع‌ترین و کارآمدترین روش‌ها برای ذخیره‌سازی و دسترسی به داده‌هاست. در ادامه، به تعریف جداول هش، نحوه کار آن‌ها و پیاده‌سازی یک نمونه ساده می‌پردازیم.

جدول هش چیست؟ 🤔

جدول هش یک ساختار داده‌ای است که از توابع هش برای نگاشت کلیدها به شاخص‌های یک آرایه استفاده می‌کند. این ساختار داده‌ای به ما امکان می‌دهد تا به سرعت داده‌ها را ذخیره، جستجو و حذف کنیم.

اجزای جدول هش:

1. کلید (Key): عنصری که می‌خواهیم در جدول هش ذخیره یا بازیابی کنیم.
2. مقدار (Value): داده‌ای که با کلید مرتبط است.
3. تابع هش (Hash Function): تابعی که کلید را به یک شاخص (Index) در آرایه نگاشت می‌کند.
4. آرایه (Array): ساختار اصلی که داده‌ها را بر اساس شاخص‌های تولید شده توسط تابع هش ذخیره می‌کند.

نحوه کار جدول هش 🛠️

1. محاسبه شاخص: ابتدا تابع هش، کلید را به یک مقدار عددی (شاخص) تبدیل می‌کند.
2. ذخیره‌سازی مقدار: مقدار مرتبط با کلید در محل شاخص محاسبه شده در آرایه ذخیره می‌شود.
3. دسترسی به مقدار: برای بازیابی مقدار مرتبط با یک کلید، همان تابع هش استفاده می‌شود تا شاخص محاسبه شده و مقدار از آن محل بازیابی شود.

مثال ساده از جدول هش 🌟

فرض کنید می‌خواهیم یک سری داده مثل نام افراد و شماره تلفن آن‌ها را ذخیره کنیم.

- کلید: نام فرد
- مقدار: شماره تلفن

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    
    def hash_function(self, key):
        return len(key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index] = value
    
    def search(self, key):
        index = self.hash_function(key)
        return self.table[index]

# ایجاد جدول هش با اندازه 10
hash_table = HashTable(10)

# درج داده‌ها
hash_table.insert("Alice", "123-4567")
hash_table.insert("Bob", "234-5678")

# جستجو برای داده‌ها
print(hash_table.search("Alice"))  # خروجی: 123-4567
print(hash_table.search("Bob"))    # خروجی: 234-5678

نحوه پیاده‌سازی یک جدول هش ساده 🚀

در این کد، یک کلاس ساده به نام HashTable داریم که یک آرایه با اندازه مشخص (در اینجا 10) برای ذخیره داده‌ها ایجاد می‌کند. تابع هش به سادگی طول کلید را به عنوان شاخص برای ذخیره‌سازی انتخاب می‌کند (که البته در پروژه‌های واقعی باید توابع هش پیچیده‌تر و کارآمدتری استفاده شود).

عملیات پایه‌ای در جدول هش:

1. درج (Insert): تابع insert، کلید و مقدار را دریافت کرده و با استفاده از تابع هش، مقدار را در محل مناسب در جدول ذخیره می‌کند.
2. جستجو (Search): تابع search، کلید را دریافت کرده و مقدار مرتبط با آن را با استفاده از شاخص محاسبه شده از تابع هش بازیابی می‌کند

در پارت بعدی، به بررسی مشکلات و چالش‌های احتمالی در جداول هش مانند برخوردها (Collisions) خواهیم پرداخت و روش‌های مختلفی برای مدیریت این مشکلات ارائه خواهیم داد.

هشینگ و جداول هش یکی از مهم‌ترین و پرکاربردترین مباحث در دنیای برنامه‌نویسی هستند، و درک درست آن‌ها می‌تواند به بهبود عملکرد سیستم‌ها کمک شایانی کند. پس تا پارت بعدی، به تمرین و بررسی بیشتر این مفاهیم بپردازید!

⚠️کلیک کن تا بیشتر یاد بگیری⚠️

#هشینگ #جداول_هش #برنامه_نویسی #ساختمان_داده #آموزش_پایتون

سری ششم: هشینگ (Hashing) و جداول هش (Hash Tables)
پارت ۳: مدیریت برخورد (Collisions) در جداول هش

سلام به همه! در پارت قبلی، با جداول هش و نحوه عملکرد آن‌ها آشنا شدیم. یکی از چالش‌های مهم در جداول هش، برخوردها (Collisions) هستند. در این پارت، به بررسی مفهوم برخورد، علت وقوع آن و روش‌های مختلف مدیریت برخورد خواهیم پرداخت.

برخورد (Collision) چیست؟ 🤔

برخورد زمانی رخ می‌دهد که تابع هش، دو کلید مختلف را به یک شاخص مشابه در جدول هش نگاشت می‌کند. در نتیجه، هر دو مقدار مرتبط با این کلیدها باید در یک مکان از آرایه ذخیره شوند که این امر باعث ایجاد مشکل می‌شود.

چرا برخورد رخ می‌دهد؟
1. محدودیت اندازه جدول: اندازه جدول هش معمولاً محدود است و تابع هش نمی‌تواند برای هر کلید یک شاخص منحصربه‌فرد تولید کند.
2. طبیعت تابع هش: تابع هش ممکن است برای کلیدهای مختلف، مقادیر شاخص مشابهی تولید کند.

روش‌های مدیریت برخورد 🛠️

برای حل مشکل برخورد، چندین روش وجود دارد. در این بخش، به دو روش پرکاربرد یعنی زنجیره‌سازی (Chaining) و جستجوی خطی (Linear Probing) خواهیم پرداخت.

روش اول: زنجیره‌سازی (Chaining) 🔗

در روش زنجیره‌سازی، هر شاخص در جدول هش به یک لیست (یا لیست پیوندی) اشاره می‌کند که تمام مقادیر مرتبط با کلیدهایی که به آن شاخص نگاشت شده‌اند را ذخیره می‌کند.

پیاده‌سازی زنجیره‌سازی:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return len(key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index].append((key, value))
    
    def search(self, key):
        index = self.hash_function(key)
        for kvp in self.table[index]:
            if kvp[0] == key:
                return kvp[1]
        return None

# ایجاد جدول هش با زنجیره‌سازی
hash_table = HashTable(10)

# درج داده‌ها
hash_table.insert("Alice", "123-4567")
hash_table.insert("Bob", "234-5678")
hash_table.insert("Charlie", "345-6789")

# جستجو برای داده‌ها
print(hash_table.search("Alice"))  # خروجی: 123-4567
print(hash_table.search("Bob"))    # خروجی: 234-5678
print(hash_table.search("Charlie"))  # خروجی: 345-6789

در این کد، هر شاخص در آرایه به یک لیست اشاره می‌کند که کلید و مقدار را به صورت جفت (Key-Value) ذخیره می‌کند. این روش به خوبی می‌تواند برخوردها را مدیریت کند.

روش دوم: جستجوی خطی (Linear Probing) 🔍

در روش جستجوی خطی، اگر یک برخورد رخ دهد، الگوریتم به دنبال اولین شاخص خالی در آرایه می‌گردد و مقدار جدید را در آنجا ذخیره می‌کند.

پیاده‌سازی جستجوی خطی:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    
    def hash_function(self, key):
        return len(key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
            index = (index + 1) % self.size
        self.table[index] = (key, value)
    
    def search(self, key):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
        return None

# ایجاد جدول هش با جستجوی خطی
hash_table = HashTable(10)

# درج داده‌ها
hash_table.insert("Alice", "123-4567")
hash_table.insert("Bob", "234-5678")
hash_table.insert("Charlie", "345-6789")

# جستجو برای داده‌ها
print(hash_table.search("Alice"))  # خروجی: 123-4567
print(hash_table.search("Bob"))    # خروجی: 234-5678
print(hash_table.search("Charlie"))  # خروجی: 345-6789

در این کد، اگر یک شاخص پر باشد، به سادگی به شاخص بعدی در آرایه می‌رود تا یک مکان خالی پیدا کند. این روش نیز یکی از متداول‌ترین روش‌ها برای مدیریت برخوردها است.

مزایا و معایب روش‌ها ⚖️

1. زنجیره‌سازی:
- مزایا: مدیریت ساده‌تر برخوردها، ظرفیت نامحدود (تا حدی).
- معایب: استفاده بیشتر از حافظه به دلیل لیست‌های اضافی.

2. جستجوی خطی:
- مزایا: استفاده بهینه‌تر از حافظه، ساده در پیاده‌سازی.
- معایب: ممکن است منجر به خوشه‌بندی (Clustering) شود که کارایی جستجو را کاهش می‌دهد.