درخت جستجوی دودویی (4)

توضیحات

دروس ساختمان داده و الگوریتم از مهم‌ترین دروس کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی هستند به شمار می‌رود. در جلسه بیست و دوم درس ساختمان داده استاد طورانی با عنوان «درخت جستجوی دودویی (4)»، هشتمین جلسه از فصل چهارم این درس، «درخت‌ها»، ارائه می‌گردد. در سه جلسه قبل درخت جستجوی دودویی (BST: Binary Search Tree) و خصوصیات و کاربردهای آن، ارتفاع آن و جستجوی ماکزیمم و مینیمم و جستجو (پرس‌وجو) در درخت جستجوی دودویی و الگوریتم‎‌های آن و ساختن درخت جستجوی دودویی (BST) به کمک پیمایش و درج در BST و وضعیت‌های ورودی و عمق (ارتفاع) درخت جستجو و ترتیب ورود کلیدها به درخت BST، حذف از درخت BST، جستجوی گره مابعد (Successor) و ماقبل (Predecessor) در BST مورد بحث قرار گرفته و ده‌ها تست ارشد و دکترا نیز در این مورد مطرح و حل تشریحی آنها ارائه شد. در این جلسه، k بار فراخوانی مکرر تابع succ و Pred تدریس شده و سپس 5 تست ارشد و دکترا در مورد BST مطرح و حل تشریحی آن ارائه می‌گردد. سپس ساختن درخت جستجوی دودویی با n کلید مرتب و دلخواه به طور جداگانه شرح داده می‌شود و درج n کلید در درخت جستجوی تهی با چندین مثال مورد بحث قرار می‌گیرد. پس از آن 4 تست ارشد و دکترا در این مورد مطرح و حل تشریحی آن ارائه می‌گردد. سپس مرتب سازی با درخت جستجوی دودویی ارائه می‌گردد. آنگاه نوبت به مبحث درخت جستجوی دودویی متوازن (AVL) و قرمز-سیاه می‌رسد و با معرفی این درخت ها دو تست کنکور ارشد و دکترا در مورد آنها مطرح و حل تشریحی آنها ارائه می‌گردد.