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

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

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

- این مرحله رو تا جایی ادامه میدیم که یا بچه مورد نظر وجود نداشته باشه تا ما بریم توی زیر درختش و یا مقدار راسی که داریم بررسی می کنیم برابر با x باشد.

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

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

- این مرحله رو تا جایی ادامه میدیم که بچه مورد نظر وجود نداشته باشه و ما یک بچه در همون قسمت اضافه می کنیم و مقدارش رو x می گذاریم.

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