پارت ۲: عملیات روی پشته 🧱🔧

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

عملیات‌های پایه‌ای روی پشته 📌

1. **افزودن عنصر (push)** 🔼

عملیات push عنصری را به بالای پشته اضافه می‌کند. این عنصر بعداً به عنوان اولین عنصر در زمان pop حذف خواهد شد.

   def push(self, item):
       self.stack.append(item)
   

پیچیدگی زمانی:ی:**
عملیات push با استفاده از لیست در پایتون دارای پیچیدگی زمانی O(1) است، زیرا افزودن یک عنصر به انتهای لیست زمان ثابتی می‌برد.

2. **حذف عنصر (pop)** 🔽

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

   def pop(self):
       if not self.is_empty():
           return self.stack.pop()
       else:
           return "Stack is empty"
   

**پیچیدگی زمانی:**
عملیات pop نیز با پیچیدگی زمانی O(1) انجام می‌شود، زیرا حذف عنصر از انتهای لیست زمان ثابتی مشاهده عنصر بالای پشته (peek)شته (peek)** 👀

عملیات peek بدون حذف، عنصری که در بالای پشته قرار دارد را بازمی‌گرداند. این عملیات به شما امکان می‌دهد که ببینید چه عنصری در بالای پشته قرار دارد.

   def peek(self):
       if not self.is_empty():
           return self.stack[-1]
       else:
           return "Stack is empty"
   

**پیچیدگی زمانی:**
عملیات peek نیز با پیچیدگی زمانی O(1) انجام می‌شود، زیرا مشاهده عنصر آخر در لیست نیاز به پیبررسی خالی بودن پشته (isEmpty)پشته (isEmpty)** ❓

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

   def is_empty(self):
       return len(self.stack) == 0
   

**پیچیدگی زمانی:**
این عملیات نیز با پیچیدگی زمانی O(1) انجام می‌شود.

**پیاده‌سازی کامل کلاس پشته** 🛠️

حالا که با عملیات‌های پایه‌ای آشنا شدیم، بیایید کلاس پشته‌ی خود را کامل کنیم:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

**تمرین: بررسی تعادل پرانتزها با استفاده از پشته** 🔄

یکی از کاربردهای پشته، بررسی تعادل پرانتزها در یک رشته است. برای مثال، رشته‌ی "(a + b) * (c + d)" متعادل است، اما "(a + b))" نامتعادل است. بیایید یک تابع برای بررسی این موضوع بنویسیم.

def is_balanced(expression):
    stack = Stack()
    for char in expression:
        if char == '(':
            stack.push(char)
        elif char == ')':
            if stack.is_empty():
                return False
            stack.pop()
    return stack.is_empty()

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

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

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

پارت ۳: معرفی صف (Queue) 🛤️🚶‍♂️

سلام دوستان! 🌟 در این پارت از سری آموزشی، قصد داریم با صف (Queue) و کاربردهای آن در برنامه‌نویسی آشنا شویم. صف یکی از مفاهیم اساسی در ساختمان داده‌ها است که کاربردهای بسیاری در حل مسائل مختلف دارد. بیایید شروع کنیم! 🚀

صف (Queue) چیست؟ 🤔

صف (Queue) یک ساختار داده‌ای است که بر اساس اصل FIFO (First In, First Out) کار می‌کند. به این معنا که اولین عنصری که وارد صف می‌شود، اولین عنصری است که از آن خارج می‌شود.

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

ویژگی‌های کلیدی صف 📌

- FIFO (First In, First Out): اولین عنصری که وارد صف می‌شود، اولین عنصری است که از آن خارج می‌شود.
- دو انتها: صف دو انتها دارد: یک انتها برای اضافه کردن عناصر (پشت صف) و یک انتها برای حذف عناصر (جلوی صف).

کاربردهای صف در برنامه‌نویسی 💻

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

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

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

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

پیاده‌سازی یک صف ساده 🛠️

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

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            return "Queue is empty"

    def front(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

مثال کاربردی 📚

بیایید ببینیم چطور می‌توانیم از این کلاس صف استفاده کنیم:

# ایجاد یک صف
my_queue = Queue()

# اضافه کردن عناصر به صف
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)

# مشاهده عنصر جلوی صف
print("Front element:", my_queue.front())  # خروجی: 10

# حذف عنصر جلوی صف
print("Dequeued element:", my_queue.dequeue())  # خروجی: 10

# بررسی صف پس از حذف
print("Front element after dequeue:", my_queue.front())  # خروجی: 20

# بررسی اندازه صف
print("Queue size:", my_queue.size())  # خروجی: 2

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

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

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

پارت ۴: پیاده‌سازی و عملیات روی صف 🛠️🛤️

سلام دوستان! 🌟 در این پارت از سری آموزشی، به پیاده‌سازی عملی صف و بررسی عملیات‌های مختلف آن می‌پردازیم. همچنین مشکل "صف دایره‌ای" (Circular Queue) را بررسی و پیاده‌سازی خواهیم کرد. بیایید شروع کنیم! 🚀

عملیات‌های پایه‌ای روی صف 📌

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

1. **افزودن عنصر (enqueue)** 🔼

عملیات enqueue یک عنصر جدید را به انتهای صف اضافه می‌کند.

   def enqueue(self, item):
       self.queue.append(item)
   

پیچیدگی زمانی:ی:**
این عملیات دارای پیچیدگی زمانی O(1) است، زیرا افزودن یک عنصر به انتهای لیست زمان ثابتی می‌برد.

2. **حذف عنصر (dequeue)** 🔽

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

   def dequeue(self):
       if not self.is_empty():
           return self.queue.pop(0)
       else:
           return "Queue is empty"
   

**پیچیدگی زمانی:**
این عملیات دارای پیچیدگی زمانی O(n) است، زیرا حذف عنصر از ابتدای لیست نیاز به تغییر مکان همه عناصر بعدمشاهده عنصر جلوی صف (front)صف (front)** 👀

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

   def front(self):
       if not self.is_empty():
           return self.queue[0]
       else:
           return "Queue is empty"
   

**پیچیدگی زمانی:**
این عملیات دارای پیچیدگی زمانی O(1) است، زیرا مشاهده عنصر اول در لیست نیاز به پیبررسی خالی بودن صف (isEmpty)ن صف (isEmpty)** ❓

عملیات isEmpty بررسی می‌کند که آیا صف خالی است یا خیر. اگر صف خالی باشد، True و در غیر این صورت False بازمی‌گرداند.

   def is_empty(self):
       return len(self.queue) == 0
   

**پیچیدگی زمانی:**
این عملیات نیز با پیچیدگی زمانی O(1) انجام می‌شود.

**مشکل صف دایره‌ای (Circular Queue)** 🔄

یک مشکل رایج در صف‌ها این است که وقتی عناصر زیادی به صف اضافه و حذف می‌شوند، ممکن است فضای استفاده نشده در ابتدای لیست باقی بماند. این مشکل می‌تواند باعث اتلاف حاصف دایره‌ای (Circular Queu یک راه‌حل برای این مشکل است. در صف دایره‌ای، انتهای صف به ابتدای آن متصل می‌شود و به این ترتیب می‌توان از فضای آزاد در پیاده‌سازی صف دایره‌ایپیاده‌سازی صف دایره‌ایپیاده‌سازی صف دایره‌ای** 🛠️

برای پیاده‌سازی صف دایره‌ای، نیاز به استفاده از یک لیست با طول ثابت داریم و از دو اشاره‌گر front و rear برای مدیریت موقعیت‌های ابتدا و انتهای صف استفاده می‌کنیم.

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            return "Queue is full"
        elif self.front == -1:  # صف خالی است
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            return "Queue is empty"
        elif self.front == self.rear:  # صف فقط یک عنصر دارد
            temp = self.queue[self.front]
            self.front = self.rear = -1
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
        return temp

    def front_element(self):
        if self.front == -1:
            return "Queue is empty"
        return self.queue[self.front]

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

**مثال کاربردی** 📚

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

# ایجاد یک صف دایره‌ای با اندازه 5
c_queue = CircularQueue(5)

# افزودن عناصر به صف
c_queue.enqueue(10)
c_queue.enqueue(20)
c_queue.enqueue(30)
c_queue.enqueue(40)

# مشاهده عنصر جلوی صف
print("Front element:", c_queue.front_element())  # خروجی: 10

# حذف عناصر از صف
print("Dequeued element:", c_queue.dequeue())  # خروجی: 10
print("Dequeued element:", c_queue.dequeue())  # خروجی: 20

# افزودن عنصر جدید به صف
c_queue.enqueue(50)

ادامه کد بالا☝️☝️

# بررسی جلوی صف پس از عملیات
print("Front element after dequeue:", c_queue.front_element())  # خروجی: 30

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

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

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

پارت ۵: صف‌های اولویت‌دار و پیاده‌سازی آن‌ها 🎯🚦

سلام دوستان! 🌟 در این پارت از سری آموزشی، به بررسی صف‌های اولویت‌دار (Priority Queue) و نحوه پیاده‌سازی آن‌ها می‌پردازیم. صف‌های اولویت‌دار یکی از مفاهیم مهم در الگوریتم‌ها و برنامه‌نویسی هستند که در مدیریت داده‌های حساس به اولویت بسیار کاربرد دارند. بیایید شروع کنیم! 🚀

صف اولویت‌دار (Priority Queue) چیست؟ 🤔

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

برای مثال، در یک سیستم اورژانس پزشکی، بیماران بر اساس شدت بیماری‌شان درمان می‌شوند، نه بر اساس زمان ورودشان به بیمارستان. بیمار با شرایط بحرانی‌تر اولویت بالاتری دارد و زودتر درمان می‌شود.

ویژگی‌های صف اولویت‌دار 📌

- اولویت: هر عنصر در صف اولویت‌دار دارای یک مقدار اولویت است. هر چه مقدار اولویت کمتر باشد، اولویت آن عنصر بیشتر است.
- ترتیب خروج: عنصری که دارای بالاترین اولویت (کمترین مقدار اولویت) است، زودتر از صف خارج می‌شود.

کاربردهای صف‌های اولویت‌دار 💻

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

1. الگوریتم‌های مسیریابی: در الگوریتم‌هایی مانند دیکسترا، صف‌های اولویت‌دار برای پیدا کردن کوتاه‌ترین مسیر استفاده می‌شوند.
2. زمان‌بندی پردازنده: سیستم‌های عامل از صف‌های اولویت‌دار برای مدیریت فرآیندها استفاده می‌کنند تا فرآیندهای با اولویت بالاتر زودتر اجرا شوند.
3. مدیریت وظایف: در سیستم‌های مدیریت پروژه و صف‌های وظایف، از صف‌های اولویت‌دار برای ترتیب‌دهی و مدیریت وظایف بر اساس اهمیت استفاده می‌شود.

پیاده‌سازی صف اولویت‌دار 🛠️

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

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)[0]
        else:
            return "Queue is empty"

    def front(self):
        if not self.is_empty():
            return self.queue[0][0]
        else:
            return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

مثال کاربردی 📚

بیایید ببینیم چطور می‌توانیم از این صف اولویت‌دار استفاده کنیم:

# ایجاد یک صف اولویت‌دار
pq = PriorityQueue()

# اضافه کردن عناصر با اولویت‌های مختلف
pq.enqueue('Task 1', 2)
pq.enqueue('Task 2', 1)
pq.enqueue('Task 3', 3)

