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

(Search) جست و جو¶

عملیات جست و جو کردن برای یک مقدار با فرض اینکه مقداری که دنبالش هستیم x به صورت زیر است :

• ابتدا مقدار روی ریشه درخت را نگاه می کنیم، اگر بزرگتر از x بود همین مرحله رو به صورت بازگشتی بر روی زیر درخت بچه چپ انجام می دهیم و اگر کوچک تر بود روی زیر درخت بچه راست.
• این مرحله رو تا جایی ادامه میدیم که یا بچه مورد نظر وجود نداشته باشه تا ما بریم توی زیر درختش و یا مقدار راسی که داریم بررسی می کنیم برابر با x باشد.

(Insertion) اضافه کردن¶

عملیات اضافه کردن یک مقدار با فرض اینکه مقداری که قرار است اضافه شود x باشد به صورت زیر است :

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

(Deletion) حذف کردن¶

بعد از پیدا کردن راسی که قرار است حذف شود به همان روش جست و جو، ۳ حالت ممکن است. حالت اول این است که راس مورد نظر هیچ بچه ای نداشته باشه و خیلی راحت می توان همان لحظه راس را حذف کرد. حالت دوم این است که راس مورد نظر یک بچه داشته باشد و می توان راس را حذف و بچش رو جای خودش قرار می دیم. حالت سوم برای زمانیست که راس مورد نظر دو بچه داشته باشد. به دو روش می توان این راس را حذف کرد. و برای اینکه بهتر متوجه شید اسم راسی که قرار است حذف شود را u می گذاریم. روش اول به این شکل است که راس v که کوچک ترین مقدار در زیر درخت راست u را دارد بدست میاریم و مقدارش رو بجای مقدار u می گذاریم. حال اگر راس v را به یکی از دو حالت یک و دو حذف می کنیم(واضح است که راس v حالت سوم نمی تواند باشد چون v کوچک ترین راس است و اگر دو بچه داشته باشد یعنی بچه سمت چپ دارد که از خودش کوچک تر است و این تناقض است). روش دوم همانند روش اول است با این تفاوت که راس v بزرگترین راس در زیردرخت بچه چپ راس u است.