الگوریتم تصادفی -فصل 3

* ساختمان داده های تصادفی

ساختمان داده با عملیات: جستجو، اضافه کردن و حذف کردن

1- آرایه مرتب شده: زمان جستجو O(logn) زمان حذف و اضافه O(n)

2- انواع درخت های جستجوی متوازن: (مثلا red-black tree و BST) زمان جستجو، حذف و اضافه O(logn)

چون پیاده سازی اینها سخت است:

ساختمان داده های تصادفی:

1- Treap

شرطی که در یک درخت جستجو وجود دارد و باعث سرعت بهتر جستجو می شود این است که به ازای هر گره مقدار کلید گره های سمت راست آن از مقدار کلید این گره بزرگتر و مقدار کلید گره های زیر درخت سمت چپ آن کوچکتر است.

زمان جستجو در درخت به عمق آن درخت بستگی دارد.

در treap یک درخت جستجوی دودویی داریم که heap هم هست، یعنی عناصر بالاتر آن اولویت بیشتری دارند. وجود و یکتایی treap با استقرا روی n ثابت می شود.

اولویت ها را تصادفی از بازه ی صفر تا یک انتخاب می کنیم و اگر تولید اعداد تصادفی را درست انجام بدهیم، احتمال اینکه اعداد متمایز باشند یک است.

ویژگی treap: هر گره در آن اولویت بیشتر از زیر درخت هایش دارد.

زمان: برای محاسبه ی زمان جستجو باید عمق درخت را حساب کنیم. برای این کار به ازای یک گره ی x مسیر از ریشه به آن گره را در نظر می گیریم. اعداد را بر اساس مقدار آنها مرتب و شماره گذاری می کنیم.

E( depth(Xk) ) = sum(E(Xi))

Xi = 1 if i-th node is in the path root-Xk, 0 otherwise

چون گره هایی که بالاتر هستند اولویت بیشتری دارند، چیزی که مطمئنیم اینه که باید اولویت Xi از Xk بیشتر باشه، ولی این کافی نیست، چون ممکنه x توی یه مسیر دیگه بیفته. حالا باید از خاصیت BST بودنش استفاده کنیم و دو حالت داریم: Xk بزرگتر از Xi باشه (یعنی جزو زیر درخت سمت راست Xi باشه). یا کوچکتر باشه (جزو زیر درخت سمت چپ). حالت اول رو فرض کنید. هر عددی که از Xi بزرگتر باشه و از Xk کوچکتر باشه توی زیر درخت سمت راست Xi میفته و قبل از اینکه به Xk برسه. اگه بخوایم توی مسیر بیفته باید اولویتش هم طوری باشه که بین اولویت Xi و Xk بیفته وگرنه جایی بیرون این مسیر میفته.

...