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

توضیحات

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