การจัดการข้อมูลเป็นหัวใจสำคัญของการเขียนโปรแกรม มากมายกับโครงสร้างข้อมูลต่างๆที่นักพัฒนาเลือกใช้เพื่อตอบโจทย์ปัญหาที่พบ เทรีย์ (Tree) เป็นโครงสร้างข้อมูลแบบหนึ่งที่มีการใช้งานอย่างกว้างขวาง และหนึ่งในประเภทเทรีย์ที่น่าสนใจ คือ AVL Tree ซึ่งเป็นเทรีย์แบบพิเศษที่ตั้งชื่อตามผู้คิดค้น Adelson-Velskii และ Landis ได้รับการออกแบบมาเพื่อให้การค้นหาข้อมูลเป็นไปอย่างรวดเร็ว
AVL Tree มีคุณสมบัติพิเศษคือการเป็น Balanced Binary Search Tree ที่มีความสูงต่ำสุดเมื่อเทียบกับจำนวนโหนด เพราะมีกลไกในการปรับสมดุลตัวเอง เมื่อเกิดการเพิ่มหรือลบโหนดซึ่งทำให้การค้นหา, การเพิ่ม, และการลบมีประสิทธิภาพสูง
การ Insert โหนดใน AVL Tree
การเพิ่ม (insert) โหนดใน AVL Tree ต้องทำการควบคุมความสมดุลของเทรีย์ด้วย operation ที่เรียกว่า “rotation” และยังต้องยึดตามหลักของ Binary Search Tree คือ ข้อมูลที่น้อยกว่ามาอยู่ทางซ้าย และที่มากกว่ามาอยู่ทางขวา
ต่อไปนี้เป็นตัวอย่างฟังก์ชันการ insert ใน AVL Tree:
Node* insert(Node* node, int key) {
// 1. Perform the normal BST insertion
if (node == nullptr)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
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 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;
}
อธิบายการทำงาน:
- ขั้นตอนที่ 1: ทำการเพิ่มโหนดตามหลักการของ Binary Search Tree (BST).
- ขั้นตอนที่ 2: อัพเดตความสูงของโหนดที่เพิ่ม.
- ขั้นตอนที่ 3: ตรวจสอบความสมดุลของ AVL Tree และทำการ "rotation" ถ้าจำเป็นเพื่อคงความสมดุล.
การ InsertAtFront ใน AVL Tree
การ `insertAtFront` เป็นการเพิ่มโหนดที่ root หรือที่หน้าสุดของเทรีย์ อย่างไรก็ตามใน AVL Tree หรือ BST ตามทั่วไปไม่มีโคนเซ็ปต์ของ "ฟร้อนท์" เหมือนใน Linked List เนื่องจาก AVL มีโครงสร้างที่เป็น hierarchical ซึ่งการแทรกโหนดต้องตามกฎของ BST และต้องรักษา balance ดังนั้นจึงไม่มี operation ที่เรียกว่า `insertAtFront` อย่างเฉพาะเจาะจงใน AVL Tree
การ Find โหนดใน AVL Tree
การค้นหา (find) โหนดเป็น operation ที่สำคัญ และมีประสิทธิภาพใน AVL Tree เนื่องจากคุณสมบัติของความสมดุลทำให้เวลาค้นหาลดลงใกล้เคียงกับ O(log n) โดยทั่วไปโค้ดสำหรับการค้นหาจะคล้ายกับ BST:
Node* find(Node* root, int key) {
if (root == nullptr || root->key == key)
return root;
if (root->key < key)
return find(root->right, key);
return find(root->left, key);
}
การ Delete เพิ่มโหนดใน AVL Tree
การลบ (delete) โหนดใน AVL Tree ก็ต้องพิจารณาถึงการรักษาการสมดุลหลังจากที่ลบโหนดออกไปแล้ว ซึ่งจะมีการใช้ rotation ในการบำรุงรักษาความสมดุลหลังจากการลบ:
// C++ program to delete a node from AVL Tree
// A utility function to get height of the tree
int height(Node *N) {
if (N == nullptr)
return 0;
return N->height;
}
// A utility function to get 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 */
// See the diagram given above.
Node *rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
/* A utility function to left rotate subtree rooted with x */
// See the diagram given above.
Node *leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N) {
if (N == nullptr)
return 0;
return height(N->left) - height(N->right);
}
// 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) {
// STEP 1: PERFORM STANDARD BST DELETE
if (root == nullptr)
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 == nullptr) || (root->right == nullptr) ) {
Node *temp = root->left ? root->left : root->right;
// No child case
if (temp == nullptr) {
temp = root;
root = nullptr;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
}
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 == nullptr)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// 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;
}
การลบโหนดจะผ่านการลบตาม Binary Search Tree แต่ต้องทำการปรับสมดุลทีหลัง
ข้อดีและข้อเสียของการใช้งาน AVL Tree
ข้อดีของการใช้ AVL Tree คือ ความสามารถในการค้นหาที่รวดเร็วเนื่องจากความสมดุลของเทรีย์ ซึ่งจะเป็น O(log n) และมีความปลอดภัยในการที่โครงสร้างจะไม่เอียงไปทางใดทางหนึ่งเมื่อมีการเพิ่มหรือลบข้อมูล ส่วนข้อเสียคือ ความซับซ้อนในการแทรกและลบข้อมูลที่ต้องมีการปรับสมดุลที่แกว่งไปมามากกว่าในโครงสร้างอื่นๆ ทำให้ต้องใช้เวลาในปฏิบัติการดังกล่าวมากขึ้น
สรุป
AVL Tree เป็นโครงสร้างข้อมูลที่มีประโยชน์มากในการเก็บข้อมูลที่ต้องการการค้นหาอย่างรวดเร็ว เป็นการตอบสนองต่อภาวะที่ไม่สมดุลของโครงสร้างข้อมูลแบบสมมติฐานเบสิกเช่น Binary Searchil Tree หากคุณต้องการพัฒนาความสามารถในการเขียนโค้ดและการจัดการข้อมูลที่ซับซ้อน เราขอเชิญชวนคุณมาเรียนรู้และพัฒนาทักษะการเขียนโปรแกรมที่หลักสูตรของเราที่ EPT โดยผู้เชี่ยวชาญที่พร้อมจะนำทางคุณสู่การเป็นนักพัฒนาที่มีฝีมือคับแก้ว!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM