Struktur Data Advanced dalam C++: Master Tree, Graph, dan Hash Table untuk Pemecahan Masalah Kompleks
Kalau array dan linked list itu seperti senjata dasar dalam programming, maka tree, graph, dan hash table adalah senjata khusus pasukan elit. Bayangkan kamu mau bikin Google Maps butuh cari rute tercepat, atau bikin sistem rekomendasi Netflix butuh suggest film – mustahil pakai array biasa! Di sinilah struktur data advanced dalam C++ menunjukkan taringnya.
Artikel ini bakal ngajakin kamu menjelajahi dunia struktur data C++ yang lebih sophisticated. Kita akan kupas dari konsep fundamental sampai implementasi praktis, lengkap dengan code examples yang siap compile. Siap untuk upgrade skill programming-mu ke level advanced?
Kenapa Perlu Struktur Data Advanced?
Sebelum masuk ke teknis, mari pahami dulu mengapa struktur data ini penting:
- Efisiensi Operasi: Binary Search Tree bisa search dalam O(log n) vs array O(n)
- Representasi Data Real-World: Graph perfect untuk social networks, maps
- Memory Management: Hash table memberikan O(1) access time dengan tradeoff memory
- Problem Solving: Banyak algoritma complex membutuhkan struktur data specific
Tree Structures: Hierarchical Data Mastery
Tree adalah struktur data hierarchical yang mirip pohon keluarga atau struktur organisasi.
Binary Tree: Fondasi Segala Tree
#include
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BinaryTree {
private:
TreeNode* root;
TreeNode* insertRec(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
}
if (value < node->data) {
node->left = insertRec(node->left, value);
} else if (value > node->data) {
node->right = insertRec(node->right, value);
}
return node;
}
public:
BinaryTree() : root(nullptr) {}
void insert(int value) {
root = insertRec(root, value);
}
// Traversal methods
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
cout << node->data << " "; inorder(node->right);
}
void printInorder() {
inorder(root);
cout << endl;
}
};
// Usage example
int main() {
BinaryTree tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
cout << "Inorder traversal: ";
tree.printInorder(); // Output: 20 30 40 50 70
return 0;
}
Binary Search Tree (BST): Ordered Data Structure
BST adalah binary tree dengan sifat khusus: left child < parent < right child.
class BST {
private:
TreeNode* root;
TreeNode* searchRec(TreeNode* node, int key) {
if (node == nullptr || node->data == key) {
return node;
}
if (key < node->data) {
return searchRec(node->left, key);
}
return searchRec(node->right, key);
}
public:
TreeNode* search(int key) {
return searchRec(root, key);
}
// Complexity: O(h) where h is height of tree
// Average case: O(log n), Worst case: O(n)
};
AVL Tree: Self-Balancing BST
BST bisa jadi unbalanced, AVL tree menjaga balance dengan rotations.
struct AVLNode {
int data;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};
class AVLTree {
private:
AVLNode* root;
int getHeight(AVLNode* node) {
return node ? node->height : 0;
}
int getBalance(AVLNode* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
// Left rotation and other methods...
};
Graph Structures: Modeling Complex Relationships
Graph adalah struktur data yang merepresentasikan hubungan antar objek.
Adjacency List Representation
#include
#include
#include
using namespace std;
class Graph {
private:
int V; // Number of vertices
vector<list> adj; // Adjacency list
public:
Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // For undirected graph
}
void printGraph() {
for (int i = 0; i < V; i++) {
cout << "Vertex " << i << ":";
for (auto neighbor : adj[i]) {
cout << " -> " << neighbor;
}
cout << endl;
}
}
// BFS traversal
void BFS(int start) {
vector visited(V, false);
list queue;
visited[start] = true;
queue.push_back(start);
while (!queue.empty()) {
int current = queue.front();
cout << current << " ";
queue.pop_front();
for (auto neighbor : adj[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push_back(neighbor);
}
}
}
cout << endl;
}
};
// Usage
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
cout << "BFS from vertex 0: ";
g.BFS(0);
return 0;
}
Adjacency Matrix Representation
class GraphMatrix {
private:
int V;
vector<vector> adjMatrix;
public:
GraphMatrix(int vertices) : V(vertices), adjMatrix(vertices, vector(vertices, 0)) {}
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // Undirected graph
}
bool isConnected(int u, int v) {
return adjMatrix[u][v] == 1;
}
// DFS using adjacency matrix
void DFS(int start) {
vector visited(V, false);
DFSUtil(start, visited);
cout << endl;
}
private:
void DFSUtil(int v, vector& visited) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < V; i++) {
if (adjMatrix[v][i] == 1 && !visited[i]) {
DFSUtil(i, visited);
}
}
}
};
Hash Table: Lightning-Fast Data Access
Hash table memberikan average O(1) time complexity untuk insert, delete, dan search.
Custom Hash Table Implementation
#include
#include
#include
template
class HashMap {
private:
struct KeyValue {
K key;
V value;
KeyValue(const K& k, const V& v) : key(k), value(v) {}
};
vector<list> buckets;
int capacity;
int size;
int getBucketIndex(const K& key) {
hash hashFunc;
return hashFunc(key) % capacity;
}
public:
HashMap(int cap = 10) : capacity(cap), size(0) {
buckets.resize(capacity);
}
void insert(const K& key, const V& value) {
int index = getBucketIndex(key);
// Check if key already exists
for (auto& kv : buckets[index]) {
if (kv.key == key) {
kv.value = value; // Update existing
return;
}
}
// Insert new key-value pair
buckets[index].emplace_back(key, value);
size++;
// Resize if load factor > 0.7
if (static_cast(size) / capacity > 0.7) {
rehash();
}
}
V* get(const K& key) {
int index = getBucketIndex(key);
for (auto& kv : buckets[index]) {
if (kv.key == key) {
return &kv.value;
}
}
return nullptr; // Key not found
}
bool remove(const K& key) {
int index = getBucketIndex(key);
auto& bucket = buckets[index];
for (auto it = bucket.begin(); it != bucket.end(); ++it) {
if (it->key == key) {
bucket.erase(it);
size--;
return true;
}
}
return false;
}
private:
void rehash() {
int newCapacity = capacity * 2;
vector<list> newBuckets(newCapacity);
for (auto& bucket : buckets) {
for (auto& kv : bucket) {
hash hashFunc;
int newIndex = hashFunc(kv.key) % newCapacity;
newBuckets[newIndex].emplace_back(kv.key, kv.value);
}
}
buckets = move(newBuckets);
capacity = newCapacity;
}
};
// Usage example
int main() {
HashMap<string, int> studentGrades;
studentGrades.insert("Alice", 85);
studentGrades.insert("Bob", 92);
studentGrades.insert("Charlie", 78);
int* grade = studentGrades.get("Alice");
if (grade) {
cout << "Alice's grade: " << *grade << endl;
}
studentGrades.remove("Bob");
return 0;
}
STL unordered_map: Production-Ready Hash Table
#include
#include
#include
void STLHashMapExample() {
// Declaration
unordered_map<string, int> population;
// Insertion
population["Jakarta"] = 10700000;
population["Surabaya"] = 2870000;
population["Bandung"] = 2500000;
// Access
cout << "Jakarta population: " << population["Jakarta"] << endl;
// Check existence
if (population.find("Medan") != population.end()) {
cout << "Medan found" << endl;
} else {
cout << "Medan not found" << endl;
}
// Iteration
for (const auto& city : population) {
cout << city.first << ": " << city.second << endl;
}
// Performance characteristics
cout << "Load factor: " << population.load_factor() << endl;
cout << "Bucket count: " << population.bucket_count() << endl;
}
Advanced Applications dan Use Cases
1. Social Network dengan Graph
class SocialNetwork {
private:
unordered_map<string, list> friends;
public:
void addFriendship(const string& user1, const string& user2) {
friends[user1].push_back(user2);
friends[user2].push_back(user1);
}
list getMutualFriends(const string& user1, const string& user2) {
list mutual;
unordered_set friends1(friends[user1].begin(), friends[user1].end());
for (const auto& friend2 : friends[user2]) {
if (friends1.find(friend2) != friends1.end()) {
mutual.push_back(friend2);
}
}
return mutual;
}
int getDegreeOfSeparation(const string& start, const string& target) {
unordered_map<string, int> distances;
queue q;
distances[start] = 0;
q.push(start);
while (!q.empty()) {
string current = q.front();
q.pop();
if (current == target) {
return distances[current];
}
for (const auto& friend : friends[current]) {
if (distances.find(friend) == distances.end()) {
distances[friend] = distances[current] + 1;
q.push(friend);
}
}
}
return -1; // Not connected
}
};
2. File System dengan Tree
struct FileNode {
string name;
bool isDirectory;
vector<FileNode*> children;
FileNode* parent;
FileNode(const string& n, bool isDir, FileNode* p = nullptr)
: name(n), isDirectory(isDir), parent(p) {}
};
class FileSystem {
private:
FileNode* root;
FileNode* current;
public:
FileSystem() {
root = new FileNode("/", true);
current = root;
}
void mkdir(const string& dirName) {
FileNode* newDir = new FileNode(dirName, true, current);
current->children.push_back(newDir);
}
void ls() {
for (const auto& child : current->children) {
cout << (child->isDirectory ? "[D] " : "[F] ") << child->name << endl; } } void cd(const string& dirName) { if (dirName == "..") { if (current->parent) {
current = current->parent;
}
return;
}
for (const auto& child : current->children) {
if (child->isDirectory && child->name == dirName) {
current = child;
return;
}
}
cout << "Directory not found" << endl;
}
};
Performance Comparison dan Analysis
| Struktur Data | Search | Insert | Delete | Use Case |
|---|---|---|---|---|
| Binary Search Tree | O(log n) | O(log n) | O(log n) | Ordered data, dynamic sets |
| AVL Tree | O(log n) | O(log n) | O(log n) | Balanced trees, frequent searches |
| Hash Table | O(1) | O(1) | O(1) | Fast lookups, dictionaries |
| Graph (Adj List) | O(V+E) | O(1) | O(E) | Networks, relationships |
Memory Management dan Best Practices
Smart Pointers untuk Automatic Memory Management
#include
class TreeWithSmartPointers {
private:
struct TreeNode {
int data;
shared_ptr left;
shared_ptr right;
TreeNode(int val) : data(val) {}
};
shared_ptr root;
public:
void insert(int value) {
root = insertRec(root, value);
}
private:
shared_ptr insertRec(shared_ptr node, int value) {
if (!node) {
return make_shared(value);
}
if (value < node->data) {
node->left = insertRec(node->left, value);
} else {
node->right = insertRec(node->right, value);
}
return node;
}
};
Kesimpulan: Memilih Struktur Data yang Tepat
Menguasai struktur data advanced dalam C++ seperti tree, graph, dan hash table membuka kemampuan untuk menyelesaikan masalah programming yang lebih complex dan real-world.
Panduan memilih struktur data:
- Hash Table: When you need fastest possible lookups
- BST/AVL Tree: When you need ordered data with efficient operations
- Graph: When modeling relationships and connections
- Heap: When you need priority-based access
Practice dengan implementasi dari nol, pahami trade-offs, dan terapkan pada project nyata. Dengan mastery struktur data advanced, kamu akan menjadi programmer yang jauh lebih effective dan valuable!