# مشاهده عنصر جلوی صف (با بالاترین اولویت)
print("Front element:", pq.front())  # خروجی: Task 2

# حذف عنصر با بالاترین اولویت
print("Dequeued element:", pq.dequeue())  # خروجی: Task 2

# مشاهده عنصر جلوی صف پس از حذف
print("Front element after dequeue:", pq.front())  # خروجی: Task 1

پیچیدگی زمانی صف اولویت‌دار ⏱️

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

- **پیچیدگی زمانی enqueue:** در بدترین حالت O(n log n) است (با توجه به مرتب‌سازی).
- **پیچیدگی زمانی dequeue:** به دلیل اینکه عنصر اول را برمی‌داریم، این عملیات در O(1) انجام می‌شود.

برای بهبود پیچیدگی زمانی، می‌هیپ‌ها (Heaps) برای پیاده‌سازی صف‌های اولویت‌دار استفاده کرد که در آن زمان درج و حذف هر دو O(log n) است.


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

👈اینم لینک کانال منه 👉

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

پارت ۶: پروژه عملی: مدیریت سفارشات یک فروشگاه آنلاین 🛒💻

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

تعریف مسئله 📋

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

جزئیات پیاده‌سازی 🛠️

ما نیاز به دو ساختمان داده داریم:
- صف اولویت‌دار (Priority Queue): برای مدیریت سفارشات بر اساس اولویت.
- پشته (Stack): برای ذخیره آخرین سفارش ثبت شده جهت دسترسی سریع.

کدنویسی پروژه 💻

ابتدا باید کلاس‌های مربوط به صف و پشته را ایجاد کنیم.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)[0]
        else:
            return "Queue is empty"

    def front(self):
        if not self.is_empty():
            return self.queue[0][0]
        else:
            return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

مدیریت سفارشات 🛒

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

class OrderManager:
    def __init__(self):
        self.orders = PriorityQueue()
        self.recent_orders = Stack()

    def add_order(self, order_id, priority):
        self.orders.enqueue(order_id, priority)
        self.recent_orders.push(order_id)
        print(f"Order {order_id} added with priority {priority}")

    def process_order(self):
        if not self.orders.is_empty():
            order_id = self.orders.dequeue()
            print(f"Processing order {order_id}")
        else:
            print("No orders to process")

    def show_recent_order(self):
        recent_order = self.recent_orders.peek()
        print(f"Most recent order: {recent_order}")

# مثال استفاده از OrderManager
manager = OrderManager()

# اضافه کردن سفارشات
manager.add_order('Order_001', 3)
manager.add_order('Order_002', 1)
manager.add_order('Order_003', 2)

# نمایش آخرین سفارش ثبت شده
manager.show_recent_order()  # خروجی: Order_003

# پردازش سفارشات
manager.process_order()  # خروجی: Order_002
manager.process_order()  # خروجی: Order_003
manager.process_order()  # خروجی: Order_001

شرح پروژه 📑

1. اضافه کردن سفارشات:
- هر سفارش شامل یک شناسه (ID) و یک اولویت است.
- سفارشات به صف اولویت‌دار اضافه می‌شوند و بر اساس اولویت مرتب می‌گردند.
- همچنین سفارشات در پشته ذخیره می‌شوند تا بتوان آخرین سفارش ثبت شده را مشاهده کرد.

2. پردازش سفارشات:
- سفارشات بر اساس اولویت از صف خارج می‌شوند.
- سفارش با اولویت بالاتر (مقدار کمتر) زودتر پردازش می‌شود.

3. نمایش آخرین سفارش:
- با استفاده از پشته، می‌توان آخرین سفارش ثبت شده را به راحتی مشاهده کرد.


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

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

اینم لینک کانال منه روش کلیک کن تا بیشتر یاد بگیری

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

☝️☝️سری سوم آموزش ساختمان داده: پشته (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 #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده