پارت ۴: عملیات پایه روی لیست‌های پیوندی تک‌پیوندی 🔄🔗

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

۱. درج (Insertion) در لیست پیوندی ✏️

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

پیچیدگی زمانی:
- درج در ابتدای لیست O(1) است.
- درج در انتهای لیست O(n) است (زیرا باید تا انتهای لیست پیمایش کنیم).
- درج در وسط لیست O(n) است (زیرا باید محل دقیق درج را پیدا کنیم).

مثال کد:

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def insert_after(self, prev_node, data):
        if prev_node is None:
            print("Previous node must be in the list.")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

ll = LinkedList()
ll.insert_at_beginning(10)
ll.insert_at_end(20)
ll.insert_after(ll.head, 15)  # درج 15 بعد از نود 10
ll.display()  # خروجی: 10 -> 15 -> 20 -> None

۲. حذف (Deletion) از لیست پیوندی ❌

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

پیچیدگی زمانی:
- حذف از ابتدای لیست O(1) است.
- حذف از انتهای لیست O(n) است.
- حذف از وسط لیست O(n) است.

مثال کد:

class LinkedList:
    def delete_node(self, key):
        current = self.head

        if current and current.data == key:
            self.head = current.next
            current = None
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if current is None:
            return

        prev.next = current.next
        current = None

ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.delete_node(20)  # حذف نود با مقدار 20
ll.display()  # خروجی: 10 -> 30 -> None

۳. جستجو (Search) در لیست پیوندی 🔍

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

پیچیدگی زمانی: جستجو در لیست پیوندی O(n) است.

مثال کد:

class LinkedList:
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
found = ll.search(20)  # خروجی: True
print("Found 20:", found)

۴. به‌روزرسانی (Update) نود در لیست پیوندی 🔄

به‌روزرسانی به معنای تغییر مقدار یک نود خاص در لیست پیوندی است. برای این کار باید نود مورد نظر را پیدا کرده و داده آن را تغییر دهیم.

پیچیدگی زمانی: به‌روزرسانی O(n) است.

مثال کد:

class LinkedList:
    def update(self, old_data, new_data):
        current = self.head
        while current:
            if current.data == old_data:
                current.data = new_data
                return True
            current = current.next
        return False

ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
updated = ll.update(20, 25)  # تغییر مقدار نود 20 به 25
ll.display()  # خروجی: 10 -> 25 -> 30 -> None

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

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

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

پارت ۵: لیست‌های پیوندی دوپیوندی و حلقوی 🔗🔄

سلام دوستان! 🌟 در پارت پنجم از سری آموزش‌های "آرایه‌ها و لیست‌های پیوندی"، به بررسی دو نوع دیگر از لیست‌های پیوندی، یعنی لیست‌های پیوندی دوپیوندی (Doubly Linked Lists) و لیست‌های پیوندی حلقوی (Circular Linked Lists) می‌پردازیم. این ساختارها در مواقع خاصی می‌توانند بسیار مفید باشند. بیایید شروع کنیم! 🚀

۱. لیست پیوندی دوپیوندی (Doubly Linked List) چیست؟ ↔️

در لیست پیوندی دوپیوندی، هر نود شامل سه بخش است:
1. داده (Data): مقداری که می‌خواهیم ذخیره کنیم.
2. اشاره‌گر به نود قبلی (Prev Pointer): اشاره‌گری که به نود قبلی اشاره می‌کند.
3. اشاره‌گر به نود بعدی (Next Pointer): اشاره‌گری که به نود بعدی اشاره می‌کند.

این ساختار اجازه می‌دهد تا بتوانیم لیست را در هر دو جهت (جلو و عقب) پیمایش کنیم.

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

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

پیاده‌سازی ساده لیست پیوندی دوپیوندی در پایتون:

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None  # اشاره‌گر به نود قبلی
        self.next = None  # اشاره‌گر به نود بعدی

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def display_backward(self):
        current = self.head
        while current.next:
            current = current.next
        while current:
            print(current.data, end=" -> ")
            current = current.prev
        print("None")

