Санамсаргүй овоолго¶

Санамсаргүй овоолго гэдэг нь санамсаргүйжүүлэлт ашиглан бүх үйлдлийг хүлээгдэх логарифм хугацаанд гүйцэтгэх боломж олгодог овоолго юм.

Минимум овоолго гэдэг нь орой бүрийн утга нь хүүхдүүдийнхээ утгаас бага буюу тэнцүү байх хоёртын мод юм. Тиймээс модны минимум нь үргэлж үндэс оройд байна.

Максимум овоолгыг үүнтэй адил тодорхойлж болно: багыг ихээр солино.

Овоолгын өгөгдмөл үйлдлүүд нь:

Утга нэмэх
Минимумыг гаргаж авах
Минимумыг устгах
Хоёр овоолгыг нэгтгэх (давхардлыг устгахгүйгээр)
Дурын элементийг устгах (модон дахь байрлал нь мэдэгдэж байвал)

Санамсаргүй овоолго нь эдгээр бүх үйлдлийг маш энгийн хэрэгжүүлэлтээр хүлээгдэх $O(\log n)$ хугацаанд гүйцэтгэж чадна.

Өгөгдлийн бүтэц¶

Бид хоёртын овоолгын бүтцийг шууд тайлбарлаж болно:

struct Tree {
    int value;
    Tree * l = nullptr;
    Tree * r = nullptr;
};

Оройд бид утга хадгална. Түүнчлэн бидэнд зүүн ба баруун хүүхэд рүү заах заагчид байх ба харгалзах хүүхэд байхгүй бол null руу заана.

Үйлдлүүд¶

Бүх үйлдлийг ганц үйлдэл болгон бууруулж болохыг харахад хэцүү биш: хоёр овоолгыг нэг болгон нэгтгэх. Үнэхээр овоолгод шинэ утга нэмэх нь тэрхүү утгатай ганц оройноос тогтох овоолготой уг овоолгыг нэгтгэхтэй эквивалент. Минимум олоход ямар ч үйлдэл огт шаардагдахгүй — минимум нь зүгээр л үндэс дэх утга юм. Минимумыг устгах нь үндэс оройн зүүн ба баруун хүүхдийг нэгтгэсэн үр дүнтэй эквивалент. Дурын элементийг устгах нь үүнтэй адил. Бид оройн хүүхдүүдийг нэгтгэж, оройг нэгтгэлтийн үр дүнгээр солино.

Тиймээс бид үнэндээ зөвхөн хоёр овоолгыг нэгтгэх үйлдлийг хэрэгжүүлэх хэрэгтэй. Бусад бүх үйлдэл энэ үйлдэлд тривиалаар буурна.

$T_1$ ба $T_2$ гэсэн хоёр овоолго өгөгдсөн байг. Эдгээр овоолго тус бүрийн үндэс өөрийн минимумыг агуулна гэдэг нь тодорхой. Тиймээс гарсан овоолгын үндэс нь эдгээр хоёр утгын минимум байна. Тэгэхээр бид хоёр утгыг харьцуулж, багыг нь шинэ үндэс болгон ашиглана. Одоо бид сонгосон оройн хүүхдүүдийг үлдсэн овоолготой хослуулах хэрэгтэй. Үүний тулд бид хүүхдүүдийн нэгийг сонгож, үлдсэн овоолготой нэгтгэнэ. Ингэснээр бид дахин хоёр овоолгыг нэгтгэх үйлдэлтэй болно. Эрт орой хэзээ нэгэн цагт энэ процесс дуусна (ийм алхмын тоо нь хоёр овоолгын өндрүүдийн нийлбэрээр хязгаарлагдана)

Дунджаар логарифм complexity-д хүрэхийн тулд бид дундаж замын урт логарифм байхаар хоёр хүүхдийн нэгийг сонгох аргыг зааж өгөх хэрэгтэй. Бид энэ шийдвэрийг санамсаргүйгээр гаргана гэдгийг таахад хэцүү биш. Тиймээс нэгтгэх үйлдлийн хэрэгжүүлэлт дараах байдалтай:

Tree* merge(Tree* t1, Tree* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t2->value < t1->value)
        swap(t1, t2);
    if (rand() & 1)
        swap(t1->l, t1->r);
    t1->l = merge(t1->l, t2);
    return t1;
}

