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

توضیحات

دروس ساختمان داده و الگوریتم از مهم‌ترین دروس کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی هستند به شمار می‌رود. در جلسه بیست و چهارم درس ساختمان داده استاد طورانی با عنوان «درخت جستجوی دودویی (6)»، دهمین جلسه از فصل چهارم این درس، «درخت‌ها»، ارائه می‌گردد. در پنج جلسه قبل درخت جستجوی دودویی (BST: Binary Search Tree) و خصوصیات و کاربردهای آن، ارتفاع آن و جستجوی ماکزیمم و مینیمم و جستجو (پرس‌وجو) در درخت جستجوی دودویی و الگوریتم‎‌های آن و ساختن درخت جستجوی دودویی (BST) به کمک پیمایش و درج در BST و وضعیت‌های ورودی و عمق (ارتفاع) درخت جستجو و ترتیب ورود کلیدها به درخت BST، حذف از درخت BST، جستجوی گره مابعد (Successor) و ماقبل (Predecessor) در BST، و k بار فراخوانی مکرر تابع succ و Pred، ساختن درخت جستجوی دودویی با n کلید مرتب و دلخواه، درج n کلید در درخت جستجوی تهی، مرتب سازی با درخت جستجوی دودویی و معرفی و مفاهیم اولیه درخت جستجوی دودویی متوازن (AVL) و قرمز-سیاه، OS-TREE یا درﺧﺖ آﻣﺎره ﺗﺮتیبی (Order Statist Tree)، حداقل گره برای درخت با ارتفاع متوازن h و چرخش و دوران در این درخت ها مورد بحث قرار گرفته و ده‌ها تست ارشد و دکترا و دهها مثال و تمرین نیز در این مورد مطرح و حل تشریحی آنها ارائه شد. در این جلسه ابتدا سه تمرین در مورد چرخش و دوران حل می‌شود. سپس متوازن کردن درخت جستجوی دودویی با دوران و چرخش با 11 مثال تدریس شده و 5 تست کنکور ارشد در همین مورد مطرح و حل تشریحی آنها ارائه می‌شود.