Tree(Data Structure) – Мод(Өгөгдлийн бүтэц)

Анхбаяр

• 2023-03-08

Мод өгөгдлийн бүтэц нь хайх болон чиглүүлэхэд илүү амар байдлаар өгөгдлийг зохион байгуулах мөн дүрслэхэд ашиглагддаг шаталсан бүцэт юм. Энэхүү бүтэц нь цагирагаар зангилаа үүсгэн тогтоно. Модны хамгийн дээр байгаа цагирагийг үндэс(root) гэж нэрлэдэг ба үүний доор байгаа цагирагуудыг хүүхэд цагираг гэж нэрлэдэг. Цагираг бүр хэд хэдэн хүүхэд цагирагтай байж болох ба эдгээр хүүхэд цагирагууд нь мөн л өөрсдийн гэсэн хүүхэд цагирагтай байх боломжтой. Яг л ургийн мод шиг.

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

Мод өгөгдлийн бүтцийн төрлүүдийг ерөнхийд нь 3 төрөлд хуваан авч үздэг. Үүнд:
1. Ерөнхий мод
Ерөнхий модон өгөгдлийн бүтэц нь цагирагийн тоон дээр ямар нэгэн хязгаарлалт байдаггүй. Энэ нь эцэг цагирагууд хэдэн ч тооны хүүхэд цагирагтай байж болдог.
2. Хоёртын мод
Хоёртын модны цагираг нь дээд талдаа 2 хүүхэд цагирагтай байна.
3. Тэнцвэртэй мод
Хэрэв зүүн талын туслах модны хэсгийн өндөр болон баруун талын туслах модны хэсэг нь хоорондоо тэнцүү эсвэл хамгийн ихдээ 1-ийн зөрүүтэй бол үүнийг тэнцвэртэй модон өгөгдлийн бүтэц гэж нэрлэнэ.

Мод өгөгдлийн бүтцийн давуу талууд:

• Үр ашигтайгаар өгөгдөл оруулах, устгах мөн хайлтын үйлдлийг хийх.
• Хадгалагдаж болохуйц өгөгдлийн төрлүүдийн хувьд илүү мод нь уян хатан байдаг.
• Шаталсан хамаарлыг дүрслэхэд тохиромжтой.
• Huffman coding болон decision tree зэрэг олон төрлийн өгөгдлийн бүтэц болон алгоритмууд дээр ашиглагддаг.

Мод өгөгдлийн бүтцийн сул талууд:

• Мод нь заагчуудад нэмэлт санах ойг шаарддаг.
• Шаталсан хамааралгүй өгөгдлийн хувьд муу сонголт болдог.
• Мод нь олон давхаргуудтай(levels) тохиолдолд хайлт хийхэд маш их нөөц шаардана.