Энд эхлээд бид овоолгуудын нэг нь хоосон эсэхийг шалгана, тэгвэл бид ямар ч нэгтгэх үйлдэл огт хийх шаардлагагүй. Эс бөгөөс бид t1 овоолгыг бага утгатайг нь болгоно (шаардлагатай бол t1 ба t2-г солих замаар). Бид t1-ийн зүүн хүүхдийг t2-тэй нэгтгэхийг хүсэж байгаа тул t1-ийн хүүхдүүдийг санамсаргүйгээр сольж, дараа нь нэгтгэлийг гүйцэтгэнэ.

Complexity¶

Бид үндэснээс навч хүртэлх санамсаргүй замын урт-ыг (ирмэгийн тоогоор илэрхийлсэн урт) тэмдэглэх $h(T)$ санамсаргүй хэмжигдэхүүнийг нэвтрүүлнэ. merge алгоритм $O(h(T_1) + h(T_2))$ алхам гүйцэтгэдэг нь тодорхой. Тиймээс үйлдлүүдийн complexity-г ойлгохын тулд бид $h(T)$ санамсаргүй хэмжигдэхүүнийг судлах ёстой.

Хүлээгдэх утга¶

Бид $h(T)$-ийн математик хүлээлтийг овоолго дахь оройн тооны логарифмаар дээрээс нь үнэлж болно гэж үзнэ:

$$\mathbf{E} h(T) \le \log(n+1)$$

Үүнийг индукцээр амархан батлаж болно. $L$ ба $R$ нь $T$ үндсийн зүүн ба баруун дэд мод, $n_L$ ба $n_R$ нь тэдгээр дэх оройн тоо ($n = n_L + n_R + 1$) байг.

Индукцийн алхам дараах байдалтай:

$$\begin{align} \mathbf{E} h(T) &= 1 + \frac{\mathbf{E} h(L) + \mathbf{E} h(R)}{2} \le 1 + \frac{\log(n_L + 1) + \log(n_R + 1)}{2} \\\\ &= 1 + \log\sqrt{(n_L + 1)(n_R + 1)} = \log 2\sqrt{(n_L + 1)(n_R + 1)} \\\\ &\le \log \frac{2\left((n_L + 1) + (n_R + 1)\right)}{2} = \log(n_L + n_R + 2) = \log(n+1) \end{align}$$

Хүлээгдэх утгаас хэтрэх нь¶

Мэдээж бид одоо ч сэтгэл хангалуун бус байна. $h(T)$-ийн хүлээгдэх утга хамгийн муу тохиолдлын талаар юу ч хэлэхгүй. Тодорхой модны хувьд үндэснээс орой хүртэлх замууд дунджаар $\log(n + 1)$-ээс хамаагүй их байх боломж хэвээр байна.

Хүлээгдэх утгаас хэтрэх магадлал үнэхээр маш бага болохыг батлая:

$${\cal P}(h(T) > (c+1) \log n) < \frac{1}{n^c}$$

дурын эерэг тогтмол $c$-ийн хувьд.

Энд бид овоолгын үндэснээс навчид хүрэх, урт нь $(c+1) \log n$-ээс хэтрэх замуудын олонлогийг $P$ гэж тэмдэглэнэ. $|p|$ урттай дурын зам $p$-ийн хувьд түүнийг санамсаргүй зам болгон сонгох магадлал нь $2^{-|p|}$ болохыг анхаарна уу. Тиймээс бид:

$${\cal P}(h(T) > (c+1) \log n) = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$$

-г олж авна.

Алгоритмын complexity¶

Тиймээс merge алгоритм, улмаар түүгээр илэрхийлэгдэх бусад бүх үйлдлийг дунджаар $O(\log n)$-д гүйцэтгэж болно.

Түүнчлэн дурын эерэг тогтмол $\epsilon$-ийн хувьд, үйлдэл $c \log n$-ээс олон алхам шаардах магадлал нь $n^{-\epsilon}$-ээс бага байх эерэг тогтмол $c$ байдаг (тодорхой утгаараа энэ нь алгоритмын хамгийн муу тохиолдлын зан төлөвийг тодорхойлно).