در این جلسه تیم کدگیت را با آموزش درخت جستجوی دودویی در پایتون همراهی کنید. ابتدای این جلسه درخت جستجوی دودویی در پایتون را معرفی سپس عملیات‌هایی مانند درج و حذف گره را توضیح میدهیم. در پایان یک پیاده سازی کامل از این درخت جستجو را انجام خواهیم داد. پیش نیاز این جلسه شامل موارد زیر است:
- آشنایی با توابع
- آشنایی با if
- آشنایی با for
- آشنایی با while
- آشنایی با شی گرایی
درخت جستجوی دودویی
درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:
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)
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
80 node deleted from Tree
Print Tree after Delete 80 node:
20
30
40
50
60
70
اگر سوالی در خصوص درخت جستجوی دودویی دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.
