بخش ۱۰: درخت های دودویی

پرسش: یک درخت دودویی داده می شود که یک عبارت ریاضی را به این صورت نشان می دهد: هر گره یک عملگر یا یک مقدار است. عملگر روی حاصل زیر درخت چپ و راست عمل می کند. برنامه ای بنویسید که حاصل عبارت ریاضی مرتبط با درخت دودویی را محاسبه نماید.پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم که آن را درست درک کرده ایم. فرض کنیم که درخت عبارت ریاضی شکل زیر را داریم. این درخت معادل عبارت ریاضی (9-2) * 4 می باشد.


ریشه این درخت عملگر * (ضرب) می باشد. این به آن معناست که حاصل نهایی این عبارت شامل حاصل ضرب زیر درخت چپ (یعنی 4) در حاصل زیر درخت سمت راست می باشد. بنابراین قبل از آنکه بتوانیم حاصل ضرب را حساب کنیم به دانستن حاصل زیر درخت سمت راست نیاز داریم. ریشه زیر درخت سمت راست عملگر – (تفریق) می باشد به این معنا که حاصل این زیر درخت برابر با تفریق زیر درخت های سمت چپ و راست آن (یعنی 2 و 9) خواهد بود. بنابراین حاصل این زیر درخت 2 – 9 = 7- می باشد. با توجه به اینکه اکنون حاصل زیر درخت سمت راست ریشه را داریم می توانیم عملگر ضرب را اعمال نموده و با حاصل نهایی 4*(7-) = 28- می رسیم.

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

.۱- محاسبه مقدار برای ریشه درخت    مشاهده ریشه (عملگر *)
۱.۱ – محاسبه مقدار زیر درخت سمت چپ       
مشاهده مقدار 4 به عنوان ریشه. چون یک عملگر نیست خود مقدار 4 حاصل است.         
۲.۱ – محاسبه مقدار زیر درخت سمت راست              
مشاهده ریشه زیر درخت (عملگر -)                      
۱.۲.۱- محاسبه زیر درخت سمت چپ                               
مشاهده مقدار 2 به عنوان ریشه و برگرداندن آن به عنوان حاصل
  ۲.۲.۱- محاسبه زیر درخت سمت راست        
مشاهده مقدار 9 به عنوان ریشه و برگرداندن آن به عنوان حاصل               
اعمال عملگر – روی حاصل زیر درخت چپ (2) و زیر درخت راست (9) و برگرداندن 7-
    اعمال عملگر * روی حاصل زیر درخت چپ (4) و زیر درخت راست (7-) و برگرداندن 28-

بنابر این اجرای الگوریتم روی درخت مثال پاسخ درست را تولید می کند. سپس شروع به نوشتن برنامه می کنیم. ابتدا نام و پارامتر مناسب برای تابع تعریف می کنیم (خط 1). در ابتدای تابع چک می کنیم که آیا ریشه مقداری تهی است. در این صورت مقدار 0 را بر می گرداند (خط 2 و 3). این کار بخصوص در مواجهه با عملگر تکی منها مفید می باشد. سپس یک دیکشنری از عملگرها تعریف می کنیم. مقدار مربوط به هر عنصر دیکشنری یک تابع است که دو پارامتر می گیرد و عملگر را روی آنها اعمال و حاصل را برمی گرداند (خط 5 تا 8). از این تکنیک به عنوان جایگزینی برای ساختار شرطی متوالی مورد نیاز و تکرار کد مشابه استفاده می کنیم. دو خط آخر برنامه بسیار فشرده است و فراخوانی های بازگشتی در آن انجام می دهیم. در هر بازگشت ریشه یک زیر درخت وارسی می کنیم. اگر مقدار ریشه عملگر (یکی از مقادیر +، -، *، /) نباشد خود مقدار برمی گردانیم. در غیر این صورت حاصل زیر درخت چپ و سپس راست با فراخوانی بازگشتی محاسبه می کنیم و آنگاه عملگر روی آنها برای محاسبه حاصل اعمال می شود (خط 9 و 10).

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

def calc(root):
	if root == None:
		return 0
	
	opt = {"+": lambda x, y: x + y,
		   "-": lambda x, y: x - y,
		   "*": lambda x, y: x * y, 
		   "/": lambda x, y: x / y}
	return opt[root.data](calc(root.left), calc(root.right))\
		   if root.data in opt else root.data

پرسش: برنامه ای بنویسید که مینیمم ارتفاع برگ یک درخت را محاسبه نماید.

پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم که آن را درست فهمیده ایم. درخت زیر را در نظر بگیریم.

یک درخت دودویی که مینیمم ارتفاع برگها آن 2 می باشد. برگ F کمترین ارتفاع را دارد.

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

واقعیت این است که محاسبه مقدار نهایی در برگها تنها مدل فکر کردن در برنامه های بازگشتی نیست. البته در برخی از مسایل از جمله برنامه بازگشتی مربوط به ب.م.م (gcd) از این روش استفاده می شود. اما در بسیاری مسایل دیگر محاسبات نهایی پس از برگرداندن مقادیر محاسبه شده از زیر درخت ها و در گره پدر انجام می شود.برای رسیدن به پیاده سازی تمیزتر باید محاسبات در راه حل کنونی در گره های پدر انجام شوند. باید به این فکر کنیم که چگونه می توان کمترین ارتفاع برگها نسبت به گره پدر را بر اساس مینیمم ارتفاع برگ ها در زیر درخت های سمت چپ و راست آن بدست آورد؟ منظور از مینیمم ارتفاع زیر درخت ها بدون توجه به ارتفاع آنها در درخت پدر است. یعنی اگر زیر درخت تنها یک گره باشد، مینیمم ارتفاع برگها در آن 0 است.

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

این پیمایش از ریشه تا هریک از برگها می رود و همه گره ها را تنها یکبار مشاهده می کند. چنانچه درخت دارای n گره باشد، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.

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

import sys
class Node:
	def __init__(self, value):
		self.value = value
		self.right = None
		self.left  = None

def findMinLeaf(root):
	if not root:
		return -1
	if not root.left and not root.right:
		return 0 
	return min(findMinLeaf(root.left) if root.left else sys.maxint, 
		    findMinLeaf(root.right) if root.right else sys.maxint) + 1





GiottoPress by Enrique Chavez