Өөрийгөө тэнцвэржүүлэгч мод | TEE Education

2026.05.222 min read#алгоритмбаөгөгдлийнбүтэц#tree#DSA#AVL#Red-Black#Splay#B-tree

Өөрийгөө тэнцвэржүүлэгч мод

М.Хатанболд

Багш

Мэдээллийн технологийн салбарт өгөгдлийг хэрхэн зохион байгуулах нь системийн хурд, хүчин чадалд шийдвэрлэх нөлөө үзүүлдэг. Энэхүү нийтлэлээр бид мод өгөгдлийн бүтцийн ерөнхий ойлголт, тэнцвэржүүлэлтийн ач холбогдол болон орчин үеийн програм хангамжид ашиглагддаг гол алгоритмуудын механизмыг дэлгэрэнгүй авч үзэх болно.

Мод (Tree) өгөгдлийн бүтэц гэж юу вэ?

Мод гэдэг нь өгөгдлийг шатласан (hierarchical) хэлбэрээр хадгалдаг шугаман бус бүтэц юм. Бидний эргэн тойронд байдаг файлын систем (Folders/Files), байгууллагын бүтэц, эсвэл вэб хуудасны DOM (Document Object Model) зэрэг нь бүгд мод өгөгдлийн бүтцийн бодит жишээнүүд юм.

Мод нь дараах үндсэн бүрэлдэхүүн хэсгүүдээс бүрдэнэ:

Үндэс (Root): Модны хамгийн дээд талын, эцэггүй зангилаа.
Зангилаа/Орой (Node): Өгөгдөл хадгалж буй цэг бүр.
Ирмэг (Edge): Хоёр зангилааг холбосон шугам.
Навч (Leaf): Хүүхэдгүй буюу модны төгсгөл дэх зангилаанууд.

Модны гол давуу тал нь өгөгдлийг төрөл төрлөөр нь бүлэглэж, хайлт хийх замыг богиносгодогт оршдог. Гэвч модны бүтэц нэг тал руугаа хэт хазайж "тэнцвэр" алдагдвал энэхүү давуу тал нь үгүй болж, ердийн жагсаалт шиг удаан ажиллаж эхэлдэг. Үүнээс сэргийлэхийн тулд "өөрийгөө тэнцвэржүүлэгч" механизмуудыг ашигладаг. Өөрийгөө тэнцвэржүүлэгч мод нь зангилаа нэмэх/устгах бүрт өндрөө автоматаар тохируулж, хайлтын хурдыг үргэлж хамгийн дээд O(log n) түвшинд барьдаг.

Түгээмэл ашиглагддаг өөрийгөө тэнцвэржүүлэгч моднууд

AVL мод: "Төгс" тэнцвэрийн төлөөх тэмцэл

1962 онд Г.М.Адельсон-Вельский, Е.М.Ландис нарын танилцуулсан энэхүү мод нь хамгийн анхны өөрийгөө тэнцвэржүүлэгч өгөгдлийн бүтэц юм.

Зангилаа бүрийн баруун, зүүн дэд модны өндрийн зөрүү нь заавал {-1, 0, 1} байх ёстой. Хэрэв зөрүү 2 хүрвэл "эргүүлэлт" (Rotation) хийж тэнцвэрийг сэргээнэ. AVL мод нь маш хатуу тэнцвэр барьдаг тул хайлт хийхэд хамгийн бага хугацаа зарцуулдаг. Хэрэв таны системд өгөгдөл нэг л удаа нэмэгдээд, дараа нь маш олон удаа хайлт хийгдэх бол (жишээ нь, цахим толь бичиг) AVL хамгийн шилдэг сонголт юм.

Улаан-Хар мод: Практик хэрэглээний хаан

Энэхүү мод нь AVL шиг хатуу биш ч гэсэн "хангалттай сайн" тэнцвэрийг барьж чаддаг. Түүний дүрэм нь зангилаа бүрт өнгө (Улаан эсвэл Хар) онооход суурилдаг.

Linux үйлдлийн системийн процессын төлөвлөгч (Completely Fair Scheduler) нь Улаан-Хар модыг ашигладаг. Процессууд байнга нэмэгдэж, хасагдаж байдаг тул AVL шиг хатуу мод ашиглавал "эргүүлэлт" хийх гэж их хугацаа алдана. Улаан-Хар мод нь өнгө солих замаар маш хурдан тэнцвэрждэг.

Splay мод: "Сүүлд хандсаныг нь түрүүлж"

Splay мод нь тэнцвэрээ тогтмол барьдаггүй, харин хэрэглэгчийн хандалт дээр тулгуурлан өөрийгөө өөрчилдөг. Хамгийн сүүлд хандсан зангилааг модны оройд (үндэс дээр) гаргаж ирдэг. Сүлжээний чиглүүлэгч (Router) дээр ашиглахад маш тохиромжтой. Байнга пакет илгээж буй IP хаяг модны оройд байх тул хайлт бараг агшин зуурт O(1) орчим хийгдэнэ.

B-Tree ба B+ Tree: Өгөгдлийн сангийн тулгуур

Бидний өдөр тутам ашигладаг Google Search, банкны гүйлгээний системүүд B-Tree-ийн ачаар хурдан ажилладаг. Бусад моднууд санах ойд (RAM) зориулагдсан бол B-Tree нь Диск (HDD/SSD) дээр ажиллахад зориулагдсан. Нэг оройнд хэдэн зуун өгөгдөл хадгалах боломжтой тул модны өндөр нь маш бага (ихэвчлэн 3-4 түвшин) байдаг. 1 тэрбум өгөгдөл дундаас хайхад дискнээс ердөө 3-4 удаа уншилт хийхэд л хангалттай байдаг нь асар их хугацаа хэмнэдэг.

Өөрийгөө тэнцвэржүүлэгч моднууд нь програм хангамжийн архитектурын "үл үзэгдэх баатрууд" юм. Тэд байгаагүй бол бидний ашигладаг хайлтын систем, үйлдлийн системүүд өгөгдөл ихсэх тусам удааширч, ашиглах боломжгүй болох байсан. Хөгжүүлэгчийн хувьд системийнхээ онцлогт (унших үйлдэл их үү, бичих үйлдэл их үү) тохируулан зөв модоо сонгох нь гүйцэтгэлийг хэдэн зуу дахин нэмэгдүүлэх үндэс болдог.