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

صفحه 1:
Tree Sort 

صفحه 2:
درخت جستجوی دودویی(7۶ ‎(Birary Gearck‏ درخت جستجوی دودویی یک درخت دودویی است که ممکن است تهی باشد. اگر تهی نباشد دارای خاصیت زیر است: مقدار هر گره بزرگتر از هر مقدار در زیر درخت چپ و کوچکتر از هر مقدار در زیر درخت راست آن می باشد. هر گره دارای یک کلید است و دو گره نباید دارای کلید یکسان باشند(کلیدها منحصر به فردهستند). 

صفحه 3:
در شکلهای زیر: شکل الف /969) نیست چرا که فرزند راست گره © (يعنى 40) از آن کوچکتر است در حالی که باید بزرگتر باشد. شکل ب یک درخت /009) می باشد. (9 \ OD 9 0۰ {Oo 6 © oy (2) (8) € ia) 

صفحه 4:
جستجوی یک عنصر در “06084 فرض كنيد بخواهيم دنبال عنصرى با كليد « بكرديم . ابتدا از ريشه شروع می کنیم .اگر ريشه تهی باشد» درخت جستجو فاقد هر عنصرى بوده و جستجو ناموفق خواهد بود. در غیر اين صورتء « را با مقدار کلید ريشه مقایسه می کنیم. اگرم« کمتر از مقدار کلبد ريشه باشد» زیر درخت چپ را جستجو می کنیم. اگر >« بزرگتر از مقدار کلید ريشه باشد آنگاه زیر درخت راست را جستجو می کنیم. در زیر الگوریتم جستجو را بیان می کنیم: 

صفحه 5:
صر م06 :)دهاز مسا تلم -ه00)ر مس ملاسما B (<> al) bea bes Prana PROO he B skal) > a thew Prannl 2= perch ‏اس‎ ‎the P sks) <iche Search (Rohde ((), x); ‏اس‎ 

صفحه 6:
اگر | ارتفاع یا عمق یک درخت جستجوی دودویی باشد» با استفاده از ‎peak ati‏ مى توانيم عمل جستجو را در ()0) انجام دهيم. البته در روش بازكشتى به يك يشته اضافى به ميزان (0)1 نياز خواهيم داشت. 

صفحه 7:
اضافه کردن یک عنصر به ‎MGT‏ ‏برا ى درج عنصر جديد مه بايد ابتدا مشخص نمود كه آيا اين عنصر با عناصر موجود متفاوت مى باشد يا خير. براى انجام اين كار بايد درخت را جستجو کرد. اگر جستجو ناموفق باشد پس ما عنصر را در محلى كه جستجو خاتمه پیدا کرده است درج می کنیم. بنابراین الگوریتم اضافه کردن شبیه الگوریتم جستجو است و برای این کار باید به انتهای الگوریتم جستجو خط زير را اضافه کنیم: (ور 2( ‎(aot Pouerd ) thea fesert‏ از 

صفحه 8:
تابع ‎tment‏ به صورت زیر است: ‎toteyer | 4 BON pvicter)‏ :كد ) موود ملد ‎jOw | OGD pvicter‏ ‎rca‏ ‎sew (1); cdata(!) = x ‎boi ():=<l; Robe (1):=cil ‎(data (g) > x) thea ‏0(:<۱) لاسرا ‎thea‏ (« > (واصعل) ۳ سعاد ‎۳0۸۹)۰(:<۱ ‎{ud 

صفحه 9:
Tree Gort od os Gis ‏برای مرتب سازی‎ OGT ‏در اين روش از درختهای جستجوی دودویی‎ ‏لس پیمایش شود‎ Gy 2 42 DGD ‏استفاده می شود. اگر درخت‎ ‏دنباله حاصل به صورت صعودی مرتب خواهد شد.‎ ‏در این الگوریتم ابتدا عناصر آرایه یک به یک داخل یک درخت‎ ‏که در ابتدا تهی است درج می کنیم. سپس همزمان با پیمایش این‎ BGT ‏درخت. عناصر پیمایش شده را در یک آرایه قرار می دهیم تا مرتب‎ 5 

صفحه 10:
Oo €0,80,S0,99,96,0 29 © © © © © 9 40 3 0 9 0 0 9 0 < و oo 11 

صفحه 11:
بدترین حالت حالت مت متوسط بهترین حالت (WO) Si Geis) | ‏وت‎ 0 

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

صفحه 13:
حذف یک عنصر از ‎BGM‏ حذف یک عنصر از 909۳) نسبتا دشوارتر از درج آن است. زیرا وقتی گره ای حذف می شود که دارای فرزند است باید گره دیگری انتخاب شود تا جایگزین گره حذف شده شود. اگر اين انتخاب درست انجام نشود خواص ‎BOM‏ نقض می شود. كره اى كه بايد حذف شود ابتدا در “0008/4 جستجو مى شود سپس به نحوى جايكزين مى شود كه خواص درخت حفظ شود. 

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

صفحه 15:


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

صفحه 17:
حالت. فرزند راست گره ای که باید حذف شود فرزند چپی ندارد. بنابراین فرزند راست جایگزین آن می شود. ۱ x fe © Lo 6 0( 98 175 

صفحه 18:
حالت(),فرزند راست گره ای که باید حذف شود فرزند چپ دارد. در این حالت چپ ترین فرزند راست گره جایگزین آن می شود. یعنی کوچکترین مقدارزیر درخت راست گره. برای مثال اگر بخواهیم گره 00 را حذف کنیم چپ ترین فرزند راست آن یعنی 00 را حذف می کنیم. 

صفحه 19:


صفحه 20:
ييمايش جل به صورت زیر است: AROS ,99,FF,80,O0,00,79 9 بنابراین گره 00 که بعد از 00 ظاهر می شود را جانشین گره 00 می کنیم. پعنی ابتدا گره 00 را حذف کرده(بنا به حالت ب) و سپس آن را جای 00 قرار می دهیم. ۱0 © (ه و ‘(o 0) Xoo), (04) 

صفحه 21:
جانشینی گره 00 به جای 06 در حافظه تنها چم رف با تغییر اشاره گرها انجام می شود و نه با جا به جایی محتوای یک گره از یک مکان ‎(PY‏ ‏9 ‏به مکان دیگر. البته بجای گره 00 می توانیم گره 05 را جانشی( 5 ‎CS‏ کنیم. در نتیجه درخت 907) حاصل از عمل حذف یکتا نمی باشد. ‎)6 ۵( 

صفحه 22:
عمل حذف می تواند در زمان (6)() انجام گیرد که | عمق درخت ‎ash‏ ‏در یک درخت “90984 با ارتفاع متوسط ‎boy ost‏ کوچکترین عنصر را میتوان حذف کرد. 

صفحه 23:
ساختمان دادها حمیدرضا مقسمی ‎wunw. WRK Chsses. ir‏ 

صفحه 24: