Konsep Tree

Sejauh ini kita banyak berurusan dengan struktur data linier seperti array, linked list, stack, dan queue. Setiap elemen di sana paling banyak memiliki satu suksesor langsung — bayangkan kereta dengan satu lokomotif dan satu gerbong berikutnya. Namun banyak masalah nyata memiliki struktur hierarkis: file system memiliki folder berisi folder berisi file, DOM HTML memiliki elemen <html> berisi <body> berisi <div> berisi <p>, dan struktur organisasi perusahaan memiliki CEO di puncak yang membawahi manajer-manajer. Tree adalah struktur data non-linier yang merepresentasikan hubungan hierarkis tersebut. Pada Chapter ini kita akan memahami definisi formal tree, perbedaannya dengan struktur linier, dan mengapa struktur hierarkis menyiapkan fondasi penting untuk BST, AVL, trie, segment tree, dan banyak struktur data lanjutan lainnya.

Struktur Linier vs Hierarkis #

Pada struktur linier, setiap elemen paling banyak memiliki satu suksesor. Pada tree, sebuah elemen boleh memiliki banyak suksesor sehingga terbentuk percabangan.

Definisi Formal Tree #

Sebuah tree adalah himpunan node yang terhubung oleh edge berarah dengan sifat-sifat berikut:

1. Terdapat tepat satu node khusus bernama root yang tidak memiliki parent.
2. Setiap node selain root memiliki tepat satu parent.
3. Terdapat unique path (jalur unik) dari root ke setiap node.

Sifat kedua membedakan tree dari graph umum: pada graph, sebuah node boleh punya banyak parent atau membentuk cycle. Pada tree, tidak ada cycle.

Contoh Nyata Tree #

Beberapa struktur sehari-hari yang berbentuk tree:

• File system: / → /home → /home/andi → /home/andi/proyek.
• DOM HTML: <html> → <body> → <div> → <p>.
• Struktur organisasi: CEO → Manager → Supervisor → Staff.
• Taxonomy biologi: Animalia → Chordata → Mammalia → Primata.
• Pohon genealogi: kakek → ayah → anak.

Visualisasi Tree dengan Mermaid #

Diagram berikut menampilkan tree dengan 7 node. Node A adalah root, D-G adalah leaf.

Pada diagram di atas, edge berarah dari parent ke child. Setiap node kecuali A memiliki tepat satu parent. Path dari root ke leaf apapun bersifat unik.

Representasi Tree dalam C++ #

Setiap node pada tree umumnya direpresentasikan sebagai struct atau class yang menyimpan data dan pointer ke children. Untuk tree umum dengan jumlah child variabel, kita gunakan std::vector untuk menampung children:

#include <iostream>
#include <vector>
#include <memory>
#include <string>

template <typename T>
struct TreeNode {
    T data;
    std::vector<std::shared_ptr<TreeNode>> children;

    explicit TreeNode(const T& v) : data(v) {}
};

template <typename T>
void print_tree(const std::shared_ptr<TreeNode<T>>& node, int depth = 0) {
    if (!node) return;
    std::string indent(depth * 2, ' ');
    std::cout << indent << "- " << node->data << '\n';
    for (const auto& child : node->children) {
        print_tree(child, depth + 1);
    }
}

int main() {
    auto root = std::make_shared<TreeNode<std::string>>("proyek");
    auto src = std::make_shared<TreeNode<std::string>>("src");
    auto docs = std::make_shared<TreeNode<std::string>>("docs");
    auto main_cpp = std::make_shared<TreeNode<std::string>>("main.cpp");
    auto util_cpp = std::make_shared<TreeNode<std::string>>("util.cpp");
    auto readme = std::make_shared<TreeNode<std::string>>("README.md");

    root->children.push_back(src);
    root->children.push_back(docs);
    src->children.push_back(main_cpp);
    src->children.push_back(util_cpp);
    docs->children.push_back(readme);

    std::cout << "Struktur folder:\n";
    print_tree(root);
    return 0;
}

Output yang Dihasilkan:

Struktur folder:
- proyek
  - src
    - main.cpp
    - util.cpp
  - docs
    - README.md

1. template <typename T> struct TreeNode: struct generik yang menyimpan data bertipe T dan std::vector anak-anak. std::shared_ptr digunakan agar ownership node dikelola otomatis oleh reference counting.
2. std::vector<std::shared_ptr<TreeNode>> children: vector menampung child dalam jumlah variabel. Tree umum (bukan binary) memungkinkan node memiliki 0, 1, 2, atau lebih children.
3. Fungsi print_tree: rekursif dengan parameter depth untuk indentasi. Setiap level hierarki ditambah 2 spasi indentasi.
4. Konstruksi tree: proyek adalah root. src dan docs adalah children. main.cpp dan util.cpp adalah children dari src. Struktur ini menggambarkan tree folder proyek perangkat lunak.

Mengapa Tree Penting #

Tree memecahkan masalah-masalah yang sulit diselesaikan struktur linier:

• Pencarian terurut: BST menjamin pencarian O(log n) dengan urutan in-order terurut.
• Auto-complete: Trie menyimpan kamus dengan prefix sharing, efisien untuk autocomplete.
• Range query: Segment tree menjawab “jumlah elemen pada range [l, r]” dalam O(log n).
• Heap priority queue: Binary heap menyimpan elemen dengan prioritas tertinggi di root.
• Parsing ekspresi: Expression tree (a + b) * c diurai menjadi pohon dengan * di root.

Ringkasan #

• Tree adalah struktur data non-linier dan hierarkis: setiap node boleh memiliki banyak children, namun tepat satu parent (kecuali root).
• Sifat unik tree: ada tepat satu root, setiap node non-root punya tepat satu parent, dan path dari root ke node manapun bersifat unik.
• Tree merepresentasikan struktur nyata seperti file system, DOM, dan organisasi.
• Implementasi node tree umum memakai struct dengan std::vector children untuk tree dengan derajat variabel.
• Bab-bab berikutnya di Section 13 akan memperkenalkan varian tree spesifik: binary tree, BST, AVL, trie, segment tree, dan fenwick tree.