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

  1. آشنایی با توابع
  2. آشنایی با if
  3. آشنایی با for
  4. آشنایی با while
  5. آشنایی با شی گرایی

درخت جستجوی دودویی

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

    1- مقادیر تمامی گره‌های زیردرخت راست از مقدار گره بزرگتر هستند.

    2- مقادیر تمامی گره‌های زیردرخت چپ از مقدار گره کوچکتر هستند.

درخت جستجوی دودویی در پایتون

درج گره جدید در درخت جستجوی دودویی

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

درخت جستجوی دودویی در پایتون

حذف گره از درخت جستجوی دودویی

حذف گره از درخت جستجوی دودویی به سه طریق انجام می‌گیرد:

1.گره برگ باشد که به راحتی قابل حذف از درخت می‌باشد

درخت جستجوی دودویی در پایتون

2.گره ما یک فرزند دارد. در این صورت گره حذف و فرزند آن جایگزین می‌شود.

درخت جستجوی دودویی در پایتون

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

درخت جستجوی دودویی در پایتون

پیاده سازی درخت جستجوی دودویی در پایتون

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

class Node: 
  
    # Constructor to create a new node 
    def __init__(self, key): 
        self.key = key  
        self.left = None
        self.right = None

 کلاس Node شامل سه فیلد key و left و right است. بعد از ساخت هر گره نیاز به ساخت درخت است که ما کلاس BinarySearchTree را برای این کار در نظر گرفتیم.

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

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

کد درج در درخت جستجوی دودویی

برای درج در درخت ابتدا باید به محلی برویم که میتوان گره را در آن قرار داد. توابع insert و insetRec برای درج در درخت است و کد آن به صورت زیر است.

def insert(self, data):
        self.root = self.insertRec(self.root, data);
        
    def insertRec(self,root, data):
        if root is None: 
            root = Node(data)
            return root
        if data<root.key:
            root.left = self.insertRec(root.left, data);
        elif data>root.key:
            root.right = self.insertRec(root.right, data);
        
        return root;

همانطور که از کد درخت جستجوی دودویی در پایتون  پیداست ابتدا چک میکنیم درخت ما خالی است یا خیر! اگر خالی بود ما ریشه را میسازیم.

if self.root is None: 
            self.root = Node(data)

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

کد حذف گره در درخت جستجوی دودویی

برای حذف همانطور که گفته شد ما باید سه مرحله را طی کنیم. مرحله اول آن است که ما گره ای بدون فرزند را بخواهیم حذف کنیم و مرحله دو اگر یک فرزند داشته باشد و مرحله سه اگر دو فرزند داشته باشد. تابع delete کد حذف را در سه مرحله به ما نشان میدهد.

def findsuccessor(self, current_node):
        while current_node.left != None:
            current_node = current_node.left
        return current_node
    
    def deleteNode(self, root, key): 
  
        # Base Case 
        if root is None: 
            return root  
      
        # If the key to be deleted is smaller than the root's 
        # key then it lies in  left subtree 
        if key < root.key: 
            root.left = self.deleteNode(root.left, key) 
      
        # If the kye to be delete is greater than the root's key 
        # then it lies in right subtree 
        elif(key > root.key): 
            root.right = self.deleteNode(root.right, key) 
      
        # If key is same as root's key, then this is the node 
        # to be deleted 
        else: 
              
            # Node with only one child or no child 
            if root.left is None : 
                return root.right  
                  
            elif root.right is None : 
                return root.left 
      
            # Node with two children: Get the inorder successor 
            # (smallest in the right subtree) 
            temp = self.findsuccessor(root.right) 
      
            # Copy the inorder successor's content to this node 
            root.key = temp.key 
      
            # Delete the inorder successor 
            root.right = self.deleteNode(root.right , temp.key) 
      
        return root  
    
    def delete(self, key): 
        return self.deleteNode(self.root, key)

همانطور که در کد میبینید ما ابتدا بررسی میکنیم آیا گره ای که میخواهیم وجود دارد یا خیر! در صورت درستی سه قسمتی که در قسمت حذف یک گره توضیح داده شد را انجام میدهیم

پیمایش درخت جستجوی دودویی

در این قسمت ما پیمایش inorder در درخت جستجوی دودویی را پیاده سازی خواهیم کرد. این پیمایش به این صورت است که ابتدا فرزند چپ یک گره را چاپ و بعد خود گره و در آخر فرزند راست گره را چاپ می‌کند. در درخت جستجو دودویی اگر از پیمایش inorder استفاده کنیم گره ها به صورت کوچک به بزرگ نمایش داده می‌شوند(چرا؟). برای پیاده سازی این پیمایش ما از روش بازگشتی استفاده کردیم. کد این پیمایش به صورت زیر است:

def inorder(self, root): 
        if root is not None: 
            self.inorder(root.left) 
            print(root.key) 
            self.inorder(root.right)

تست برنامه درخت جستجوی دودویی

برای اجرای برنامه بالا، کد زیر را بزنید:

if __name__ == '__main__':
    bst = BinarySearchTree()
    print("insert 50 30 20 40 70 60 80:")
    bst.insert(50)
    bst.insert(30) 
    bst.insert(20) 
    bst.insert(40) 
    bst.insert(70) 
    bst.insert(60) 
    bst.insert(80)
    print("inorder Permutation:")
    bst.inorder(bst.root)
    search = 80
    print('search for 80 Node:')
    if bst.search(bst.root, search) is None:
        print(search, ' is not exist in tree')
    else:
        print(search, ' is in tree')
    bst.delete(80)
    print("80 node deleted from Tree")   
    print("Print Tree after Delete 80 node:")
    bst.inorder(bst.root)

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

insert 50 30 20 40 70 60 80:

inorder Permutation:

20

30

40

50

60

70

80

search for 80 Node:

80  is in tree

80 node deleted from Tree

Print Tree after Delete 80 node:

20

30

40

50

60

70

اگر سوالی در خصوص درخت جستجوی دودویی دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.

Download “دانلود سورس درخت جستجوی دودویی در پایتون” BST-in-Python-www.codegate.ir_.zip – 171 بار دانلود شده است – 2 کیلوبایت

پسورد: www.codegate.ir