6_tree.md

Мод

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

Жишээ болгон дараах хоёртын модны (хоёр мөчиртэй) бүтцийг сонирхоё. Энэ модны зангилаа бүр нь нэг үг агуулах ба зангилаа бүрийн зүүн салаа нь уг үгээс бага эрэмбэтэй үгүүдийг, баруун салаа нь түүнээс их эрэмбэтэй үгүүдийг агуулахаар байрлуулсан байна.

Жишээлбэл, orange үгийг модонд нэмэхдээ эхлээд үндэс болох lemon-оос эхлэн харьцуулна (цагаан толгойн эрэмбээр), orange > lemon учраас баруун салаагаар бууж pear дээр очно. Ингээд orange < pear учраас зүүн салаанд очиж байрлана.

Модны хамгийн дээр байгаа элементийг үндэс, доод үзүүрийн элементүүдийг навчнууд гэнэ. Зангилаа бүр зүүн, баруун гэсэн хоёр холбоосыг агуулна, эдгээр нь зүүн, баруун салаа модуудыг заана.

Модыг дараах бүтцээр зохион байгуулж болно.

// модны нэг зангилаа
type Node struct {
  right, left *Node // зүүн, баруун зангилаа
  value string	 // зангилаан дээрх утга
}

// мод бүтэц
type BinaryTree struct {
  root *Node // оройн элементийг заана
}

Модонд өгөгдөл нэмэх

Модтой ажиллах үед рекурсив функц маш чухал байдаг.

Жишээ нь өгөгдөл нэмэх алгоритм нь:

1. Хэрэв мод буюу дэд мод хоосон бол шинэ зангилаа үүсгэх
2. Хэрэв өгөгдөл аль хэдийн модонд байвал ямар нэг зүйл хийхгүй
3. Эсрэг тохиолдолд зүүн эсвэл баруун зангилаагаар 1 алхамаас эхлэн рекурсээр давтах

func (b *BinaryTree) insert(root *Node, val string) *Node {
  switch {
  case root == nil:
    return addNode(val)
  case val <= root.value:
    root.left = b.insert(root.left, val)
  case val > root.value:
    root.right = b.insert(root.right, val)
  }
  return root
}

func addNode(val string) *Node {
  return &Node{nil, nil, val}
}

func (b *BinaryTree) Insert(val string) (n *Node) {
  if b.root == nil {
    n = addNode(val)
    b.root = n
  } else {
    n = b.insert(b.root, val)
  }
  return
}

Модонд fig гэсэн үгийг нэмэхэд алгоритм яаж ажиллахыг харая. Эхлээд fig үгийг lemon-той харьцуулна. fig нь бага эрэмбэтэй учраас apple руу очно, fig том учраас grape рүү очно. fig нь grape-ээс бага учраас зүүн талын холбоос дээр залгахыг оролдоно. Хэрэв энэ зангилаа nil бол шинэ зангилаа үүсгэнэ.

Модноос элемент хайх

Модноос элемент хайхад мөн рекурс ашиглана.

Хайх алгоритм нь:

1. Хайж байгаа утгыг модны өгөгдсөн зангилааны утгатай харьцуулна.
2. Хэрэв тэнцүү бол өгөгдөл олдлоо гэсэн үг.
3. Бага бол зүүн зангилаагаар орж 1 алхамд шилжинэ
4. Их бол баруун зангилаагаар орж 1 алхамд шилжинэ

func find(n *Node, val string) {
  if (n == nil) {
    return
  }
  if n.value == val {
    fmt.Printf("%s үг модонд олдлоо!\n", val)
  }
  if val <= n.value {
    find(n.left, val)
  } else {
    find(n.right, val)
  }
}

func (b *BinaryTree) Find(val string) {
  find(b.root, val)
}

Модонд их элементүүд баруун салаанд, бага элементүүд зүүн салаанд байрлаж байгаа нь тодорхой үед элемент хайх нь хурдан байх нь ойлгомжтой юм. Тухайлбал grape үгийг хайхад эхлээд lemon-той харьцуулна, grape нь цагаан толгойн эрэмбээр lemon-оос бага учраас зүүн салаа уруу орно. Зүүн салааны оройн элемент нь apple байна, grape > apple учраас баруун салаа уруу орно. Ингээд grape элементийг 2 удаагийн харьцуулалтын дараа олж байна.

Модыг хэвлэх

Модны бүх элементийг дэлгэцэнд хэвлэхэд маш хялбархан.

Хэвлэх алгоритм нь дараах байдалтай:

1. Хоосон мод бол юу ч хэвлэхгүй дуусгана
2. Эсрэг тохиолдолд эхлээд зүүн салааг хэвлэнэ, дараа нь тухайн зангилааг өөрийг нь, дараа нь баруун зангилааг хэвлэнэ.

func printTree(n *Node) {
    if n == nil {
        return;
    }
    printTree(n.left);
    fmt.Printf("%s\n", n.value)
    printTree(n.right);
}

func (b *BinaryTree) Print() {
  printTree(b.root)
}

Дээрх функцүүдийг main() функцэд нэгтгээд бичвэл:

func main() {
  b := new(BinaryTree)
  b.Insert("lemon")
  b.Insert("apple")
  b.Insert("grape")
  b.Insert("orange")
  b.Insert("plum")
  b.Insert("pear")

  b.Print()
  b.Find("pear")
}