جستجو در BST

جستجوی يک مقدار در BST از گره ريشه شروع می شود. آرگومان جستجو با مقدار گره مقايسه می شود. اگر يکسان باشند داده مورد نظر پيدا شده است در غيراينصورت اگر داده از مقدار گره کوچکتر باشد جستجو از زيردرخت چپ و اگر بزرگتر باشد جستجو از زيردرخت راست گره ادامه پيدا می کند.  به طور خلاصه الگوريتم جستجوی BST به صورت زير بيان می شود. Item داده موردنظر است که در BST جستجو می شود. الگوريتم مقدار تهی يا گره ای که دنبالش هستيم را بر می گرداند.

Search ( TreePointer T, DataType Item )
Begin
   If (T = null) Then return null {tree is empty}
   Else If (Item = T.Data ) Then return T {item found}
   Else If (Item < T. Data and T.Left !=NULL ) Then Search(T.Left, ِData)
   Else If (Item > T.Data and T.Right !=NULL ) Then Search (T.Right, Data)
   End If
End

مثال. فرض کنيد می خواهيم عدد 10 را در درخت شکل (b) مثال قبل جستجو کنيم. جستجو از ريشه شروع می شود. عدد 7 در ريشه است که کمتر از 10 است. بنابراين اگر 10 وجود داشته باشد بايد در زيردرخت راست ريشه باشد. پس جستجو را از گره 11 ادامه می دهيم. در حالت 10 از عدد 11 کمتر است بنابراين اگر 10 در درخت باشد بايد در زيردرخت چپ گره 11 باشد. به سمت چپ گره 11 حرکت می کنيم که گره 10 است و گره ای که دنبالش می گشتيم را پيدا کرديم. ممکن است که اگر گره ای که به دنبالش هستيم در درخت موجود نباشد. برای نمونه اگر بدنبال عدد 9 هستيم ابتدا به همان طريق بالا عمل می کنيم. وقتی به گره 10 می رسيم بايد جستجو را از زيردرخت چپ ادامه دهيم ولی گره 10 فرزند چپ ندارد بنابراين 9 در درخت وجود ندارد. با دقت در الگوريتم جستجو می توان مشاهده کرد که درهرمرحله تعداد گره هايی که بايد بررسی شوند نصف می شوند. بنابراين چنين زمان اجرای الگوريتم log₂ n می شود. البته زمان جستجو به توپولوژی درخت بستگی دارد و در بهترين حالت O(log n) است، در بدترين حالت O(n) می شود. اگر يک BST به روش InOrder پيمايش شود مقادير گره‌های درخت به صورت مرتب بدست می آيد. زمان اجرای پيمايش روی درخت O(n) است.

درج در BST

درج يک گره جديد در BST در دو مرحله انجام می گيرد. ابتدا داده جديد در BST طبق الگوريتمی که ذکر شد جستجو می شود سپس در محل خاتمه جستجو گره جديد اضافه می شود. با فرض اينکه داده تکراری در درخت مجاز نيست، هنگام درج گره جديد دو شرط بايد مدنظر باشد:

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

اگر زيربرنامه جستجو متوجه شود که گره جديد قبلا در BST وجود دارد پايان می يابد و دوباره آنرا درج نمی کند. گره جديد به نحوی بايد به درخت اضافه شود که BST خواص خود را حفظ کند.گره جديد هميشه به صورت يک برگ اضافه می شود. بنابراين ترتيب درج روی توپولوژی درخت تاثير می گذارد. زمان اجرای الگوريتم درج مشابه الگوريتم جستجو است.

مثال. مراحلی که بايد طی شود تا گره 62 به BST اضافه شود در شکل های زير نشان داده شده است.

حذف از BST

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

حالت 1. گره که بايد حذف شود برگ باشد و فرزندی نداشته باشد. در اين حالت حذف به سادگی انجام می پذيرد و کافی است اشاره گر والد برابر تهی شود. برای مثال در شکل گره 25 که حذف می شود فرزندی ندارد.

حالت 2. گره ای که بايد حذف شود تنها دارای يک فرزند چپ است که می تواند جايگزين آن شود. برای مثال فرض کنيد بخواهيم گره 50 را حذف کنيم. چون 50 فرزند راستی ندارد 20 با آن جايگزين می شود.

حالت 3. فرزند راست گره ای که بايد حذف شود فرزند چپی ندارد بنابراين فرزند راست گره جايگزين آن می شود. برای مثال اگر بخواهيم گره 150 را حذف کنيم چون فرزند راست آن فرزند چپی ندارد فرزند راستش يعنی 175 جايگزين می شود.

حالت 4. فرزند راست گره ای که بايد حذف شود فرزند چپ دارد. در اين حالت چپ ترين فرزند راست گره جايگزين آن می شود. يعنی کوچکترين مقدار زير درخت راست گره. برای مثال اگر گره 50 را در شکل زير حذف کنيم چپ ترين فرزند آن يعنی 66 را انتخاب کرده و جايگزين می کنيم.

در هر BST کوچکترين مقدار در سمت چپ ترين گره و بزرگترين مقدار در سمت راست ترين گره وجود دارد.

اولين مرحله در حذف گره پيدا کردن محل گره ای است که می خواهيم حذف کنيم که توسط الگوريتم جستجو که قبلا توضيح داده شد انجام می گيرد. بنابراين زمان حذف همان زمان O(log n) در حالت متوسط و O(n) در بدترين حالت است.

معايب BST

باوجود اينکه درخت های جستجوی دودويي به طور ايده ال زمان زيرخطی برای درج، جستجو و حذف می دهند، زمان اجرا بستگی به توپولوزی BST دارد. توپولوژی درخت وابسته به ترتيبی است که داده در BST درج می شود. اگر داده ورودی مرتب باشد توپولوژی BST يک درخت ناميزان طولانی و باريک می شود که بدترين زمان را در اجرای الگوريتم ها می دهد و معمولا در دنيای واقعی داده ها بطور طبيعی مرتب يا نزديک به مرتب هستند.