دسته بندی درختان

دسته بندی درختان

اسلاید 1: Tree Sort

اسلاید 2: درخت جستجوی دودویی(Binary Search Tree) درخت جستجوی دودویی یک درخت دودویی است که ممکن است تهی باشد. اگر تهی نباشد دارای خاصیت زیر است: مقدار هر گره بزرگتر از هر مقدار در زیر درخت چپ و کوچکتر از هر مقدار در زیر درخت راست آن می باشد. هر گره دارای یک کلید است و دو گره نباید دارای کلید یکسان باشند(کلیدها منحصر به فردهستند).

اسلاید 3: در شکلهای زیر: شکل الف BST نیست چرا که فرزند راست گره 15 (یعنی 10) از آن کوچکتر است در حالی که باید بزرگتر باشد. شکل ب یک درخت BST می باشد.2015251210305402 (ب)(الف)

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

اسلاید 5: Function search (t: BSTpointer; x:integer):boolean;Var found: boolean;Begin found:=false; if (t<>nill) then begin found=TRUE if data(t) = x then else if data(t) > x then found := search (Lchild(t) , x) else if data(t) < x thenSearch (Rchild (t), x); found := end; Search := found;End;

اسلاید 6: نکته: اگر h ارتفاع یا عمق یک درخت جستجوی دودویی باشد، با استفاده از تابع search می توانیم عمل جستجو را در O(h) انجام دهیم. البته در روش بازگشتی به یک پشته اضافی به میزان O(h) نیاز خواهیم داشت.

اسلاید 7: اضافه کردن یک عنصر به BST برا ی درج عنصر جدید x، باید ابتدا مشخص نمود که آیا این عنصر با عناصر موجود متفاوت می باشد یا خیر. برای انجام این کار باید درخت را جستجو کرد. اگر جستجو ناموفق باشد پس ما عنصر را در محلی که جستجو خاتمه پیدا کرده است درج می کنیم. بنابراین الگوریتم اضافه کردن شبیه الگوریتم جستجو است و برای این کار باید به انتهای الگوریتم جستجو خط زیر را اضافه کنیم: if (not found ) then insert (x ,q);

اسلاید 8: تابع insert به صورت زیر است:Procedure insert ( x: integer ; q: BSTpointer);Var t: BSTpointer;Begin new (t); data(t) := x; Lchild (t):=nil; Rchild (t):=nil; if (data (q) > x) then Lchild (q):=t else if (data(q) < x) then Rchild(q):=t;End;

اسلاید 9: مرتب سازی درختی Tree Sort در این روش از درختهای جستجوی دودویی BST برای مرتب سازی استفاده می شود. اگر درخت BST به صورت inorder پیمایش شود، دنباله حاصل به صورت صعودی مرتب خواهد شد. در این الگوریتم ابتدا عناصر آرایه یک به یک داخل یک درخت BST که در ابتدا تهی است درج می کنیم. سپس همزمان با پیمایش این درخت، عناصر پیمایش شده را در یک آرایه قرار می دهیم تا مرتب شوند.

اسلاید 10: 40,60,50,33,55,114060 > 406050 > 4050 < 605033 < 403355 > 4055 < 6055 > 505511 < 4011 < 3311113340505560

اسلاید 11:

اسلاید 12: نکته مهم آن است که اگر اعداد داده شده با ترتیب مختلفی داده شده باشند، آن گاه درختهای حاصل ممکن است با هم فرق می کنند و عمق مختلفی داشته باشند.

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

اسلاید 14: حالت 1. گره ای که باید حذف شود برگ باشد و فرزندی نداشته باشد. در این حالت حذف به سادگی انجام می پذیرد و کافی است اشاره گر والد برابر تهی شود.

اسلاید 15: 90509520525905095205

اسلاید 16: حالت 2.گره ای باید حذف شود تنها دارای یک فرزند چپ است که می تواند جایگزین آن شود. 90509520525909520525

اسلاید 17: حالت3. فرزند راست گره ای که باید حذف شود فرزند چپی ندارد. بنابراین فرزند راست جایگزین آن می شود.905015020125175140905017520125140

اسلاید 18: حالت4.فرزند راست گره ای که باید حذف شود فرزند چپ دارد. در این حالت چپ ترین فرزند راست گره جایگزین آن می شود. یعنی کوچکترین مقدارزیر درخت راست گره. برای مثال اگر بخواهیم گره 50 را حذف کنیم چپ ترین فرزند راست آن یعنی 66 را حذف می کنیم.

اسلاید 19: 905015020575668090661502057580

اسلاید 20: پیمایش inorder به صورت زیر است:15,25,33,44,50,60,66,75.بنابراین گره 33 که بعد از 25 ظاهر می شود را جانشین گره 25 می کنیم.یعنی ابتدا گره 33 را حذف کرده(بنا به حالت ب) و سپس آن را جای 25 قرار می دهیم.6025751550663344

اسلاید 21: جانشینی گره 33 به جای 25 در حافظه تنها با تغییر اشاره گرها انجام می شود و نه با جا به جایی محتوای یک گره از یک مکان به مکان دیگر. البته بجای گره 33 می توانیم گره 15 را جانشین 25 کنیم.در نتیجه درخت BST حاصل از عمل حذف یکتا نمی باشد.60337515506644

اسلاید 22: عمل حذف می تواند در زمان O(h) انجام گیرد که h عمق درخت می باشد. در یک درخت BST با ارتفاع متوسط Log 2n، کوچکترین عنصر را میتوان حذف کرد.

اسلاید 23: منبع:ساختمان دادهاحمیدرضا مقسمیwww.HPKClasses.ir

اسلاید 24: تهیه کنندگان: مونا امامیسمانه نوع جواستاد راهنما:استاد کسمایی