بی شک یکی از مهم ترین مباحث در دنیا و علوم کامپیوتر بحث ساختمان های داده است . بدون ساختمان های داده نمی توان الگوریتم مدنظر یا الگوریتم بهینه و کارآمد طراحی کرد و بدون الگوریتم نمی توان برنامه نویسی کرد و بدون برنامه نویسی هم نمی توانیم از کامپیوتر استفاده کنیم و مسائل مختلف را حل کنیم . امیدوارم با این جمله زنجیروار اهمیت ساختمان های داده رو درک کرده باشید . این روزا هم شرکت های بزرگ در زمان استخدام برنامه نویس هم مهارت برنامه نویسی و هم مهارت ساختمان های داده و طراحی الگوریتم شما را می سنجند . در واقع تفاوت یه برنامه نویس معمولی با یه برنامه نویس خوب این است که برنامه نویس معمولی صرفا کدزنی بلد است ولی برنامه نویس خوب کسی است که علاوه بر مهارت کدزنی مهارت طراحی الگوریتم های بهینه و کارآمد و همچنین تحلیل آن الگوریتم را دارد . پس اینو فهمیدیم که برای افزایش مهارت حل مسئله و همچنین کار در شرکت های رویایی مان نیازمند یادگیری مباحث پایه علوم کامپیوتر نظیر ساختمان های داده و طراحی الگوریتم هستیم .
خب رسیدیم به اصل مطلب این مقاله یعنی درخت دودویی . درخت دودویی یکی از ساختمان های داده پرکاربرد در علوم کامپیوتر است . شکل زیر را مشاهده کنید .
همان طور که مشاهده میکنید این یک ساختمان داده درخت دودویی است که به هر کدوم از اون دایره ها که درونش عدد نوشته شده گره یا Node گفته می شود و در درخت دودویی یک گره فقط می تواند به 0 یا 1 یا 2 گره دیگر اشاره کند . در غیر این صورت دیگر یک درخت دودویی نیست و ما فقط به آن درخت می گوییم . شکل زیر را ببینید تا بهتر متوجه شوید .
همان طور که مشاهده میکنید گره 4 به 3 گره دیگر اشاره کرده پس این درخت دودویی نیست و ما این را فقط درخت یا Tree می نامیم . یک درخت می تواند به بی نهایت گره دیگر اشاره کند .
خب حالا برگردیم سر درخت دودویی . گره ای که در بالاترین نقطه قرار دارد را گره ریشه یا Root می نامیم .
گره ای که حداقل به یک گره دیگر اشاره میکند را گره والد یا Parent می نامیم .
در اینجا گره 4 گره ریشه و گره والد است .
گره هایی که توسط یک گره دیگر به آن ها اشاره شده است را گره های فرزند یا Child می نامیم. در اینجا گره های 3 ، 23 ، 12 ، 7 ، 14 و 27 گره های فرزند هستند . گره های فرزند می توانند والد هم باشند (مانند گره های 3 و 23) ، گره هایی که والد نیستند و هیچ فرزندی ندارند (به گره دیگری اشاره نمی کنند) برگ نامیده می شوند .
یکی از مهم ترین کاربرد های درخت دودویی در جست و جو کردن است . جست و جو کردن با درخت دودویی گاهی می تواند خیلی سریع انجام شود . به درخت دودویی مخصوص جست و تو می گوییم Binary Search Tree یا به اختصار BST . اما این درخت چگونه عمل می کند؟ فرض کنیم عددی مانند 47 داریم . حال میخواهیم عدد دیگری را اضافه کنیم با این شرط که اگر از 47 بزرگتر بود در سمت راست قرار بگیرد و اگر از 47 کوچک تر بود سمت چپ قرار بگیرد . فرض کنیم آن عدد 76 باشد ، در این صورت طبق شرط این عدد در سمت راست 47 قرار میگیرد .
همان طور که می بینید داریم با استفاده از این کار یک درخت جست و جوی دودویی تشکیل می دهیم . حال عدد دیگری مثل 52 را فرض کنیم . 52 از 47 بزرگتر است پس سمت راست قرار میگیرد اما با عدد 76 نیز باید مقایسه شود و چون از 76 کوچک تر است بنابراین سمت چپ 76 قرار میگیرد . به این شکل :
حال اگر عددی مانند 21 را در نظر بگیریم چون از 47 کوچک تر است سمت چپ درخت قرار میگیرد . حال عدد 82 را در نظر بگیریم . اول از 47 شروع میکنیم ، چون از آن بزرگتر است سمت راست 47 قرار میگیرد. حال با عدد 76 مقایسه میکنیم و چون از 76 بزرگتر است سمت راست 76 قرار می گیرد .
حال عدد 18 و 27 را اگر بخواهیم در این درخت اضافه کنیم ، هر دو از 47 کوچک تر هستند پس به سمت چپ درخت می رویم و عدد 21 را میبینیم و حال آن ها را با 21 مقایسه میکنیم . 18 از 21 کوچکتر است پس سمت چپ قرار میگیرد و 27 از 21 بزرگتر است پس سمت راست قرار میگیرد .
در نهایت درخت جست و جوی ما با این اعداد تکمیل شد و 47 ریشه این درخت است و این درخت را بر اساس شرط بزرگتر یا کوچک تر از 47 (ریشه درخت) مرتب سازی کردیم . حال ببینیم واقعا این درخت چه کمکی به ما می کند . در تحلیل الگوریتم ها مفهومی به نام مرتبه زمانی داریم . میخواهیم ببینیم برای پیدا کردن یک عدد در درخت جست و جوی دودویی مرتبه زمانی چقدر خواهد بود ! بگذارید تعداد گره ها در هر مرحله را به دست بیاوریم . در مرحله اول یک گره داشتیم آن هم 47 بود اما من عدد یک رو می توانیم بنویسیم 1 - 1^2 که نتیجه این عبارت همان عدد 1 خواهد بود .
در مرحله بعد 3 عدد خواهیم داشت که می توانیم بنویسم 1 - 2^2 .
در مرحله بعد 7 عدد خواهیم داشت که می توانیم بنویسیم 1 - 3^2 .
فکر می کنم متوجه شده اید که این درخت با چه الگویی تعدادش بیشتر و بیشتر می شود . حال بیاید بررسی کنیم برای پیدا کردن عدد 47 چند گره باید پیش بریم . طبیعتا جواب 1 است یعنی ما در همان ابتدا عدد 47 را می توانیم پیدا کنیم . حال عدد 76 چطور؟ یک بار عدد 47 را بررسی میکنیم و چون از عدد 47 بزرگتر است به سمت راست رفته و بعد از آن ، آن را پیدا میکنیم یعنی 2 حرکت برای پیدا کردن 76 لازم است . حال عدد 27 چطور ؟ آن هم به همین ترتیب خواهد بود ابتدا 47 سپس چون کوچک تر است به سمت چپ رفته و به عدد 21 میرسیم و چون از 21 بزرگتر است به سمت راست رفته و آن را پیدا میکنیم . در واقع برای پیدا کردن یک عدد در درخت جست و جوی دودویی مرتبه زمانی آن O(Log n) خواهد بود که بسیار سریع و کارآمد است .
فرض کنید میخواهیم عدد 49 را در درخت بالا پیدا کنیم . 49 از 47 بزرگتر است پس به سمت راست میرویم . همین که به سمت راست رفتیم عملا میتونیم بگیم که با نصف دیگر آن درخت کاری نداریم و در واقع درخت را نصف کردیم .
حال با 76 مقایسه میکنیم و چون از آن کوچک تر است به سمت چپ می رویم و باز درخت ما با این ترتیب نصف میشود .
حال آن را با 52 مقایسه میکنیم و چون از آن هم کوچک تر است به سمت چپ می رویم و آن را پیدا میکنیم .
حال فرض کنید اگر درخت ما میلیون ها گره داشت چه اتفاقی می افتاد؟ درست حدس زدید ، مشکلی پیش نمی آید چون ما با هر بار جلو رفتن اندازه درختمان را نصف میکنیم و به همین خاطر است که این روش بسیار سریع و کارآمد است . اما یه مسئله اینجا پیش می آید ، آن هم این است که اگر مثلا همه اعداد از یکدیگر بزرگتر یا کوچک تر بودند چه اتفاقی می افتد ؟ برای درک بهتر این مسئله شکل زیر را ببینید .
در اینجا اعداد همواره بزرگتر از اعداد قبلیشان هستند و در این نمونه هیچ دو شاخه ای به وجود نیامده است . در این حالت برای جست و جوی یک عدد مرتبه زمانی O(n) خواهد بود . در واقع میتوانیم این شکل را یک لیست پیوندی در نظر بگیریم چرا که در آن هیچ دو شاخه ای به وجود نیامده است .
در لیست پیوندی بدترین حالت برای جست و جوی یک عدد مرتبه زمانی O(n) است . پس عملا می توان گفت در یک همچین شرایطی درخت دودویی با یک لیست پیوندی هیچ تفاوتی ندارد . بنابراین مرتبه زمانی درخت جستو جوی دودویی در بهترین حالت و حالت متوسط O(log n) و در بدترین حالت O(n) است .
اولین چیزی که باید پیاده سازی کنیم ، گره های درخت در پایتون است . برای اینکار باید یه کلاس به نام Node در پایتون بسازیم که این کلاس به شکل زیر خواهد بود .
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
حال کلاس BinarySearchTree را خواهیم ساخت که به شکل زیر خواهد بود .
class BinarySearchTree:
def __init__(self, value):
new_node = Node(value)
self.root = new_node
زمانی که یک نمومه از کلاس ساختیم یک مقدار به constructor آن پاس میدهیم تا یک گره از آن مقدار برای ما بسازد . فراموش نکنیم که هر گره نیازمند این است که یک گره دیگر به آن اشاره کند به جز اولین گره که گره ریشه ما است . همین موضوع هم در لیست های پیوندی وجود دارد . اگر قرار است یک لیست پیوندی داشته باشیم ، نیازمند این هستیم که یک چیزی به اولین عنصر لیست اشاره کند ، چون این تنها راهی برای دسترسی به اولین عنصر درون یک لیست پیوندی است . حال برگردیم سراغ درخت ها . پس باید این متغیر گره ریشه را بسازیم . یک کار جالبی میتوان انجام داد . ما میتوانیم مقدار ریشه را None قرار دهیم . در واقع میخواهیم یک درخت خالی بسازیم و زمانی که میخواهیم اولین گره را اضافه کنیم ، میتوانیم با استفاده از متد Insert آن را اضافه کنیم . در واقع زمانی که یک نمونه از درخت میسازیم اولین گره را نیاز نیست به constructor آن پاس بدهیم و میتوانیم آن را با متد Insert اضافه کنیم . پس باید یکمی تغییر در کد بالا ایجاد کنیم ، پس گفتیم نیازی به مقدار اولیه نیست و آن را حذف میکنیم و self.root را برابر None قرار میدهیم .
class BinarySearchTree:
def __init__(self):
self.root = None
حال ببینیم چگونه میتوانیم متد Insert را بسازیم . فرض کنید میخواهیم عدد 27 را به درخت زیر اضافه کنیم .
قاعدتا میدانید که عدد 27 باید سمت راست عدد 21 قرار بگیرد ، اما حال چگونه کدی بنویسیم که تشخیص دهد در کدام موقعیت قرار بگیرد و به درخت اضافه بشود ؟
اولین قدم این است که یک گره جدید ایجاد کنیم . قدم بعدی این است که مقدار آن گره جدید که 27 است را با گره ریشه مقایسه کنیم و اگر گره جدید کوچکتر بود به سمت چپ رفته و اگر بزرگتر بود به سمت راست خواهد رفت . در این مورد خاص ما قطعا باید به سمت چپ برویم . و حال دو مورد پیش می آید ، آیا گره دیگری پس از آن مقایسه مثل گره عدد 21 وجود دارد یا خیر؟ اگر که وجود ندارد خیلی راحت میتوانیم آن را به سمت چپ اضافه کنیم ، پس اگر سمت چپ گره 47 برابر None بود ، آن را اضافه میکنیم . اما اگر آن عدد 21 وجود دارد ، باید دوباره عدد 27 را با 21 مقایسه کنیم . پس در واقع میتوانیم بگوییم که اگر عدد دیگری وجود نداشت (None بود) آن را به آنجا اضافه میکنیم در غیر این صورت به گره بعدی میرویم و دوباره مقایسه را انجام میدهیم . پس در واقع به یک حلقه احتیاج داریم تا این دو شرط را بارها تکرار کند و انجام دهد . به یک متغیر دیگر نیز نیاز داریم که گره ای که میخواهیم در هر مرحله آن را با گره ای که میخواهیم به درخت اضافه کنیم ، مقایسه کنیم . آن را temp می نامیم .
این الگوریتم می تواند برای اضافه کردن به ما کمک خیلی خوبی بکند ولی باید یک سری حالات دیگر را بررسی کنیم تا به مشکل نخوریم . اولین مورد این است که اگر یک درخت خالی داشتیم ، باید گره ریشه را برابر گره جدید قرار دهیم ، پس نیازی به حلقه و متغیر temp نداریم . یک مسئله دیگر هم وجود دارد . فرض کنید میخواهیم گره ای اضافه کنیم که آن گره در درخت ما وجود دارد . چون طبق الگوریتم نوشته شده فقط میتوانیم بزرگتر یا کوچکتر را اضافه کنیم ، باید یک شرط داخل حلقه بگذاریم که اگر گره جدیدی که داریم اضافه میکنیم برابر temp بود ، مقدار False را return کن . الان تمامی شرایط را بررسی کردیم و الگوریتم خودمان را تکمیل کردیم . حال باید این الگوریتم را با پایتون پیاده سازی کنیم (def insert) . (اگر اینجا متوجه متغیر temp نشدید در پیاده سازی متد و الگوریتم بعدی بهتر برای شما متغیر temp را توضیح داده ایم .)
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return True
temp = self.root
while (True):
if new_node.value == temp.value:
return False
if new_node.value < temp.value:
if temp.left is None:
temp.left = new_node
return True
temp = temp.left
else:
if temp.right is None:
temp.right = new_node
return True
temp = temp.right
حال نیاز به متد جست و جو داریم . برای مثال فرض کنیم عدد 27 در درخت ما وجود دارد ، در این صورت متد جست و جو باید مقدار True را return کند . اما اگری عددی مثل 17 در درخت ما وجود نداشت ، متد جست و جو باید مقدار False را return کند .
در گام اول باید ابتدا متوجه بشویم درختمان خالی است یا خیر . اگر خالی بود قاعدتا باید مقدار False را return کنیم . مثل متد Insert ، متغیر temp را نیاز داریم . در ابتدا گفتیم مقدار temp برابر گره ریشه است . فرض کنیم عکس زیر دنبال عدد 27 میگردیم .
چون 27 از temp کوچکتر است به سمت چپ میرویم . اکنون temp عدد 21 می شود . حال 27 از 21 بزرگتر است بنابراین به سمت راست می رویم و بعد از آن temp برابر 27 می شود و چون برابر 27 با temp برابر است یعنی ما عدد 27 را پیدا کردیم . حال مورد دیگری را بررسی میکنیم که در درخت تصویر بالا وجود ندارد مثلا عدد 17، temp در ابتدا برابر گره ریشه است . بنابراین 17 از temp کوچکتر است پس به سمت چپ می رویم ، سپس temp عدد 21 خواهد شد ، چون دوباره 17 از temp کوچکتر است ، به سمت چپ می رویم ، اکنون temp برابر عدد 18 می شود که دوباره از 17 بزرگتر بوده و ما به سمت چپ می رویم ولی چون سمت چپ 18 خالی (None) است بنابراین میتوانیم نتیجه بگیریم که عدد 17 در درخت ما وجود ندارد . در واقع مقدار temp پس از عدد 18 برابر None می شود . پس به یک حلقه احتیاج داریم که تا زمانی که temp برابر None نبود ، حلقه تکرار شود . داخل حلقه 3 شرط داریم ، اگر عددی که دنبالشیم کوچکتر از temp بود ، به سمت چپ می رویم . اگر عددی که دنبالشیم بزرگتر از temp بود ، به سمت راست می رویم و اگر عددی که دنبالشیم برابر temp بود ، True را return کن . اگر مثل عدد 17 ، temp ما برابر None شد ، حلقه خاتمه میابد و در نتیجه چون در درخت عددی مثل 17 نداشتیم ، False را return میکند .
این کل الگوریتم ما برای پیدا کردن یک عدد در یک درخت است . اکنون این الگوریتم را با پایتون پیاده سازی میکنیم (def Search) .
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return True
temp = self.root
while (True):
if new_node.value == temp.value:
return False
if new_node.value < temp.value:
if temp.left is None:
temp.left = new_node
return True
temp = temp.left
else:
if temp.right is None:
temp.right = new_node
return True
temp = temp.right
def Search(self, value):
temp = self.root
while (temp is not None):
if value < temp.value:
temp = temp.left
elif value > temp.value:
temp = temp.right
else:
return True
return False
منابع :
1- Data structures and algorithms in python - Udemy
2- Geekforgeeks - Binary Tree and BST
