5

                                           Мод

Байгаль дээр үндэс, мөчир, навч бүхий ургамлыг мод гэдэг. Компьютерын ухаанд модтой бүтцийн хувьд төстэй өгөгдлийн бүтцийг мөн мод гэдэг. Гэхдээ компьютерын ухаанд модыг уруу харуулж зурдаг. Мод гэдэг бүтцийн хувьд үндэс бол хамгийн чухал элемент бөгөөд нэг модонд цорын ганц үндэс байна. Үндсээс мөчир, мөчрөөс навч гардаг. Салаалж ургасан модны хэсгийг дэд мод гэнэ. Нэг зангилаанаас хэдэн элемент – мөчир/навч салаалсан гэдгээс нь хамааруулж хоёртын, N –тын мод гэж ялгаж болдог. Тэдэн дотор хоёрын мод онцгой байр эзэлдэг бөгөөд хоёртын модонд суурилсан олон хэрэглээ байдаг. Модны тухай ярихад өвөг эцэг, эцэг, хүүхэд, ахан дүүс гэсэн ухагдахуунуудыг бас хэрэглэдэг.

Мод нь ямар нэг нөхцөлийг хангах тодорхой дүрмээр зохион байгуулагдсан зангилаанууд болон тэдгээрийг холбосон холбоосуудыг агуулдаг. Зангилаа нь мэдээлэлийг хадгалах ердийн нэг объект ба холбоос нь хоёр зангилааны хоорондын харилцааг тодорхойлдог. Холбоосоор холбогдсон модны дараалсан зангилаануудын жагсаалтыг зам гэнэ.

Модыг ингэж сурах нь байгаль дээрхтэй адилтгаж ойлгоход хэрэгтэй ч компьютерын ухаанд дараах байдлаар зурдаг. Амьдрал дээр мод бүтцээр илэрхийлж болох, илүү тохиромжтой олон тооны өгөгдлийг нэрлэж болно. Жишээ нь хүмүүсийн ургийн бичиг, байгуулгын зохион байгуулалтын бүтэц, Байгаль, техникийн нийлмэл системийн бүтэц г.м. Өгөгдлийн мод бүтэц дээр боловсруулалт хийнэ гэдэг үнэн чанартаа модны үндсээс навч хүртэл дээшээ, доошоо салаа мөчрөөр дамжин нэвтрэлт хийнэ гэсэн үг. Хоёртын модонд нэвтрэлт нь сонгосон алгоритмаасаа хамаарч Preorder, Inorder, Postorder, Levelorder гэсэн 4 төрөлд хуваагддаг.

Preorder нэвтрэлт:

public static void preOrder(BinaryTreeNode t)

{

   if (t != null)

  {

      visit(t);

      preOrder(t.leftChild);

      preOrder(t.rightChild);

   }

}

inOrder нэвтрэлт:

public static void inOrder(BinaryTreeNode t)

{

  if (t != null)

  {

     inOrder(t.leftChild);

     visit(t);

     inOrder(t.rightChild);

  }

}

PostOrder нэвтрэлт:

public static void postOrder(BinaryTreeNode t)

{

   if (t != null)

   {

      postOrder(t.leftChild);

      postOrder(t.rightChild);

      visit(t);

   }

}

LevelOrder нэвтрэлт:

public static void LevelOrder(BinaryTreeNode t)

{

   while (t != null)

  {

      t –д зочлоод хүүхдүүдийг нь FIFO дараалалд хийнэ;

      зангилааг FIFO дарааллаас устгаж, дуудна t;

     // дараалал хоосон бол устгал null –г буцаана

   }

}

Компьютерийн ухаанд хоёртын моднь өргөн хэрэглэгддэг өгөгдлийн бүтэц юм. Мод нь зангилаатай байдаг бөгөөд ихдээ 2 хүүхэд зангилаатай байдаг (баруун хүүхэд ба зүүн хүүхэд ).Үндэс (root node) нь модны бүх зангилааны өвөг дээдэс нь болох ба модны аль ч зангилаа толгой зангилаанаас хамааралтай байна. Мод нь толгой зангилаанаас өөр зангилаагүй бол хоосон мод болно. Хоёртын мод-онд бүх зангилааны түвшин нь ихэвчлэн хоёр байдаг. n зангилаатай мод байвал n-1 нь мөчир эсвэл түвшин болно. Хоёртын мод нь binarySearchTrees эсвэл binaryHeaps- ийн хэрэгжүүлдэг. Энэ нь хайх болон эрэмблэх гэсэн давуу талуудыг зэрэг тусгасан.

Хоёртын модны онцгой хэрэглээ нь K-ary tree юм.

Хоёртын мод нь модны онцгой нэг тохиолдол бөгөөд зангилаа бүр нь хоёроос илүүгүй дэд зангилаатай байдаг. Хэрэв нэг ч зангилаа агуулаагүй бол хоосон мод буюу null мод/зангилаа гэж нэрлэнэ. Зангилааны хоёр дэд зангилааг зүүн дэд загилаа ба баруун дэд зангилаа гэж ялгадаг. Хоёртын модны зангилаа нь нэг эсвэл хоёр хүүхэд зангилаа агуулж болно.

Модны хамгийн сүүлчийн түвшингээс бусад түвшинд дотоод загилаагаар гүйцэд дүүргэсэн бол түүнийг дүүрэн хоёртын мод гэнэ. Дүүрэн хоёртын модны хамгийн сүүлчийн түвшинд зөвхөн гадаад зангилааг агуулна. Харин дотоод зангилааг агуулах хамгийн сүүлчийн түвшингийн зөвхөн баруун талд зарим гадаад зангилаа байвал түүнийг гүйцэд мод гэнэ.

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

Модны үндэс(Definitions for rooted trees)

·         Чиглэлтэй холбоос нь эцэгээс хүүрүү чиглэж холбоно.

·         Толгой зангилаа нь эцэггүй байна. Модонд ганц л толгой зангилаа байна.

·         Навчин зангилаа нь хүүхэдгүй байна.

·         Толгой зангилаанаас хамгийн доод талын зангилаа хүртэлх замын урт нь модны урт болно.

·         Нэг эцэгтэй зангилаанууд нь ах дүүс болно.

·         Хэрвээ p зангилаа нь толгой зангилаанаас q зангилаа хүртэлх зам дээр байвал p зангилаа нь q зангилааны эцэг болно.

·          

Хоёртын модны шинж чанарууд(Properties of binary treesТөгс хоёртын модны n зангилааны тоог олохдоо дараах томъёог ашиглана. n = 2^h+1-1 (h нь модны түвшин)

·         Хоёртын модны n зангилааны тоог олохдоо өндөр h багадаа n = h + 1 ихдээ n = 2^h+1-1 (h нь модны түвшин)

·         Төгс хоёртын модны навчит зангилаануудын тоог олохдоо дараах томъёог ашиглана. l = 2^h

·         Төгс хоёртын модны n зангилааны тоог олохдоо дараах томъёог ашиглана. n = 2l-1 (l нь модны навчит зангилаануудын тоо)

·         Бүрэн төгс хоёртын модны Null холбоосын тоог олохдоо (хүүхэдгүй зангилаанууд) (n+1).

·         Бүрэн төгс хоёртын модны дотоод зангилааны тоо (навчгүй зангилаа) ⌊ n/2 ⌋.