ບົດທີ 5 Trees

2. ປະເພດຂອງ Trees

ມີຫຼາຍຊະນິດຂອງຕົ້ນໄມ້, ແຕ່ລະຄົນມີຄຸນສົມບັດແລະການນໍາໃຊ້ທີ່ເປັນເອກະລັກຂອງຕົນເອງ. ນີ້ແມ່ນບາງຊະນິດຂອງຕົ້ນໄມ້ທົ່ວໄປທີ່ສຸດ:

1. 1. ຕົ້ນໄມ້ໄບນາຣີ: ໄມ້ຢືນຕົ້ນສອງແມ່ນຕົ້ນໄມ້ທີ່ແຕ່ລະຂໍ້ມີລູກນ້ອຍທີ່ສຸດສອງລູກ, ເອີ້ນວ່າລູກຊ້າຍ ແລະ ລູກຂວາ.

   2. Binary Search Tree (BST): ຕົ້ນໄມ້ຄົ້ນຫາໄບນາຣີແມ່ນເປັນໄມ້ຢືນຕົ້ນຄູ່ທີ່ລູກຊ້າຍຂອງ node ມີພຽງແຕ່ຄ່າທີ່ນ້ອຍກວ່າ node, ແລະລູກຂວາຂອງ node ມີພຽງແຕ່ຄ່າທີ່ໃຫຍ່ກວ່າ node ເທົ່ານັ້ນ. ຄຸນສົມບັດນີ້ອະນຸຍາດໃຫ້ດໍາເນີນການຄົ້ນຫາແລະຈັດຮຽງຢ່າງມີປະສິດທິພາບ.

   3. AVL Tree: ຕົ້ນໄມ້ AVL ແມ່ນຕົ້ນໄມ້ຄົ້ນຫາຄູ່ທີ່ມີຄວາມສົມດູນ, ຊຶ່ງຫມາຍຄວາມວ່າຄວາມສູງຂອງຕົ້ນໄມ້ຍ່ອຍຊ້າຍແລະຂວາຂອງ node ໃດແຕກຕ່າງກັນໂດຍສູງສຸດຫນຶ່ງ. ນີ້ຮັບປະກັນການປະຕິບັດການຄົ້ນຫາແລະການແຊກທີ່ມີປະສິດທິພາບ.

   4. ຕົ້ນໄມ້ສີແດງ-ດຳ: ຕົ້ນໄມ້ສີແດງ-ດຳແມ່ນຕົ້ນໄມ້ຊອກຫາຄູ່ທີ່ແຕ່ລະຂໍ້ມີສີແດງ ຫຼື ດຳ. ຕົ້ນໄມ້ມີຄວາມສົມດູນໂດຍການຮັບປະກັນວ່າບໍ່ມີເສັ້ນທາງຈາກຮາກໄປຫາໃບຍາວກວ່າສອງເທົ່າຂອງເສັ້ນທາງອື່ນ.

   5. B-Tree: B-tree ແມ່ນໂຄງສ້າງຂໍ້ມູນຕົ້ນໄມ້ທີ່ຖືກນໍາໃຊ້ເພື່ອເກັບຮັກສາຂໍ້ມູນຈໍານວນຫລາຍໃນແຜ່ນຫຼືໃນຫນ່ວຍຄວາມຈໍາ. ມັນເປັນຕົ້ນໄມ້ທີ່ສົມດູນທີ່ຊ່ວຍໃຫ້ການຄົ້ນຫາທີ່ມີປະສິດທິພາບ, ໃສ່, ແລະລຶບການດໍາເນີນງານ.

   6. Trie: A trie ແມ່ນໂຄງສ້າງຂໍ້ມູນຕົ້ນໄມ້ທີ່ໃຊ້ສໍາລັບການດຶງລະຫັດທີ່ມີປະສິດທິພາບຈາກຊຸດໃຫຍ່ຂອງສາຍ. ມັນຍັງເປັນທີ່ຮູ້ຈັກເປັນຕົ້ນໄມ້ prefix, ເພາະວ່າແຕ່ລະ node ເປັນຕົວແທນຂອງຄໍານໍາຫນ້າຂອງຫນຶ່ງຫຼືຫຼາຍສາຍ.

   7. Segment Tree: segment tree ແມ່ນຕົ້ນໄມ້ຄູ່ທີ່ໃຊ້ສໍາລັບການສອບຖາມ range ໃນ arrays ຫຼືໂຄງສ້າງຂໍ້ມູນອື່ນໆ. ມັນອະນຸຍາດໃຫ້ມີການສອບຖາມປະສິດທິພາບຂອງຜົນລວມ, ຕໍາ່ສຸດ, ສູງສຸດ, ຫຼືຄ່າລວມອື່ນໆຂອງຊ່ວງຂອງອົງປະກອບໃນອາເຣ.

   8. heap: heap ເປັນຕົ້ນໄມ້ຄູ່ທີ່ຄ່າຂອງແຕ່ລະ node ຫຼາຍກວ່າ ຫຼືເທົ່າກັບຄ່າຂອງລູກຂອງມັນ (ໃນ heap ສູງສຸດ) ຫຼືຫນ້ອຍກວ່າ ຫຼືເທົ່າກັບຄ່າຂອງລູກຂອງມັນ (ໃນ min heap). Heaps ຖືກໃຊ້ທົ່ວໄປໃນແຖວບູລິມະສິດ ແລະລະບົບກຣາຟ.

