Хоёртын мод

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

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

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

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

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

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

Чиглэлтэй холбоос нь эцэгээс хүүрүү чиглэж холбоно.
Толгой зангилаа нь эцэггүй байна. Модонд ганц л толгой зангилаа байна.
Навчин зангилаа нь хүүхэдгүй байна.
Толгой зангилаанаас хамгийн доод талын зангилаа хүртэлх замын урт нь модны урт болно.
Нэг эцэгтэй зангилаанууд нь ах дүүс болно.
Хэрвээ p зангилаа нь толгой зангилаанаас q зангилаа хүртэлх зам дээр байвал p зангилаа нь q зангилааны эцэг болно.

Чанар

Чанар 1:

Модны ямар нэг хоёр буюу гурав аа бас дөрөв зангилааг холбох ганц зам байна. Аль ч хоёр зангилааг авч үзэхэд ядаж нэр ерөнхий өвөг зангилаа олдоно. Ийм ерөнхий эх зангилаанаас уг хоёр зангилаанд хүрэх зам нь давтагдашгүй бөгөөд эдгээрийг нийлүүлснээр зөвхөн ганц зам олдоно.

Чанар 2:

N зангилаа бүхий мод N-1 холбоостой байна. Энэ чанар нь үндсэн зангилаанаас бусад бүх зангилаа нь зөвхөн ганц эх зангилаанд шууд холбогдоно гэдгээс мөрдөн гарна.

Чанар 3:

N дотоод зангилаа бүхий хоёртын мод нь N+1 гадаад зангилаатай байна.

Чанар 4:

N дотоод зангилаа бүхий хоёртын модны гадаад замын урт нь дотоод замын уртаас 2N-ээр илүү байдаг.

Чанар 5:

Хоёртын модны i дүгээр түвшинд хамгийн ихдээ 2 i зэрэг байна.

Чанар 6:

n өндөртэй хоёртын модны максиум зангилааны тоо нь 2-ийн n зэргээс хасдаг нь 1 тэй тэнцүү байна.

Чанар 7:

N дотоод зангилаа бүхий дүүрэн хоёртын модны өндөр нь ойролцоогоор Log хоёр суурьтай И байна.

Хоёртын модны төрөл(Types of binary tree)

Үндэстэй хоёртын мод бол хамгийн дээд талдаа 2 хүүг агуулсан толгой зангилаатай мод юм.
Зөв хоёртын мод гэдэг нь зангилаа бүрээс биш, навч бүртээ 2 хүүтэй модыг хэлнэ. Эсвэл хоёртын модны зангилаа бүр нь яг 0 юмуу 2 хүүтэй байж болно.
Төгс хоёртын мод нь эцэг болгон 2 хүүтэй, бүх навчнууд нь ижил түвшинд байрлах мод юм.Төгс хоёртын модны жишээ бол ургын мод - хүн бүр 2 эцэгтэй (нэг нь аав, нэг нь ээж);
Бүрэн хоёртын мод аль ч түвшинд сүүлийнхийг хасах боломжтой, бүгд дүүрсэн, мөн бүх зангилаанууд зүүн хүүтэй байх боломжтой. ........... сүүлийн түвшин дүүрээгүй. Энэ төрөл бол мэргэшсэн өгөгдлийн бүтцэд хэрэглэгддэг гэгддэг.
Хязгааргүй хоёртын мод зангилаа бүр 2 хүүтэй түвшингийн тоо хязгааргүйгээр тоологдох. Хязгааргүй тоологдох бүх зангилаануудын олонлог, гэвч бүх хязгааргүй замын олонлог толгой тоологдохгүй.
Тэнцвэртэй хоёртын мод. Ерөнхийдөө хоёртын модны түвшний зүүн болон баруун дэд моднууд зангилаа бүрээсээ 1 юмуу нэлээд багаар ялгаатай байна гэж тодорхойлсон.

Хоёртын модны шинж чанарууд(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 ⌋.

Хоёртын модонд нэвтрэх аргууд

Хоёртын модонд нэвтрэх 4 арга байдаг

Pre-order

Үндэсдээ нэвтрэнэ.
Зүүн хүүхэддээ нэвтрэнэ.
Баруун хүүхэддээ нэвтрэнэ.

In-order

Зүүн хүүхэддээ нэвтрэнэ.
Үндэсдээ нэвтрэнэ.
Баруун хүүхэддээ нэвтрэнэ.

Post-order

Зүүн хүүхэддээ нэвтрэнэ.
Баруун хүүхэддээ нэвтрэнэ.
Үндэсдээ нэвтрэнэ.

Level-order

Түвшин түвшингээр нь нэвтэрнэ.

Хоёртын мод байгуулах

Хоёртыг модыг нэвтрүүлэх нэг арга бол түүний зангилааг өгөгдсөн болон хоёр (зүүн/баруун) холбоос агуулах өгөгдлийн хийсвэр төрлөөр тодорхойлдог.

Хоёртын модонд нэвтрэлт

сонгосон алгоритмаасаа хамаарч Preorder, Inorder, Postorder, Levelorder гэсэн 4 төрөлд хуваагддаг. Java кодоор харуулбал:

 public static void preOrder(BinaryTreeNode t)

{

  if (t != null)
 {
     visit(t);
     preOrder(t.leftChild);
     preOrder(t.rightChild);
  }

}

public static void inOrder(BinaryTreeNode t) {

  if (t != null)
  {
     inOrder(t.leftChild);
     visit(t);
     inOrder(t.rightChild);
  }

}

public static void postOrder(BinaryTreeNode t) {

  if (t != null)
  { 
     postOrder(t.leftChild);
     postOrder(t.rightChild);
     visit(t);
  }

}

public static void postOrder(BinaryTreeNode t) {

  while (t != null)
 {
     t –д зочлоод хүүхдүүдийг нь FIFO дараалалд хийнэ;
     зангилааг FIFO дарааллаас устгаж, дуудна t;
    // дараалал хоосон бол устгал null –г буцаана
  }

}

Pre-order preorder(node)

 if node == null then return
 visit(node)
 preorder(node.left) 
 preorder(node.right)

iterativePreorder(node)

 parentStack = empty stack
 while not parentStack.isEmpty() or node ≠ null
   if node ≠ null then
     visit(node)
     if node.right ≠ null then
       parentStack.push(node.right)
     node = node.left
   else
     node = parentStack.pop()

In-order inorder(node)

 if node == null then return
 inorder(node.left)
 visit(node)
 inorder(node.right)

iterativeInorder(node)

 parentStack = empty stack
   while not parentStack.isEmpty() or node ≠ null
    if node ≠ null then
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right

Post-order postorder(node)

 if node == null then return
 postorder(node.left)
 postorder(node.right)
 visit(node)

iterativePostorder(node)

  stack = empty stack  
  lastnodeprinted = NULL 
  WHILE [NOT stack.isEmpty() OR node ≠ NULL]
      IF (node)
          stack.push(node)
          node = node->left
      ELSE
          peeknode = stack.peek()
          IF (peeknode->right AND lastnodeprinted ≠ peeknode->right) 
              /* if visiting node from left child AND right child exists, move right */
              node = peeknode->right
          ELSE
              stack.pop() 
              visit(peeknode)
              lastnodeprinted = peeknode