درخت جستجوی دودویی نوع خاصی از درختان دودویی است. ویژگی اصلی این درخت آن است که مقادیر درخت با نظم خاصی در آن قرار می گیرند به این صورت که همه مقادیر در زیر درخت چپ هر گره از آن کوچکتر و تمام مقادیر در زیر درخت راست آن بزرگتر از آن می باشند. این خاصیت حل مسایل ویژه ای را امکان پذیر می کند. به عنوان مثال می توان یک مقدار در چنین درختی را بصورت متوسط با ((O(log(n مقایسه پیدا نمود. این بهبود قابل ملاحظه ای در مقایسه با جستجوی خطی در یک لیست بی نظم می باشد.
در این متن درخت جستجوی دودویی را به اختصار دِرَجد می خوانیم.
پرسش: برنامه ای بنویسید که یک لیست از اعداد دریافت نماید و برای هر عنصر لیست تعداد عناصر کوچکتر بعد از آن را برگرداند.
پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم که آن را درست درک کرده ایم. فرض کنیم لیست [5, 3, 7, 11, 2, 4] را داریم. دو عنصر با مقادیر 2 و 3 بعد از اولین 4 قرار دارند و کوچکتر از آن می باشند. هیچ عنصری بعد از 2 کوچکتر از آن نیست و هر سه مقدار 7، 3، و 5 از 11 کوچکتر می باشند. بنابراین برنامه باید لیست [0, 0, 2, 3, 0, 2] را به عنوان جواب برگرداند.
ارایه الگوریتم را از روش جستجوی کامل (brute force) شروع می کنیم تا هم بیشتر مساله را درک کنیم و هم نشان دهیم که می توانیم حداقل یک راه حل ساده برای مساله بیابیم.
در روش جستجوی کامل از سمت چپ لیست شروع می کنیم و برای هر عنصر تمام عناصر بعد آن را تا آخر لیست یک به یک بررسی می کنیم. از یک شمارنده کمک می گیریم تا تعداد عناصری در لیست که کوچکتر از آن می باشند را بشماریم. بنابراین راه حل جستجوی کامل از دو حلقه تکرار تودرتو تشکیل می شود که حلقه بیرونی سراغ تک تک عناصر لیست می رود و حلقه درونی از آن عنصر تا انتهای لیست را می پیماید تا تعداد عناصر کوچکتر از آن را بشمارد. پیچیدگی محاسباتی این الگوریتم (O(n^2می باشد.
پیاده سازی این الگوریتم بسیار ساده است اما خود الگوریتم کند است. مشکل این الگوریتم کند بودن حلقه درونی است که باید مابقی لیست را تا آخر بپیماید تا تعداد عناصر کمتر از یک عنصر را بشمارد.
اما اگر عناصر بعد از یک عنصر مرتب بودند این مشکل وجود نداشت. مثلا فرض کنیم در مثال قبل عناصر بعد از 4 را ابتدا مرتب کنیم و در یک لیست جدا بصورت [11, 7, 5, 3, 2] قراردهیم. آنگاه اندیس اولین عنصری که بزرگتر مساوی 4 هست تعداد عناصر کوچکتر از آن را نشان می دهد. در مثال بالا اولین عنصر بزرگتر از 4، عنصر 5 می باشد که اندیس آن 2 می باشد. در یک لیست مرتب شده عمل جستجوی برای یافتن اولین عنصر بزرگتر از یک مقدار خواسته شده بسیار سریعتر از جستجوی خطی است. در واقع اگر لیستی از n عنصر مرتب داشته باشیم با استفاده از جستجوی دودویی، جستجو نیاز به حداکثر (log(n مقایسه خواهد داشت. بنابراین اگر عناصر بعد از هر عنصر را مرتب کنیم می توانیم به این روش تعداد عناصر کوچکتر از آن را بیابیم.
اما مشکل اصلی آن است که برای هر عنصر باید ابتدا تمام عناصر آن را مرتب کنیم تا بتوانیم از جستجوی سریع استفاده نماییم.
یک راه حل بظاهر احمقانه برای حل این مشکل این است که تنها یکبار لیست را مرتب کنیم و قبل از یافتن تعداد عناصر کوچکتر از هر عنصر آن را از لیست مرتب شده حذف کنیم. با اینکار لیست مقادیر بعد از هر عنصر را بصورت مرتب شده خواهیم داشت و می توانیم در آن سریع به دنبال اولین عنصر بزرگتر از آن دست یابیم. نهایتا می توانیم تعداد عناصر کوچکتر از آن را محاسبه کنیم. مشکل این الگوریتم آن است که هر بار باید یکی از عناصر را از لیست مرتب شده حذف کنیم. متاسفانه حذف یک عنصر از یک لیست هزینه بالایی دارد و پیچیدگی محاسباتی آن (O(n می باشد.
معادل ایده احمقانه بالا آن است که بجای پیمایش لیست از چپ به راست، آن را از راست به چپ بپیماییم. در این صورت بجای مرتب سازی کل لیست و حذف عناصر مصرف شده، با حرکت از راست به چپ عناصر پیمایش شده را در محل مناسب لیست مرتب درج می کنیم. این لیست مرتب در ابتدا خالی است و عناصر بگونه ای به آن اضافه می شود که مرتب بماند. با این کار عمل درج در یک لیست مرتب جایگزین حذف از یک لیست مرتب می شود که باز هم پیچیدگی محاسباتی (O(n دارد.
روش احمقانه دوم تفاوتی سرعتی با روش قبل ندارد اما جرقه ای در ذهن برای استفاده از ساختمان داده ای را می دهد که امکان جستجوی سریع با سرعتی که در یک لیست مرتب شده ممکن است را می دهد و همزمان هزینه درج در آن بسیار کمتر از درج در یک لیست است. این ساختان داده دِرَجد می باشد. یک درجد مشابه یک لیست مرتب شده است با این تفاوت که درج و حذف عناصر آن با پیچیدگی محاسباتی ((O(log(n انجام می شود.
اما درجد یک کمبود هم دارد و آن اینکه نمی توان با اندیس به عناصر درجد دست یافت. به همین دلیل نمی توان تعداد عناصر کوچکتر از یک عنصر در یک درجد را بدون پیمایش همه عناصر کوچتر از آن شمرد.
همچنان تسلیم نمی شویم. گویا چیزی در پس این ایده است که اگر آن را بفهمیم مشکل حل می شود.
شاید بتوانیم تغییری در درجد ایجاد کنیم که این کار را راحت کند؟ خاصیتی که درجد تغییر یافته در این مساله نیاز دارد آن است که شمارش تعداد عناصر کوچکتر از یک عنصر را آسان کند. برای این کار می توانیم یک فیلد به گره های درخت اضافه کنیم که تعداد گره های زیر درخت چپ آن گره را در خود نگه دارد. اسم این فیلد جدید را شمارنده (counter) می گذاریم و آن را با C نشان می دهیم. به عنوان مثال درجد با فیلد اضافی برای لیست [5, 3, 7, 11, 2, 4] با فرض اینکه عناصر را از راست به چپ در درخت درج کنیم این است:
در این شکل مقادیر مربوط به شمارنده را توسط ":c" مشخص نموده ایم. برای محاسبه تعداد عناصر کوچکتر از یک مقدار داده شده باید درخت را پیمایش کنیم و مقدار مجموع شمارنده ":c" را بروش خاصی جمع بزنیم. برای این کار هرگاه در مسیر رسیدن به عنصر مورد نظر (که می خواهیم تعداد عناصر کوچکتر از آن را بیابیم) به سمت زیر درخت راست یک گره حرکت کنیم باید مقدار شمارنده آن گره بعلاوه یک را به مجموع اضافه کنیم. به عنوان مثال برای یافتن تعداد عناصر کوچکتر از 11 مقادیر (1+3) و (1+0) را با هم جمع می کنیم که برابر با 5 می باشد.
با استفاده از این تغییر کوچک می توانیم تعداد عناصر کوچکتر از یک عنصر را با تنها با صرف ((O(log(n بیابیم. به این دلیل که این مقادیر را در زمان درج عناصر در درخت جستجوی دودویی بروز می کنیم، بار اضافی برای محاسبه اولیه این مقادیر نخواهیم داشت.
بنابراین کلیت الگوریتم جدید آن است که از سمت راست لیست شروع می کنیم. برای شمارش سریع تعداد عناصر کوچکتر در سمت راست هر عنصر از یک درجد استفاده می کنیم. این درجد در ابتدا خالی است. با حرکت از راست به چپ لیست ابتدا تعداد عناصر کوچکتر از آن را با استفاده از درجد محاسبه می کنیم. سپس خود این عنصر را در درجد درج می کنیم و مقادیر مربوط به شمارنده تعداد عناصر کوچکتر از گره ها را بروز می کنیم تا برای محاسبه تعداد عناصر کوچکتر عنصر بعدی در لیست آماده باشیم.
برای اینکه از درستی الگوریتم مطمین شویم آن را روی مثال ورودی بالا مرحله به مرحله اجرا می کنیم.
مثال بالا نشان می دهد که الگوریتم در صورتی که مقادیر عناصر لیست یکتا باشند بدرستی عمل می کند.
در صورتی که مقادیر عناصر تکراری باشند نیاز به تغییر رویه کوچکی در محاسبه شمارنده در گره ها هستیم. به این صورت که در زمان درج یک عنصر جدید در درجد مقدار شمارنده را با حرکت به سمت چپ یک گره یا مشاهده مقدار مساوی با آن یک واحد افزایش می دهیم. در ضمن به شمارنده یک گره جدید مقدار اولیه 1 می دهیم. این مشکل مربوط به مقادیر تکراری را حل می کند. با یک مثال دیگر که شامل عناصر تکراری نیز هست بررسی می کنیم که آیا این تغییر درست عمل می کند. فرض کنید لیست ورودی برابر با
[5, 5, 1, 11, 2, 4] است. دنباله درخت های زیر وضعیت درجد را پس از مشاهده مقادیر مختلف نشان می دهد.
مثال فوق نشان می دهد که این تغییر می تواند پاسخگوی ورودی با تکرار نیز می باشد. با توجه به اینکه تست های ابتدایی نشان می دهد که الگوریتم درست است، با گرفتن تایید از مصاحبه کننده بسراغ پیاده سازی الگوریتم می رویم.
در ابتدا یک گره از درجد که تغییر یافته است را تعریف می کنیم. یک متغیر شی به نام leq_counter برای نگه داشتن شمارش عناصر مساوی با یک عنصر یا کوچکتر از آن که در سمت چپ آن هستند در نظر می گیریم (خطوط 7-1). این متغیر معادل ':c' در شکلهای بالاست.
سپس یک تابع با پارامترهای مناسب تعریف می کنیم (خط 8). اگر لیست خالی باشد باید یک لیست خالی را به عنوان پاسخ برگردانیم (خط 9 و 10). سپس ریشه درجد را با ایجاد یک گره بر اساس آخرین عنصر لیست است (خط 13). این کار را به این دلیل انجام می دهیم که نتیجه را برای آخرین عنصر لیست می دانیم (تعداد عناصر کوچکتر بعد آن همیشه 0 است) و محاسبات را عمل از عنصر یکی به آخر شروع می کنیم. سپس لیست نتایج را با صفر مقدار دهی اولیه می کنیم (خط 14). در یک حلقه تکرار از عنصر یکی به آخر لیست شروع می کنیم و به سمت چپ لیست (عناصر با اندیس کوچکتر) حرکت می کنیم (خط 16). سپس در یک حلقه تکرار (خط 20 تا 27) با شروع از ریشه درخت جای درست این عنصر را در درجد می یابیم و همزمان با این کار مقدار شمارنده گره ها را بروز می کنیم. برای این کار یک متغییر به اسم c_node که ابتدا به ریشه درخت اشاره می کند و یک متغییر به اسم p_node که ابتدا مقدار نال (None) دارد تعریف می کنیم (خط 17). این دو اشاره گر در هنگام حرکت به سمت محل مناسب برای درج عنصر i ام بروز می شوند. سپس یک متغیر برای شمارش تعداد عناصر کوچکتر از عنصر iام که می خواهیم آن را در درجد درج کنیم با مقدار اولیه 0 در تعریف می کنیم (خط 18). با حرکت به سمت راست گره ها مقدار شمارنده گره ها را با این شمارنده جمع می کنیم.
سپس مقدار c_node را درون متغیر p_node نگه می داریم به این خاطر که c_node می خواهید یک سطح به سمت پایین درخت حرکت کند و چنانچه سطح بعدی نال باشد محل درج عنصر i ام را از دست ندهیم (خط 21). سپس مقدار عنصر i ام را با عنصر c_node مقایسه می کنیم. در صورتی که عنصر i ام کوچکتر از c_node باشد محل درج آن در سمت چپ c_node می باشد. بنابر این باید متغیر شی مربوط به عنصر c_node را یک واحد بیفزاییم و سپس به سمت چپ آن حرکت کنیم (خط 22 تا 24). در صورتی که عنصر iام بزرگتر از c_node باشد محل درج آن در سمت راست c_node می باشد. این همچنین به این مفهوم است که همه عناصر سمت چپ c_node از عنصر i ام کوچکترند و بنابر این تعداد آنها (مقدار متغیر شی leq_counter) باید به متغییر counter که تعداد چنین عناصری را می شمارد اضافه شود (خطوط 25 تا 27).
پس از انتهای حلقه درونی محل درست درج عنصر iام در سمت راست یا چپ p_node می باشد. بنابر این با مقایسه مقدار عنصر iام با مقدار p_node آن را در سمت راست یا چپ این گره درج می کنیم (خطوط 29 تا 32). نهایتا تعداد عناصر کوچکتر از آن در لیست نتایج res قرار می گیرد (خط 34).
با توجه به اینکه برای هر i حداکثر (log(n جستجو در درجد نیاز است، پیچیدگی محاسباتی این الگوریتم ((O(n*log(n می باشد.
