Гуравтын мод (Ternary tree)

Компьютерийн шинжлэх ухаанд өгөгдлийг үр ашигтай хадгалах, боловсруулах нь хамгийн чухал асуудлуудын нэг байдаг. Үүнийг хэрэгжүүлэхэд ашиглагддаг үндсэн өгөгдлийн бүтцүүдийн нэг нь мод (Tree) юм. Ихэнх хүмүүс хоёр хүүхэд зангилаатай хоёртын мод (Binary Tree)-ыг сайн мэддэг боловч түүнээс илүү олон салаатай моднууд ч байдаг. Тэдгээрийн нэг нь гуравтын мод (Ternary Tree) бөгөөд нэг зангилаа хамгийн ихдээ гурван хүүхэдтэй байж болдгоороо онцлогтой юм.

Гуравтын мод гэж юу вэ?

Гуравтын мод нь шаталсан бүтэцтэй өгөгдлийн төрөл бөгөөд зангилаа (Node) бүр зүүн (Left), дунд (Middle), баруун (Right) гэсэн хамгийн ихдээ гурван үргэлжлэлтэй байж болно. Модны хамгийн дээд зангилааг үндэс (Root) гэж нэрлэх бөгөөд түүнээс доош байрлах зангилаанууд эцэг–хүүхдийн холбоогоор холбогдоно.

Гуравтын мод хэрхэн ажилладаг вэ?

Гуравтын мод нь зангилаануудыг шаталсан байдлаар зохион байгуулдаг. Шинэ элемент нэмэхдээ тодорхой дүрмийн дагуу аль салбарт байрлуулахаа сонгодог. Хайлт хийх үед тухайн зангилааг шалгаад шаардлагатай бол зүүн, дунд эсвэл баруун салбар руу шилжин үргэлжлүүлэн хайдаг.

Ингэснээр мэдээллийг бүхэлд нь дарааллаар шалгах шаардлагагүй болж, олон тохиолдолд хайлтын хугацаа мэдэгдэхүйц багасдаг.

Давуу талууд

Гуравтын мод нь хэд хэдэн давуу талтай.

• Нэг зангилаа гурван хүүхэдтэй байж болох тул модны өндөр хоёртын модтой харьцуулахад бага байх боломжтой.

• Илүү олон сонголтыг нэг түвшинд хадгалж чаддаг.

• Зарим төрлийн хайлт болон тэмдэгт мөр боловсруулах алгоритмуудад маш тохиромжтой.

• Өгөгдлийг шаталсан бүтэцтэйгээр ойлгомжтой зохион байгуулдаг.

Ялангуяа олон тооны үг хадгалдаг системүүдэд гуравтын хайлтын мод (Ternary Search Tree) нь санах ойн хэрэглээ болон хайлтын хурдын хооронд сайн тэнцвэрийг бий болгодог.

Сул талууд

Гэсэн хэдий ч бүх нөхцөлд хамгийн сайн сонголт байдаггүй.

• Хэрэгжүүлэх алгоритм нь хоёртын модноос илүү төвөгтэй.

• Нэг зангилаанд илүү олон заагч (pointer) хадгалах шаардлагатай тул санах ой илүү ашиглаж болно.

• Зарим асуудалд хоёртын мод илүү энгийн бөгөөд хурдан ажиллах боломжтой.

Иймээс ашиглах бүтэц нь тухайн асуудлын онцлогоос ихээхэн шалтгаалдаг.

Бодит хэрэглээ

Гуравтын модыг дараах салбаруудад өргөн ашигладаг.

Binary vs Trinary

Хүүхдийн тоо нэмэгдэх тусам мод илүү өргөн болох боловч нэг түвшинд илүү олон мэдээлэл хадгалах боломжтой болдог.

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

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