การจัดการข้อมูล (Data management) นั้นถือเป็นหลักการที่สำคัญมากในโลกของการเขียนโปรแกรม โดยเฉพาะเมื่อมาถึงประเด็นของการจัดการข้อมูลที่มีขนาดใหญ่และต้องการการค้นหา, เพิ่ม, และลบข้อมูลอย่างรวดเร็วและมีประสิทธิภาพการทำงานที่สม่ำเสมอ เทคนิคหนึ่งที่ได้รับความนิยมก็คือการใช้ Self-Balancing Binary Search Tree หรือ Self-Balancing BST ในการจัดการข้อมูลเหล่านั้น
เราจะมาดูกันว่า Self-Balancing BST ใน C++ นั้นทำงานอย่างไร ข้อดีข้อเสียคืออะไร พร้อมทั้งยกตัวอย่างโค้ดสำหรับการ insert, insertAtFront, find, และ delete ในการใช้งานกับโครงสร้างข้อมูลประเภทนี้
Self-Balancing BST เป็นโครงสร้างข้อมูลที่ปรับสมดุลตัวเองได้อัตโนมัติ เพื่อรักษาประสิทธิภาพการทำงานของการค้นหา, การแทรก (insertion), และการลบ (deletion) ให้อยู่ในระดับ Logarithmic time (`O(log n)`). ตัวอย่างที่โด่งดังของ Self-Balancing BST ได้แก่ AVL Trees และ Red-Black Trees นั้นมีข้อดีหลายอย่าง เช่น
- การปรับสมดุล: โดยปกติ BST ถ้าไม่มีการปรับสมดุลอาจทำให้เกิดการเบ้ข้าง (unbalanced) จนกระทั่งมีลักษณะคล้าย linked list ในกรณีเลวร้ายที่สุด ซึ่งจะทำให้ประสิทธิภาพลดลงมาก แต่ Self-Balancing BST จะปรับตัวเองให้มีความสมดุลอยู่เสมอ - ประสิทธิภาพ: ด้วยการทำงานในระดับ O(log n) ทำให้การทำงานสม่ำเสมอและรวดเร็ว แม้อาจจะมี overhead จากการปรับสมดุลเล็กน้อย
ต่อไปนี้คือตัวอย่างโค้ดการแทรก, ค้นหา, และการลบข้อมูลใน Self-Balancing BST โดยจำลองวิธีการทำงานของ AVL Tree:
#include
using namespace std;
// โครงสร้างของโหนดใน AVL tree
struct Node {
int key;
Node *left;
Node *right;
int height;
};
// Function to get height of the tree
int height(Node *N) {
if (N == NULL) return 0;
return N->height;
}
// Function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Helper function to create a new node
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
// Right rotate utility
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;
}
// Left rotate utility
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 == 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 insert */
if (node == NULL) 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 return node; // Equal keys are not allowed in BST
/* 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;
}
// Function to delete a node with given key
// It returns root of the modified subtree
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 = root->left ? root->left : root->right;
// No child case
if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child
delete 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 == NULL) 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;
}
Node * minValueNode(Node* node) {
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) current = current->left;
return current;
}
// A utility function to print preorder traversal of the tree. The function also prints height of every node
void preOrder(Node *root) {
if(root != NULL) {
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Function to search a given key in a given BST
Node* search(Node* root, int key) {
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key) return root;
// Key is greater than root's key
if (root->key < key) return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
// main function to demonstrate tree operations
int main() {
Node *root = NULL;
// Constructing tree given in the above figure
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/
cout << "Preorder traversal of the constructed AVL tree is \n";
preOrder(root);
root = deleteNode(root, 10);
cout << "\nPreorder traversal after deletion of 10 \n";
preOrder(root);
Node* found = search(root, 5);
if (found != NULL) {
cout << "\nFound node with key " << found->key << endl;
} else {
cout << "\nThe key 5 was not found in the tree.\n";
}
return 0;
}
ข้อดี:
- การปรับสมดุลอัตโนมัติ: Self-Balancing BST จะปรับสมดุลของตัวเองหลังจากการใส่หรือลบโหนดเพื่อรักษาประสิทธิภาพในการค้นหาที่สม่ำเสมอ - ประสิทธิภาพการค้นหาสูง: เนื่องจากการปรับสมดุลนี้ทำให้การค้นหารักษาเวลาเฉลี่ยที่ O(log n) ไม่ว่าจะมีการเปลี่ยนแปลงโครงสร้างข้อมูลอย่างไรก็ตาม - โครงสร้างข้อมูลเป็นลักษณะต้นไม้: มีลักษณะที่ชัดเจนและสามารถจำลองเป็นโครงสร้างในรูปแบบต่างๆได้ตามความต้องการข้อเสีย:
- ความซับซ้อนในการเข้าใจและการเขียนโค้ด: การเขียนและทำความเข้าใจ Self-Balancing BST นั้นซับซ้อนกว่าโครงสร้างข้อมูลแบบพื้นฐานอื่นๆ - Overhead จากการปรับสมดุล: บางครั้งการแทรกหรือลบข้อมูลอาจส่งผลให้ต้องมีการรวบรวมข้อมูลใหม่ทั้งหมด ซึ่งจะใช้เวลาและทรัพยากรเพิ่มขึ้น
การใช้ Self-Balancing BST ในภาษา C++ เป็นเทคนิคสำคัญในการจัดการข้อมูลแบบไดนามิคที่ช่วยให้การทำงานมีประสิทธิภาพและรักษาการทำงานที่สม่ำเสมอ แม้จะมีความซับซ้อนบ้าง แต่เมื่อคุณได้เรียนรู้และทำความเข้าใจศัพท์และเทคนิคต่างๆก็จะนำไปใช้ได้มากทีเดียว
หากคุณสนใจอยากแตกหักปัญหาใหม่ๆในโลกของการเขียนโค้ดและชื่นชอบในการเรียนรู้เทคนิคและแนวคิดขั้นสูง เราที่ Expert-Programming-Tutor (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