بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
درخت جستجوی دودویی - الگوریتمستان
الگوریتمستان
5914.535.00
  »  

       

آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره

درخت دودویی (Binary Tree)

  [بازگشت به فهرست]

    درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

      

    

درخت دودویی

      

درخت جستجوی دودویی (Binary Search Tree - BST)

  [بازگشت به فهرست]

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

    1- مقادیر تمامی گره‌های زیردرخت راست - در صورت وجود - از مقدار گره بزرگتر هستند.

    2- مقادیر تمامی گره‌های زیردرخت چپ - در صورت وجود - از مقدار گره کوچکتر هستند.

    با توجه به چنین تعریفی، واضح است که فرزندان چپ و راست یک گره در صورت وجود به ترتیب مقداری کمتر و بیشتر از مقدار خود گره دارند.

      

درخت جستجوی دودویی

      

کاربرد درخت جستجوی دودویی

  [بازگشت به فهرست]

مهمترین کاربرد چنین درختی از نام آن مشخص است. این درخت با توجه به تعریف آن برای انجام عملیات جستجو مناسب است. فرض کنید در مجموعه اعداد درخت فوق به دنبال عدد 6 هستیم. ابتدا 6 را با مقدار گره رأس - یعنی 5 - مقایسه می‌کنیم. این گره، گره مورد نظر ما نیست. عدد 6 هم از عدد 5 بزرگتر است. در نتیجه با توجه به تعریف درخت جستجوی دودویی، مطمئن هستیم که اگر گرهی با مقدار 6 وجود داشته باشد، به طور حتم در زیردرخت راست گره 5 است. پس به سمت راست حرکت کرده و عدد 6 را با 8 مقایسه می‌کنیم. باز هم به گره مطلوب نرسیدیم. اما با توجه به اینکه 6 از 8 کوچکتر است، به زیردرخت چپ گره 8 مراجعه می‌کنیم. در این مرحله به گره با مقدار 6 می‌رسیم که گره مطلوب ما است.

      

جستجو در درخت جستجوی دودویی

      

    اگر در حین جستجو مجبور به حرکت به سمتی شدیم که زیردرختی وجود ندارد، به این معنی است که گره مورد نظر در درخت وجود ندارد.

      

جستجو در درخت جستجوی دودویی

      

تحلیل الگوریتم جستجوی درخت

  [بازگشت به فهرست]

در جستجو با استفاده از درخت جستجوی دودویی، در هر مرحله اگر به گره مطلوب نرسیم، یک لایه در درخت به سمت پایین حرکت می‌کنیم. بنابراین تعداد مقایسه‌ها حداکثر برابر با عمق درخت است. حداقل تعداد مقایسه‌ها هم زمانی اتفاق می‌افتد که گره مورد نظر در رأس درخت قرار داشته باشد. در این حالت تنها یک مقایسه صورت می‌گیرد.

    عمق یک درخت با $n$ گره حداکثر $n$ و حداقل $[log_2\;n]+1$ است (چرا؟). پس می‌توان گفت این روش جستجو حداقل از مرتبه‌ی یک، حداکثر از مرتبه‌ی $n$ و به طور متوسط از مرتبه‌ی $log\;n$ است.

      

    نکته: در روش جستجوی دودویی در بدترین حالت هم مرتبه‌ی اجرا log n است. چرا که در هر مرحله به طور حتم داده‌ها به دو قسمت تقسیم می‌شوند. در نتیجه اگر یک درخت جستجوی دودویی و یک آرایه مرتب از مجموعه اعداد یکسان داشته باشیم، با صرفه‌تر است که از روش جستجوی دودویی برای جستجو استفاده کنیم. مگر آنکه درخت با توزیع مناسبی ساخته شده باشد و عمق آن حداقل باشد.

      

درج گره جدید در درخت جستجوی دودویی

  [بازگشت به فهرست]

زمانی که اقدام به درج یک گره جدید ذر درخت جستجوی دودویی می‌کنیم، باید محل مناسبی برای این گره پیدا کنیم. برای یافتن محل مناسب، فرض می‌کنیم که چنین گرهی در درخت وجود دارد و عملیات جستجو را برای آن انجام می‌دهیم. در نهایت به طور حتم به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است (چرا؟). این گره والد گره جدید خواهد بود.

    برای مثال فرض کنید می‌خواهیم گرهی با مقدار 7 را به درخت فوق اضافه کنیم:

      

درج گره در درخت جستجوی دودویی

      

    و اگر گرهی با مقدار صفر درج کنیم:

      

درج گره در درخت جستجوی دودویی

      

    زمانی که قصد ساخت یک درخت جستجوی دودویی را داریم، ترتیب درج مقادیر تاثیر مستقیمی در عمق درخت و سرعت اجرای عملیات جستجو خواهد داشت. اگر مجموعه اعداد وارد شده از قبل مرتب باشند، درخت به دست آمده از عمق n خواهد بود که در هر لایه‌ی آن تنها یک گره وجود دارد:

      

درخت جستجوی دودویی خطی

      

    بهترین حالت زمانی اتفاق می‌افتد که درخت ایجاد شده حداقل مقدار ممکن برای عمق ($log_2\;n] + 1]$) را داشته باشد. اما تشخیص چنین ترتیبی برای درج گره‌ها همواره آسان نیست. به همین خاطر روشهایی مانند AVL برای ساخت درخت‌ها ابداع شده است. درخت AVL درختی است که اختلاف عمق زیردرخت‌های چپ و راست هر گره، حداکثر یک است. برای ساختن چنین درختی از دستورالعمل خاصی استفاده می‌شود.

      

      

حذف گره از درخت جستجوی دودویی

  [بازگشت به فهرست]

حذف گره از درخت جستجوی دودویی پیچیده‌گی‌هایی دارد که گاهی گره را تنها با علامت‌گذاری حذف می‌کنند. به عبارت دیگر در این حالت هر گره درخت شامل فیلدی است که وضعیت حذف آن را مشخص می‌کند. اگر گرهی را با استفاده از تغییر مقدار این فیلد حذف کنیم، در عمل حافظه آن آزاد نشده و تغییری در ساختار درخت ایجاد نمی‌شود. اما در پردازش‌های آتی، این گره را در نظر نمی‌گیریم. اما گاهی نیاز است که گره به طور کامل حذف شده و حافظه‌ی مصرفی آن نیز آزاد شود.

    هر گره در درخت جستجوی دودویی ممکن است در یکی از سه وضعیت زیر باشد:

    1- گره فاقد فرزند است: یعنی گره مذکور یک برگ است. در چنین حالتی به راحتی می‌توان گره را حذف کرده و فضای مصرفی آن را آزاد کرد.

      

حدف برگ از درخت جستجوی دودویی

      

    2- گره دارای یک فرزند است: در این حالت گره فرزند را جایگزین گره مذکور می‌کنیم. به عبارت ساده‌تر، بین والد گره و فرزند گره ارتباط مستقیم برقرار کرده و گره مطلوب را حذف می‌کنیم.

      

حذف برگی با یک فرزند از درخت جستجوی دودویی

      

    3- گره دارای دو فرزند است: این حالت کمی پیچیده‌تر از حالت‌های قبلی است. ابتدا گرهی با کوچک‌ترین مقدار در زیردرخت راست گره را پیدا می‌کنیم. درج این گره به جای گره قبلی شروط درخت جستجوی دودویی را به هم نمی‌زند (چرا؟). در نتیجه می‌توان به راحتی آن را جایگزین کرد.

      

حذف گرهی با دو فرزند از درخت جستجوی دودویی

      

    گرهی که جایگزین می‌شود به طور حتم فرزند چپ ندارد (چرا؟). اما ممکن است فرزند راست داشته باشد. در این حالت عمل حذف طی دو مرحله انجام می‌شود. ابتدا گره جایگزین از محل خود بنا به حالت شماره‌ی 2 حذف می‌شود. سپس گره اصلی با جایگزین شدن این گره حذف می‌گردد.

    نکته: به کوچکترین گره زیردرخت راست گره، گره مابعد آن (Successor) گفته می‌شود. این نام‌گذاری به این خاطر است که اگر عناصر درخت با توجه به مقدار آنها مرتب شوند (مثلا با پیمایش Inorder) این گره بلافاصله بعد از آن قرار می‌گیرد. به همین ترتیب، گره ماقبل (Predecessor) یک گره نیز گرهی با بزرگترین مقدار در زیردرخت سمت چپ آن است. این گره نیز پس از مرتب‌سازی در کنار گره مفروض و قبل از آن قرار می‌گیرد. در حالت 3 برای حذف گره به جای عضو مابعد می‌توان از این گره نیز استفاده کرد.


نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی یا معرفی پیوند دانلود فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» منصور

یکشنبه، ۲۶ دی ماه ۱۳۹۵، ساعت ۰۹:۲۳
سلام ممنون06

» ارمین

شنبه، ۴ دی ماه ۱۳۹۵، ساعت ۰۰:۰۲
سلام
الان هر گره از این درخت فقط یک نوع داده داره اگه بخوایم تو هر گره چند نوع داده باشه باید چه کنیم؟
مثلا هر گره شامل کد دانشجویی(long)
معدل (float)
نام (string)
باشه


شنبه، ۴ دی ماه ۱۳۹۵، ساعت ۱۸:۴۰
مسعود:
اگر درخت با استفاده از اشاره‌گرها پیاده‌سازی بشه، حالت عادی هم از struct یا شی از کلاس node برای نگهداری اطلاعات گره‌های فرزند در کنار اطلاعات خود گره استفاده می‌شه. یعنی یک ساختار که دو آدرس به فرزندان و یک مقدار داره. حالا می‌شه این مقدار رو چند مقدار کرد.
اگر درخت با آرایه پیاده‌سازی شده هم به همین ترتیب می‌شه تغییراتی انجام داد.

» mohammad

یکشنبه، ۲۱ آذر ماه ۱۳۹۵، ساعت ۱۸:۰۳
خاهشا میشه کد این برنامه رو برام میل کنین؟ مرسی06

» kamyar

دوشنبه، ۳۱ خرداد ماه ۱۳۹۵، ساعت ۱۸:۰۸
خیلی ممنون080808

» مجید امینیان

سه‌شنبه، ۱۷ اردیبهشت ماه ۱۳۹۲، ساعت ۰۹:۳۱
با سلام و درود
من هر چقدر توی اینترنت گشتم جایی ندیدم که در مورد کاربرد الگوربتمهای مطرح در درس طراحی الگوریتم, در صنعت یا علم توضیحی داده باشه اگه امکان داره یه منبع یا اگر خودتون اطلاعاتی دارید برام ایمیل بفرمایید
ممنون میشم اگه کمکم کنید  

» mitra

دوشنبه، ۱۹ دی ماه ۱۳۹۰، ساعت ۱۳:۱۰
سلام من کد برنامه های بالا رو واسه امتحان میخوام میشه واسم میل کنید

» مهدی

شنبه، ۱۷ دی ماه ۱۳۹۰، ساعت ۰۹:۵۰
ما  26 دی 90 امتحان طراحی داریم
درخت کامل چیه؟؟


شنبه، ۱۷ دی ماه ۱۳۹۰، ساعت ۱۰:۵۹
مسعود:
مطلب با عنوان درخت Heap رو مطالعه کنید.

» مريم

چهارشنبه، ۷ دی ماه ۱۳۹۰، ساعت ۱۲:۱۷
واقعا جالب حساب كتاب كردي ايول افرين كيف كردم 120610

» مريم

چهارشنبه، ۷ دی ماه ۱۳۹۰، ساعت ۱۲:۰۶
دلم واسه اول دبستانم تنگ شده... که وقتی تنها ... یه گوشه ی حیاط مدرسه وایسادی... یه نفر میاد و بهت میگه ... با من دوست میشی؟

» سارا

شنبه، ۲۹ آبان ماه ۱۳۸۹، ساعت ۰۱:۲۳
کاش کد رو هم میذاشتین

» آرام

سه‌شنبه، ۲۲ تیر ماه ۱۳۸۹، ساعت ۰۰:۴۷
من برنامه ی درج و حذف در یک درخت AVL رو می خوام.شما میتونین کمکم کنین.فوریه!11

» نانا

چهارشنبه، ۲ تیر ماه ۱۳۸۹، ساعت ۱۱:۵۸
0506070803060606060606060613

» زهرا

سه‌شنبه، ۱۹ آبان ماه ۱۳۸۸، ساعت ۱۷:۳۵
الگوریتم زمانبندی مسابقات وتحلیل زمانی ان