ຄວາມເຂົ້າໃຈກ່ຽວກັບຄຸນສົມບັດແລະປະເພດຂອງຕົ້ນໄມ້ເປັນສິ່ງສໍາຄັນສໍາລັບການດໍາເນີນໂຄງການທີ່ມີປະສິດຕິຜົນແລະສໍາລັບການເລືອກໂຄງສ້າງຂໍ້ມູນທີ່ເຫມາະສົມກັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດໄວ້.

3. ຄວາມສາມາດພື້ນຖານຂອງ Trees

ຕົ້ນໄມ້ສະຫນັບສະຫນູນບາງການດໍາເນີນງານພື້ນຖານທີ່ຖືກນໍາໃຊ້ທົ່ວໄປໃນການຂຽນໂປຼແກຼມ. ນີ້ແມ່ນບາງການດໍາເນີນງານທີ່ສໍາຄັນທີ່ສຸດ:

1. ການໃສ່: ການເພີ່ມ node ໃຫມ່ກັບຕົ້ນໄມ້ໃນສະຖານທີ່ທີ່ເຫມາະສົມໂດຍອີງໃສ່ມູນຄ່າຂອງມັນ.

2. ການລຶບ: ການຖອນ node ຈາກຕົ້ນໄມ້ໃນຂະນະທີ່ຮັກສາຄຸນສົມບັດຂອງຕົ້ນໄມ້.

3. ການເດີນທາງຜ່ານ: ໄປຢ້ຽມຢາມແຕ່ລະ node ໃນຕົ້ນໄມ້ໃນຄໍາສັ່ງສະເພາະ. ມີສາມປະເພດຕົ້ນຕໍຂອງການຂ້າມຜ່ານ:

• • • In-order traversal: ການໄປຢ້ຽມຢາມຕົ້ນໄມ້ຍ່ອຍທາງຊ້າຍ, ຫຼັງຈາກນັ້ນ node ໃນປັດຈຸບັນ, ຫຼັງຈາກນັ້ນເປັນຕົ້ນໄມ້ຍ່ອຍຂວາ.

    • Pre-order traversal: ການໄປຢ້ຽມຢາມ node ໃນປັດຈຸບັນ, ຈາກນັ້ນ subtree ຊ້າຍ, ຫຼັງຈາກນັ້ນ subtree ຂວາ.

    • Post-order traversal: ການໄປຢ້ຽມຢາມຕົ້ນໄມ້ຍ່ອຍຊ້າຍ, ຈາກນັ້ນຕົ້ນໄມ້ຍ່ອຍຂວາ, ຈາກນັ້ນແມ່ນຂໍ້ປະຈຸບັນ.

4. ຄົ້ນຫາ: ຊອກຫາຂໍ້ສະເພາະໃນຕົ້ນໄມ້ໂດຍອີງໃສ່ມູນຄ່າຂອງມັນ.

5. ຄວາມສູງ: ກັບຄືນຄວາມສູງຂອງຕົ້ນໄມ້, ເຊິ່ງເປັນຈໍານວນແຄມຂອງເສັ້ນທາງທີ່ຍາວທີ່ສຸດຈາກຮາກໄປຫາຂໍ້ໃບ.

6. ຂະໜາດ: ສົ່ງຄືນຈຳນວນຂອງ nodes ໃນຕົ້ນໄມ້.

ຄວາມສັບສົນທີ່ໃຊ້ເວລາຂອງການດໍາເນີນງານເຫຼົ່ານີ້ແມ່ນຂຶ້ນກັບການປະຕິບັດສະເພາະຂອງຕົ້ນໄມ້. ຕົວຢ່າງ, ການປະຕິບັດການແຊກແລະການລົບຢູ່ໃນຕົ້ນໄມ້ຄົ້ນຫາຄູ່ໃຊ້ເວລາ O(log n) ໂດຍສະເລ່ຍ, ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງ nodes ໃນຕົ້ນໄມ້. ການປະຕິບັດການຂ້າມຜ່ານໃຊ້ເວລາ O(n), ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງ nodes ໃນຕົ້ນໄມ້.

ມັນເປັນສິ່ງສໍາຄັນທີ່ຈະເລືອກເອົາປະເພດທີ່ເຫມາະສົມຂອງຕົ້ນໄມ້ແລະການປະຕິບັດສໍາລັບຄໍາຮ້ອງສະຫມັກທີ່ໄດ້ຮັບໂດຍອີງໃສ່ຄວາມຕ້ອງການສະເພາະຂອງບັນຫາທີ່ມີຢູ່ໃນມື. ຕົວຢ່າງເຊັ່ນ, ຕົ້ນໄມ້ຄົ້ນຫາສອງແມ່ນເປັນປະໂຫຍດສໍາລັບການຄົ້ນຫາແລະການຈັດລຽງ, ໃນຂະນະທີ່ຕົ້ນໄມ້ segment ມີປະໂຫຍດສໍາລັບການສອບຖາມລະດັບໃນ arrays.