0

Binary Tree ແມ່ນຫຍັງ? ຄົ້ນຫາຂໍ້ມູນໄວ້ແທ້ບໍ?

ສະບາຍດີຜູ້ອ່ານທຸກຄົນ ມື້ນີ້ຈະມາເວົ້າກ່ຽວກັບ Binary Tree ເຊິ່ງເປັນຫົວຂໍ້ທີ່ຢາກເວົ້າມາດົນແລ້ວ ແຕ່ວ່າຕ້ອງໃຊ້ເວລາທຳຄວາມເຂົ້າໃຈ ເລີຍຫາກໍ່ມີເວລາມາຂຽນໃນບລັອກນີ້.

ເນື້ອຫາໃນບົດຄວາມທີ່ຈະເວົ້າກ່ຽວກັບ Concept ວ່າມັນເຮັດວຽກແນວໃດເທົ່ານັ້ນເນາະ ບໍ່ໄດ້ລົງໂຄ໋ດແທ້ (ເພາະແອັດມິນກະຍັງຂຽນບໍ່ໄດ້ເທື່ອ ເຂົ້າໃຈຂ້ອນຂ້າງຍາກ ^^”)

ກ່ອນອື່ນເຮົາມາເຂົ້າໃຈກັນກ່ອນວ່າ Tree ແມ່ນຫຍັງ?

ບາງຄົນອາດຈະວ່າ Tree ກະຕົ້ນໄມ້ຫັ້ນແລະ ອັນນັ້ນກະຖືກເນາະ ຫະຫະ, ຫລາຍຄົນອາດຈະຄຸ້ນໆຮູ້ສຶກວ່າເຄີຍໄດ້ຍິນຢູ່ໃສມາກ່ອນ ຫຼື ບາງຄົນເຄີຍຮຽນ Data Structure ມາແລ້ວກໍ່ໜ້າຈະຮູ້ດີ ຫຼື ໃຜບໍ່ຄຸ້ນກໍ່ອ່ານຕໍ່ໄດ້ເລີຍ

Tree ແມ່ນ ໂຄງສ້າງຂໍ້ມູນແບບຕົ້ນໄມ້ເຊິ່ງ Tree ໜຶ່ງຈະປະກອບໄປດ້ວຍ 1 root node ແລ້ວແຕກອອກເປັນ node ຍ່ອຍຫລາຍໆໂໜດເອີ້ນວ່າ ໂໜດລູກ (Child Node)

ແລ້ວເມື່ອມີ ໂໜດລູກ ແລ້ວ ໂໜດລູກ ຍັງສາມາດເປັນ ໂໜດພໍ່ແມ່ (Parent Node) ໄດ້ອີກ ໂດຍສາມາດແຕກເປັນໂໜດຍ່ອຍໆໄດ້ອີກ. (ສັງເກດຈາກຮູບລຸ່ມນີ້)

 

ໃນບົດຄວາມນີ້ແອັດມິນຈະເນັ້ນໄປ Binary Search Tree ກັບ Array ເຊິ່ງແອັດຈະສະແດງໃຫ້ເຫັນເຖິງຄວາມແຕກຕ່າງຂອງ 2 ອັນນີ້ ໃຫ້ຜຸ້ອ່ານເຫັນໄດ້ຢ່າງຊັດເຈນເປັນເນື້ອເປັນຕ່ອນໂລດເນາະ.

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

ແລ້ວຈາກທີ່ແອັດມິນວ່າ Tree ມັນຂຽນຍາກ, ເຂົ້າໃຈຍາກ ແລ້ວມັນດີກວ່າ Array ແນວໃດ?

ຄຳຕອບກໍ່ຄື ຈຳນວນຄັ້ງໃນການຄຳນວນ ຂອງໂປແກມທີ່ເຮົາຂຽນນັ້ນເອງ.!

ເປັນຫຍັງຄືວ່າຊັ້ນ, ມາເບິ່ງຕົວຢ່າງເລີຍດີກວ່າເພື່ອໃຫ້ເຫັນພາບແຈ້ງໆ.

#include<stdio.h>
/* AUTHOR Frankkung.com */
int main(){
	int numbers[15] = {50,15,30,70,90,62,53,100,64,34,51,120,118,103,79};
	int max=numbers[0];
	
	for(int i = 0; i<=15;i++){
		if(max<numbers[i]){
			max = numbers[i];
		}
	}
	
	/* RESULT = 120 */
	printf("MAX : %d",max);
	
}

ຈາກໂຄ໋ດພາສາ C ທາງເທິງແມ່ນໃຫ້ໂປແກມຫາ ຄ່າໃຫຍ່ສຸດ ໃນ Array ເຊິ່ງການເຮັດວຽກຂອງໂປແກມກໍ່ຄື

ເກັບຄ່າ element ທຳອິດຂອງ array ກໍ່ຄື numbers[0] ເກັບໄວ້ແລ້ວເອົາເຂົ້າ for loop ເພື່ອປຽບທຽບເທື່ອລ່ະຄ່າ ຫາຄ່າໃຫຍ່ສຸດ ແລ້ວກໍ່ເກັບເຂົ້າ max ຜົນລັບທີ່ໄດ້ກໍ່ຄື 120 ນັ້ນເອງ.

ຈະເຫັນໄດ້ວ່າໂປແກມຈະເຮັດວຽກປານມານວ່າ  Array ຈະຕ້ອງປຽບທຽບໄປຈົນໝົດຊຸດຂໍ້ມູນໂດຍຫລັກການຄຳນວນແບບຄ້າວໆ ຖ້າ ມີຂໍ້ມູນ 1,000,000 ຊຸດ

array ຕ້ອງໃຊ້ຄຳນວນເທື່ອລະອັນ, ຖ້າເປັນ case ທີ່ໂຫດຮ້າຍທາລຸນສຸດໆ ເຮົາຕ້ອງ loop ເປັນລ້ານເທື່ອຈຶ່ງຈະໄດ້ຜົນລັບ.

ແຕກຕ່າງກັບ Binary Tree ເພິ່ນຈະທຳການ Sort ຂໍ້ມູນກ່ອນແລ້ວເກັບເປັນເບື້ອງ ເວລາຄົ້ນຫາຂໍ້ມູນກໍ່ຈະທຳການປຽບທຽບເປັນເບື້ອງຖ້າໜ້ອຍກະຕັດອອກໝົດຟາກເລີຍ ແລະ Worst case ຂອງ BST ແມ່ນ O(n).

ຕົວຢ່າງ: ມີຊຸດຂໍ້ມູນ (13,15,14,34,4,40,47,49,48,55,45) ແລ້ວເຮົາມາຈັດກັນເຂົ້າ Tree ແລ້ວ ຈົ່ງຫາ 14

 

binary-tree-1-search

ຈະເຫັນໄດ້ວ່າ Binary Tree ຈະມີ root node ໃນນີ້ກໍ່ຄື 40 ແລ້ວແຍກອອກເປັນ 2 ກິ່ງນ້ອຍກວ່າຈະຢູ່ເບື້ອງ ຊາຍ ຫລາຍກວ່າ ຈະຢູ່ເບື້ອງຂວາ. Node ໜຶ່ງສາມາດມີ 2 child nodes ດັ່ງພາບຂ້າງເທິງ

ເນື່ອງຈາກເຮົາຈະຫາ 14 ເຮົາຮູ່ວ່າ 14<40 ເຮົາກໍ່ຈະຕັດຟາກເບື່ອງຂວາອອກໄປເລີຍ ເຫຼືອພຽງແຕ່ 4,34,14,13,15 ເຮົາມັນຈະເລື່ອນລົງຫາຢູ່ຕາມແຕ່ລະ node ຈະເຫັນໄດ້ກວ່າ ຫລຸດຜ່ອນເວລາໃນການຫາໄປໄດ້ຫລາຍເລີຍແມ່ນບໍ.

ອີກຕົວຢ່າງໃຫ້ສັງເກດເບິ່ງ

 

ການຊອກຫາຈຳນວນຄັ້ງໃນການຄຳນວນ ສຳລັບ Binary Tree ນັ້ນມີວີທີທາງຄະນິດສາດຢູ່ນັ້ນກໍ່ຄື

log2 (n)

ສະຫລຸບສິ່ງທີ່ຢາກໃຫ້ເຫັນ:

ຖ້າເຮົາມີຂໍ້ມູນຈຳນວນ n = 1,000,000 ຊຸດ

Worst Case ຂອງ Array ໝາຍເຖິງຂໍ້ມູນຢູ່ທ້າຍສຸດ ໂປແກມຕ້ອງຄຳນວນເຖິງແຕ່ລະຂໍ້ມູນຈົນຄົບລ້ານ.

ແຕ່ວ່າ, Worst Case ຂອງ Binary Tree ຈະເທຢ່າກັບ O(n).  ໂປແກມຈະຄຳນວນປະມານ 20 ຄັ້ງເທົ່ານັ້ນ! ຈະເຫັນໄດ້ວ່າຄວາມໄວ ແລະ ເວລາທີ່ເຮົາສາມາດປະຢັດໄດ້ນັ້ນມະຫາສານເລີຍ.

ຕອນນີ້ແອັດມິນກໍ່ກຳລັງສຶກສາໃຫ້ເຂົ້າໃຈໃຫ້ເລິກໆ ແລ້ວຈະມາເວົ້າເຖິງການຂຽນໂປແກມກັບ Binary Tree ອີກຄັ້ງເນາະຖ້າໃຜສົນໃຈກໍ່ສາມາດສຶກສາແລ້ວມາລົມກັບແອັດໄດ້ເດີ້.

 

ຂອບໃຈທີ່ອ່ານຈົນຈົບອີກຄັ້ງ!

ref:

http://www.tamemo.com/

https://www.l3nr.org/posts/240991

 

Frankkung

Frankkung

FULLSTACK DEVELOPER - PENETRATION TESTER