BST

درخت های دودویی، درخت های ریشه داری هستند که هر راس حداکثر ۲ بچه دارد. Binary Search Tree یا درخت جست و جوی دودویی، یک داده ساختار درختی است که روی هر راس آن یک عدد نوشته شده است. فرض کنید روی هر راس \(u\) عدد \(a_u\) نوشته شده باشد. BST دارای ویژگی های زیر است.

  • تمام اعداد نوشته شده روی زیردرخت سمت چپ \(u\) کمتر از \(a_u\) هستند.
  • تمام اعداد نوشته شده روی زیردرخت سمت راست \(u\) بیشتر از \(a_u\) هستند.

این ویژگی جالب BST باعث می شود که جست و جو به دنبال یک عدد خاص مثل \(x\) در این داده ساختار برای ما آسان باشد. به این صورت که اگر در زیردرخت \(u\) به دنبال عدد \(x\) می گردیم ابتدا \(a_u, x\) را مقایسه می کنیم.

  • اگر \(a_u = x\) که این مقدار را پیدا کرده ایم.
  • اگر \(a_u > x\) آنگاه باید در زیردرخت بچه سمت چپ \(u\) به دنبال \(x\) بگردیم.
  • اگر \(a_u < x\) آنگاه باید در زیردرخت بچه سمت راست \(u\) به دنبال \(x\) بگردیم.

پس در واقع طی عملیات جست و جو به دنبال \(x\) یک مسیر از ریشه تا یک راس را طی می کنیم پس بیشترین تعداد عملیاتی که انجام می دهیم برابر با ارتفاع درخت است!

به صورت معمول BST ها این عملیات های پایه ای را انجام می دهند.

  • یک راس جدید با مقدار \(x\) به ساختار اضافه کن.
  • راس \(u\) (دلخواه) را حذف کن.
  • راسی که مقدار \(x\) روی آن نوشته شده را پیدا کن (یا بگو چنین راسی وجود ندارد).

همانطور که دیدیم BST ها عملیات سوم را با \(O(h)\) انجام می دهند پس باید اضافه و حذف راس (عملیات اول و دوم) را طوری انجام دهیم که ارتفاع درخت زیاد نشود!

به عنوان مثال می توان برای اضافه کردن مقدار جدید \(x\) (عملیات اول) به سادگی دنبال \(x\) بگردیم. اگر \(x\) را یافتیم که نیاز به اعمال تغییر در درخت نیست. در غیراینصورت می توانیم همانجایی که انتظار داشتیم \(x\) باشد و نبود (اولین مرحله ای که جست و جو ما را به راسی خارج از درخت هدایت می کند)، راسی با مقدار \(x\) قرار دهیم. این یک روش خیلی ساده برای انجام عملیات اول است اما اگر این روش را در پیش بگیریم ممکن است بعد از مدتی ارتفاع درخت خیلی زیاد شود که اصلا بهینه نیست. مثلا با اضافه کردن اعداد 1 تا \(n\) به صورت صعودی، در نهایت به یک مسیر \(n\) راسی می رسیم.

برای حذف کردن مقدار \(x\) یک روش ساده این است که ابتدا راس \(u\) را پیدا کنیم که \(a_u = x\) است. سپس راس با کمترین مقدار در زیر سمت راست \(u\) پیدا کنیم (اگر زیردرخت سمت راست نداشت به سادگی می توان کل زیردرخت سمت چپ را به جای زیر درخت \(u\) قرار داد). و این راس کمینه را به جای \(u\) قرار دهیم. می توان بررسی کرد که در اینصورت درخت حاصل همچنان ویژگی BST را حفظ خواهد کرد. پیدا کردن راس با کمترین مقدار هم به این شکل ممکن است که هر زمان که می توانستیم به چپ برویم، به چپ می رویم هر زمان که نتوانستیم به چپ برویم به راس با مقدار کمینه رسیده ایم. (چرا؟)

الگوریتم های متفاوتی برای BST وجود دارد که از جمله معروف ترین آن ها می توان به AVL tree, Red–black tree, Tango tree, Treap اشاره کرد. که هر کدام به روش متفاوتی عمل می کنند اما تمام آن ها تلاش می کنند که ارتفاع درخت را \(O(log(n))\) نگه دارند!

بعضی از آن ها مثل Treap به صورت احتمالاتی کار می کنند یعنی ممکن است ارتفاع درخت زیاد شود اما اگر میانگین ارتفاع در مراحل مختلف را در نظر بگیریم امیدریاضی آن از \(O(log(n))\) خواهد بود.

در کل می توان فرض کرد که الگوریتم های مشهور BST (که در اینجا به بحث درباره آن نمی پردازیم) تمام عملیات ها را با پیچیدگی زمانی \(O(log(n))\) انجام می دهند. جالب است بدانید std::set که در زبان c++ کاربرد فراوان دارد در واقع با Red–black tree پیاده سازی شده است.