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

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

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

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

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

(Deletion) حذف کردن

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