# مثال استفاده
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display_forward()  # خروجی: 10 -> 20 -> 30 -> None
dll.display_backward() # خروجی: 30 -> 20 -> 10 -> None

۲. لیست پیوندی حلقوی (Circular Linked List) چیست؟ 🔁

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

مزایا:
- امکان پیمایش بی‌پایان در لیست.
- مناسب برای برنامه‌هایی که به چرخش دائمی نیاز دارند.

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

پیاده‌سازی ساده لیست پیوندی حلقوی در پایتون:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def display(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print(f"Back to {self.head.data}")

# مثال استفاده
cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()  # خروجی: 10 -> 20 -> 30 -> Back to 10

۳. کاربردهای خاص لیست‌های پیوندی دوپیوندی و حلقوی 📊

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


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

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

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

پارت ۶: پروژه عملی ساده 🛠️🎯

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

پروژه: ساخت یک دفترچه تلفن ساده با استفاده از لیست پیوندی 📞📚

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

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

ابتدا کلاس‌های مورد نیاز را تعریف می‌کنیم. شامل کلاس نود (Node) و کلاس لیست پیوندی (LinkedList).

class ContactNode:
    def __init__(self, name, phone_number):
        self.name = name
        self.phone_number = phone_number
        self.next = None

class PhoneBook:
    def __init__(self):
        self.head = None

    def add_contact(self, name, phone_number):
        new_contact = ContactNode(name, phone_number)
        if self.head is None:
            self.head = new_contact
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_contact

    def delete_contact(self, name):
        current = self.head
        prev = None
        while current:
            if current.name == name:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                return True
            prev = current
            current = current.next
        return False

    def search_contact(self, name):
        current = self.head
        while current:
            if current.name == name:
                return current.phone_number
            current = current.next
        return None

    def display_contacts(self):
        current = self.head
        while current:
            print(f"Name: {current.name}, Phone Number: {current.phone_number}")
            current = current.next

مرحله ۲: استفاده از دفترچه تلفن 📝

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

# ایجاد دفترچه تلفن و افزودن تماس‌ها
phone_book = PhoneBook()
phone_book.add_contact("Alice", "123-456-7890")
phone_book.add_contact("Bob", "987-654-3210")
phone_book.add_contact("Charlie", "555-123-4567")

# نمایش تمام تماس‌ها
print("Contacts:")
phone_book.display_contacts()

# جستجوی یک تماس
print("\nSearching for Bob's number:")
number = phone_book.search_contact("Bob")
print(f"Bob's Number: {number}")

# حذف یک تماس
print("\nDeleting Charlie's contact:")
deleted = phone_book.delete_contact("Charlie")
if deleted:
    print("Charlie has been deleted.")
else:
    print("Charlie was not found.")

# نمایش تماس‌ها پس از حذف
print("\nContacts after deletion:")
phone_book.display_contacts()

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

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

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

پارت ۱: معرفی پشته (Stack) 🧱🔄

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

پشته (Stack) چیست؟ 🤔

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

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

ویژگی‌های کلیدی پشته 📌

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

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

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

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

2. ارزیابی و تبدیل عبارات جبری: پشته‌ها برای ارزیابی عبارات جبری (مثل تبدیل عبارات infix به postfix) و تجزیه و تحلیل آن‌ها به کار می‌روند.

3. مدیریت فراخوانی‌های توابع (Function Call 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

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

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

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

# ایجاد یک پشته
my_stack = Stack()

# اضافه کردن عناصر به پشته
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)

# مشاهده عنصر بالای پشته
print("Top element:", my_stack.peek())  # خروجی: 30

# حذف عنصر بالای پشته
print("Popped element:", my_stack.pop())  # خروجی: 30

# بررسی پشته پس از حذف
print("Top element after pop:", my_stack.peek())  # خروجی: 20

# بررسی اندازه پشته
print("Stack size:", my_stack.size())  # خروجی: 2

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

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

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

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

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

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

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