حل تشریحی سوال شماره 18 ساختمان داده ها و طراحی الگوریتم ها

کدام یک از گزاره‌های زیر درست است؟

الف- هر درخت جستجوی دودویی دلخواه با n گره می‌توان به یک درخت جستجوی دودویی دلخواه دیگر با n گره با انجام O(n) عمل rotation تبدیل شود.

برای هر دو تابع f(n) و g(n) یکی از سه حالت $f\left(n\right)\in o\left(g\left(n\right)\right)\left(1\right)$، $f\left(n\right)\in w\left(g\left(n\right)\right)$ و $f\left(n\right)\in \theta \left(g\left(n\right)\right)\left(3\right)$ برقرار است.