การจัดการข้อมูลเป็นส่วนสำคัญที่ไม่ว่าในโครงการใด ๆ ก็ต้องให้ความสำคัญ สำหรับการเขียนโปรแกรมเพื่อการจัดการข้อมูลที่มีปริมาณมากและเปลี่ยนแปลงในทุกขณะ การใช้โครงสร้างข้อมูลที่เหมาะสมจะช่วยให้โปรแกรมทำงานได้อย่างมีประสิทธิภาพ หนึ่งในโครงสร้างข้อมูลที่นิยมใช้ในกรณีนี้คือ AVL Tree ซึ่งเป็น Binary Search Tree (BST) ที่มีการทำ Self-Balancing เพื่อให้มั่นใจว่าความสูงของต้นไม้จะคงอยู่ในลำดับ Logarithmic เพื่อระบุความหมาย
ในบทความนี้ เราจะรีวิวเทคนิคการเขียนโค้ด C สำหรับการจัดการข้อมูลผ่าน AVL Tree พร้อมทั้งสำรวจข้อดีข้อเสีย และแสดงตัวอย่างโค้ดในการ insert, insertAtFront, find และ delete การทำงานของแต่ละฟังก์ชันสำคัญจะถูกอธิบายเป็นสั้น ๆ และพร้อมกันนี้ หากคุณเป็นผู้ที่ต้องการหาที่เรียนรู้การเขียนโค้ดแบบมืออาชีพ EPT ของเราก็พร้อมให้คำปรึกษาและแนะนำเสมอ
การทำงานของ AVL Tree
AVL Tree นั้นมีการทำงานหลักๆ ดังนี้
- `Insert`: เพิ่มข้อมูลใหม่เข้าไปในต้นไม้ หากมีการเพิ่มที่ทำให้ไม่สมดุล ต้นไม้จะทำการปรับสมดุลเอง
- `InsertAtFront`: เป็นการเพิ่มข้อมูลใหม่เข้าไปในตำแหน่งหน้าสุดซึ่งไม่ค่อยจำเป็นใน AVL เนื่องจากการเติมที่ตำแหน่งใดก็ตาม จะต้องทำการตรวจสอบความสมดุลอยู่ดี
- `Find`: ค้นหาข้อมูลภายในต้นไม้ ใช้ข้อดีของ BST ในการค้นหา
- `Delete`: ลบข้อมูลออกจากต้นไม้ หลังจากลบ ต้องทำการปรับสมดุลต้นไม้
ข้อดีของ AVL Tree
1. ความสมดุลของต้นไม้: AVL Tree ดำเนินการให้ความสูงของต้นไม้มีค่าอย่างมากที่สุดเท่ากับ log(n) ทำให้การค้นหา, การแทรก, และการลบมีความคงที่เป็น O(log n) 2. สมรรถนะที่มั่นคง: เนื่องจากต้นไม้มีความสมดุล จึงทำให้สมรรถนะในแต่ละการดำเนินการคาดเดาได้ง่ายกว่า BST ทั่วไปข้อเสียของ AVL Tree
1. ความซับซ้อนทางเทคนิค: การรักษาสมดุลใน AVL Tree ต้องใช้การหมุน (Rotations) ซึ่งอาจทำให้การเข้าใจและการเขียนโค้ดเป็นอย่างยาก 2. การใช้หน่วยความจำเพิ่มเติม: ต้องจัดเก็บค่าความสมดุลสำหรับแต่ละโหนดซึ่งเพิ่มปริมาณการใช้หน่วยความจำตัวอย่างโค้ด
ต่อไปนี้เป็นตัวอย่างโค้ดภาษา C สำหรับฟังก์ชัน `insert` และ `delete` ใน AVL Tree:
#include
#include
typedef struct Node {
int key;
int height;
struct Node *left;
struct Node *right;
} Node;
// Helper function to get the height of the tree
int height(Node *N) {
if (N == NULL)
return 0;
return N->height;
}
// Helper function to get the maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
// A utility function to right rotate subtree rooted with y
Node *rightRotate(Node *y) {
// Your rotation code here
// ...
}
// A utility function to left rotate subtree rooted with x
Node *leftRotate(Node *x) {
// Your rotation code here
// ...
}
// Get Balance factor of node N
int getBalance(Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key in the subtree rooted
// with node and returns the new root of the subtree.
Node* insert(Node* node, int key) {
// 1. Perform the normal BST rotation
if (node == NULL){
// Create and return a new node
// ...
return (newNode);
}
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal 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 to check whether
// this node became unbalanced
int balance = getBalance(node);
// If this 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;
}
// Recursive function to delete a node with given key from subtree with given root.
// It returns root of the modified subtree.
Node* deleteNode(Node* root, int key) {
// Your delete code here
// ...
}
// A utility function to print preorder traversal of the tree.
void preOrder(Node *root) {
if (root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main() {
Node *root = NULL;
/* Constructing tree given in the above figure */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
printf("Pre order traversal of the constructed AVL tree is \n");
preOrder(root);
return 0;
}
ทั้งหมดนี้เป็นตัวอย่างของโค้ดที่ง่ายกว่า แต่ก็ยังคงมีความซับซ้อนในการสร้างและรักษาสมดุลของ 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