บทความ: เทคนิคการเขียนโค้ดเพื่อการจัดการข้อมูลในภาษา TypeScript โดยใช้ Binary Search Tree
การจัดการข้อมูลเป็นหนึ่งในปัญหาหลักที่นักพัฒนาโปรแกรมมีความจำเป็นต้องเผชิญอย่างไม่ว่าจะบ่อยขนาดไหน โครงสร้างข้อมูลที่เรียกว่า Binary Search Tree (BST) ถือเป็นหนึ่งในเทคนิคที่ได้รับการนิยมมากที่สามารถช่วยเราจัดการกับข้อมูลได้อย่างมีประสิทธิภาพ ในบทความนี้ เราจะสำรวจการใช้งาน BST ในภาษา TypeScript เพื่อการ insert, update, find และ delete ข้อมูล พร้อมทั้งอธิบายข้อดีข้อเสียของมัน
BST คือ โครงสร้างข้อมูลประเภทหนึ่งที่มีคุณสมบัติเฉพาะตัว เช่น แต่ละโหนดจะมีค่ามากกว่าโหนดทั้งหมดใน left subtree และน้อยกว่าโหนดทั้งหมดใน right subtree ซึ่งสามารถช่วยเพิ่มประสิทธิภาพในการค้นหาข้อมูลได้
ในภาษา TypeScript, BST สามารถถูกสร้างขึ้นมาโดยการออกแบบคลาสที่มี properties และเมทอดที่เกี่ยวข้อง เช่น insert, find, update, และ delete.
Insert
การเพิ่มข้อมูล (insert) เริ่มจากการเทียบค่าข้อมูลที่ต้องการเพิ่มกับค่าของโหนดปัจจุบัน ถ้าน้อยกว่าจะไปที่ left subtree และถ้ามากกว่าไปที่ right subtree กระทั่งจะเจอตำแหน่งที่เหมาะสมแล้วจึงเพิ่มข้อมูลลงไป
class TreeNode {
key: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(key: number) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
root: TreeNode | null;
// ...
insert(key: number): void {
let newNode = new TreeNode(key);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
private insertNode(node: TreeNode, newNode: TreeNode): void {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
// ...
}
Find
การค้นหา (find) ใน BST ทำตามหลักการเดียวกับการ insert คือเริ่มที่รากแล้วมุ่งไปที่ left หรือ right subtree ตามค่าที่ต้องการค้นหา และวนซ้ำจนกว่าจะเจอข้อมูลหรือไม่เจอ
// ... continuation of the BinarySearchTree class
find(key: number): TreeNode | null {
return this.search(this.root, key);
}
private search(node: TreeNode | null, key: number): TreeNode | null {
if (node === null || node.key === key) {
return node;
}
if (key < node.key) {
return this.search(node.left, key);
} else {
return this.search(node.right, key);
}
}
// ...
Update
การปรับปรุงข้อมูล (update) อาจทำได้โดยการเข้าถึงโหนดด้วยเมทอด find แล้วเปลี่ยนค่าข้อมูล อย่างไรก็ตาม ในโครงสร้าง BST นั้นการ update โดยตรงอาจไม่สามารถทำได้เสมอไป อาจต้องใช้การเพิ่มและลบโหนดแทน
Delete
การลบข้อมูลจาก BST เป็นกระบวนการที่ซับซ้อนกว่าการ find และ insert เนื่องจากต้องพิจารณากรณีต่างๆ เช่น การลบโหนดที่มีลูกหนึ่งโหนด ลูกสองโหนด หรือไม่มีลูกเลย
// ... continuation of the BinarySearchTree class
delete(key: number): void {
this.root = this.deleteNode(this.root, key);
}
private deleteNode(node: TreeNode | null, key: number): TreeNode | null {
// Base case: If the tree is empty
if (node === null) {
return node;
}
// Otherwise, recur down the tree
if (key < node.key) {
node.left = this.deleteNode(node.left, key);
} else if (key > node.key) {
node.right = this.deleteNode(node.right, key);
} else {
// Node with only one child or no child
if (node.left === null) {
return node.right;
} else if (node.right === null) {
return node.left;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
node.key = this.minValue(node.right);
// Delete the inorder successor
node.right = this.deleteNode(node.right, node.key);
}
return node;
}
private minValue(node: TreeNode): number {
let minv = node.key;
while (node.left !== null) {
minv = node.left.key;
node = node.left;
}
return minv;
}
// ...
ข้อดี
1. การค้นหาที่รวดเร็ว: ถ้าโครงสร้าง balanced ได้ดี BST สามารถให้การค้นหาที่เป็น log(n) ด้วยการค้นหาครึ่งหนึ่งของข้อมูลในแต่ละขั้นของโครงสร้าง 2. การเรียงลำดับข้อมูลได้ง่าย: สามารถ traverse โครงสร้างโดย inorder ได้ข้อมูลที่เรียงลำดับข้อเสีย
1. โครงสร้างอาจไม่ balance: ถ้าข้อมูลที่เพิ่มไม่กระจายอย่างดี BST อาจ degenerate กลายเป็น linked list ทำให้ประสิทธิภาพการค้นหาลดลงกลายเป็น O(n) 2. ต้องดูแลการ balance: อาจจำเป็นต้องใช้ algorithmit like AVL trees หรือ Red-Black trees เพื่อการเก็บข้อมูลให้ balanced ซึ่งเพิ่มความซับซ้อนในการเลือกเรียนการเขียนโปรแกรมที่ EPT คุณจะได้สัมผัสกับหลักสูตรที่ครอบคลุมหลายเทคนิคและเครื่องมือในการจัดการข้อมูลซึ่งรวมถึงการใช้ BST ใน TypeScript พร้อมด้วยทีมงานผู้เชี่ยวชาญที่พร้อมจะแนะนำคุณให้เข้าใจได้ลึกซึ้งไม่ว่าจะในเรื่องของโครงสร้างข้อมูล หรือแม้แต่เทคนิกการเขียนโค้ดที่ทรงประสิทธิภาพ เรียนรู้การเขียนโปรแกรมอย่างมืออาชีพกับเราที่ EPT แล้วคุณจะได้ไม่แค่ความรู้แต่ยังรวมถึงประสบการณ์ที่จะช่วยให้คุณโดดเด่นในอาชีพนี้!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM