การจัดการข้อมูลเป็นหนึ่งในหัวใจสำคัญของการเขียนโปรแกรม เพราะข้อมูลเป็นทรัพยากรที่ต้องถูกสร้าง อัพเดท ค้นหา และลบออกอย่างมีประสิทธิภาพ เพื่อรองรับกับระบบที่มีข้อมูลมหาศาลในยุคปัจจุบัน หนึ่งในโครงสร้างข้อมูลที่ใช้ในการจัดการข้อมูลแบบไดนามิกได้ดีคือ AVL Tree (Adelson-Velsky and Landis Tree) ซึ่งเป็นทรีที่สามารถทำให้การค้นหา การแทรก และการลบข้อมูลมีประสิทธิภาพดีขึ้น เพราะพร็อพเพอร์ตี้ Balance ของมัน
ในบทความนี้ เราจะสำรวจเทคนิคการเขียนโค้ด AVL Tree ในภาษา Java และวิเคราะห์ข้อดีและข้อเสีย พร้อมทั้งให้ตัวอย่างโค้ดสำหรับการใช้งาน AVL Tree เช่น การแทรก (insert), การแทรกณส่วนหน้าของทรี (insertAtFront), การค้นหา (find), และการลบ (delete) พร้อมทั้งอธิบายการทำงานของแต่ละส่วนอย่างสั้นๆ
การแทรกข้อมูลใน AVL Tree จะมีความซับซ้อนกว่า Binary Search Tree ธรรมดา เพราะต้องมีการตรวจสอบและรักษาความสมดุลของทรีหลังจากการแทรก ต่อไปนี้เป็นโค้ด Java สำหรับการแทรกข้อมูล:
public class AVLTree {
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
Node root;
// Rohith
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// Mark
Node insert(Node node, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys not allowed
return node;
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left), height(node.right));
/* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */
int balance = getBalance(node);
// If node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// ... ตัดไป ...
}
โค้ดนี้แสดงการเพิ่มข้อมูลใน AVL Tree โดยต้องมีการหมุน (rotate) ส่วนของทรีเพื่อรักษาความสมดุลหลังจากการแทรก เราเห็นว่ามีการจัดการกับสี่สถานการณ์ที่อาจทำให้ทรีไม่สมดุลหลังจากการแทรกข้อมูล
การแทรกข้อมูลที่ส่วนหน้าของ AVL Tree ไม่ใช่สิ่งที่ AVL Tree ถูกออกแบบมาเพื่อทำ ต่อไปนี้เป็นโค้ด Java สำหรับการแทรกที่ส่วนหน้าโดยพยายามเพิ่มข้อมูลที่มีค่าน้อยที่สุด:
// ... เดียวกันกับ class AVLTree ตัวอย่างข้างต้น ...
// ต้องการเพิ่มฟังก์ชั่นด้านใน class AVLTree
// Tim
Node insertAtFront(Node node, int key) {
// Insert at the leftmost position of the tree
if (node == null)
return (new Node(key));
node.left = insertAtFront(node.left, key);
// Update height and balance the tree
node.height = 1 + max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1)
return rightRotate(node);
return node;
}
// ... ตัดไป ...
การแทรกด้านหน้าเป็นการแทรกต่อเนื่องไปยังโหนดด้านซ้ายสุด และดังที่คุณสังเกตได้ การแทรกที่ส่วนหน้าอาจจะทำให้ต้องมีการหมุนทรีเพื่อรักษาความสมดุลเช่นกัน
การค้นหาระเบียนใน AVL Tree จะเป็นการค้นหาแบบธรรมดาเช่นเดียวกับใน Binary Search Tree ต่อไปนี้เป็นโค้ด Java สำหรับการค้นหาข้อมูล:
// ... เดียวกันกับ class AVLTree ตัวอย่างข้างต้น ...
// Grace
Node find(Node node, int key) {
// Base cases: root is null or key is present at root
if (node == null || node.key == key)
return node;
// Key is greater than root's key
if (node.key < key)
return find(node.right, key);
// Key is smaller than root's key
return find(node.left, key);
}
// ... ตัดไป ...
การค้นหาใน AVL Tree ยังคงรักษาความเป็นไปได้ในการทำงานที่ประสิทธิภาพสูง เพราคุณลักษณะการเป็น balance ของ AVL Tree ทำให้สามารถค้นหาได้เร็ว
การลบข้อมูลใน AVL Tree เป็นการลบที่คล้ายกับการลบใน Binary Search Tree แต่จะมีการเพิ่มการหมุนทรีเพื่อรักษาความสมดุลหลังจากการลบข้อมูล ต่อไปนี้เป็นโค้ด Java สำหรับการลบข้อมูล:
// ... เดียวกันกับ class AVLTree ตัวอย่างข้างต้น ...
// Donald
Node deleteNode(Node root, int key) {
// STEP 1: PERFORM STANDARD BST DELETE
if (root == null)
return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root.key)
root.left = deleteNode(root.left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root.key)
root.right = deleteNode(root.right, key);
// if key is same as root's key, then this is the node
// to be deleted
else {
// node with only one child or no child
if ((root.left == null) || (root.right == null)) {
Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
// No child case
if (temp == null) {
temp = root;
root = null;
} else // One child case
root = temp; // Copy the contents of the non-empty child
} else {
// node with two children: Get the inorder successor (smallest in the right subtree)
Node temp = minValueNode(root.right);
// Copy the inorder successor's data to this node
root.key = temp.key;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = max(height(root.left), height(root.right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root.left) < 0) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
// ... ตัดไป ...
โค้ดนี้จะลบโหนดที่มีคีย์ที่ระบุและใช้การหมุนเพื่อรักษาความสมดุลของ AVL Tree ซึ่งเป็นส่วนที่สำคัญหลังจากการลบโหนด
1. เส้นทางค้นหาสั้นและรวดเร็วเมื่อเทียบกับ BST ที่ไม่สมดุล
2. ประสิทธิภาพการค้นหาที่สม่ำเสมอ เนื่องจากความสมดุลของต้นไม้เสมอ
3. มีการรับประกันว่าจะมีความสมดุลเสมอหลังจากการแทรกและลบ
1. ความซับซ้อนของโค้ด มีการหมุนทรีที่ต้องดูแล
2. การขนานนามตัวแปรและการจัดการชั่งน้ำหนักอาจทำให้การเขียนโปรแกรมและการทำความเข้าใจยาก
3. อาจไม่เหมาะสำหรับทรีที่มีการเปลี่ยนแปลงบ่อยๆ เพราะทุกครั้งที่มีการแทรก หรือลบ ต้องทำการคำนวณเพื่อรักษาความสมดุล
AVL Tree เหมาะกับสถานการณ์ที่การค้นหาข้อมูลมีความจำเป็นมากกว่าการแทรกหรือลบ สำหรับระบบที่ต้องการประสิทธิภาพในการค้นหาข้อมูลที่สูง และมั่นใจได้ว่าข้อมูลจะถูกรักษารูปแบบที่สมดุล ทว่า ถ้าระบบของคุณมีการเปลี่ยนแปลงข้อมูลบ่อยครั้ง การเลือกโครงสร้างข้อมูลอื่น ๆ อาจเป็นทางเลือกที่ดีกว่า
ในที่สุด AVL Tree เป็นเครื่องมือที่มีประสิทธิภาพในการจัดการข้อมูลในโปรแกรมที่ต้องการความสมดุลและประสิทธิภาพในการค้นหาข้อมูล เหมาะอย่างยิ่งสำหรับนักพัฒนาที่ต้องการสร้างฟังก์ชันที่เร็วและรับมือกับข้อมูลปริมาณมหาศาล สำหรับผู้ที่สนใจเรียนรู้เทคนิคการเขียนโค้ด การจัดการข้อมูล และการใช้โครงสร้างข้อมูลที่เป็นประโยชน์อื่นๆ โรงเรียนของเรา EPT มีหลักสูตรที่จะช่วยให้คุณเข้าใจเหล่านี้อย่างลึกซึ้ง ไม่ว่าคุณจะเป็นมือใหม่หรือมืออาชีพ คุณจะได้เรียนรู้จากผู้เชี่ยวชาญที่พร้อมที่จะแบ่งปันความรู้และเทคนิคการเขียนโปรแกรมที่มีประสิทธิภาพให้กับคุณ!
การศึกษาที่ EPT ไม่เพียงแค่เพิ่มทักษะการเขียนโค
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM