Terminologi Tree

Setelah memahami konsep dasar tree pada Chapter sebelumnya, sekarang kita perlu membangun kosakata teknis yang tepat. Tanpa terminologi yang jelas, kita tidak bisa membahas BST, AVL rotation, atau segment tree — semuanya bergantung pada istilah seperti height, depth, ancestor, dan subtree. Misalnya, ketika nanti kita mengatakan “rotasi LL dilakukan ketika subtree kiri dari anak kiri lebih tinggi”, kita harus tahu persis apa arti subtree, anak kiri, dan tinggi. Pada Chapter ini kita akan memetakan setiap istilah penting tree ke definisi formal, menghitung depth dan height secara konkret, dan menerapkannya dalam C++ dengan contoh tree yang dapat dipertahankan.

Daftar Istilah Utama #

Berikut istilah-istilah yang wajib dikuasai sebelum melangkah ke topik tree lanjutan:

Visualisasi Tree Contoh #

Diagram berikut memakai tree dengan 8 node untuk menerangkan semua istilah:

Mari kita terapkan istilah-istilah pada tree di atas:

• A adalah root, level 0, depth 0.
• B dan C adalah sibling (parent sama: A).
• D, H, F, G adalah leaf.
• B, C, E adalah internal node.
• Ancestor dari H: A, B, E.
• Descendant dari C: F, G.
• Subtree dari B: tree dengan root B berisi B, D, E, H.
• Degree A = 2, degree E = 1, degree D = 0.
• Depth H = 3 (edge: A→B, B→E, E→H).
• Height A = 3 (path terpanjang ke leaf: A→B→E→H).
• Height H = 0 (leaf).

Aturan Relasi Depth dan Height #

Pada tree manapun, hubungan berikut selalu berlaku:

1. Height dari leaf selalu 0 (tidak ada edge ke bawah).
2. Height dari node = 1 + max(height children) bila node punya child.
3. Depth dari root selalu 0.
4. Depth dari node = depth parent + 1.
5. Height tree = height root = depth leaf terdalam.

Implementasi: Menghitung Depth dan Height #

Berikut implementasi C++ yang menghitung depth (via parent pointer) dan height (via rekursi):

#include <iostream>
#include <memory>
#include <algorithm>

template <typename T>
struct Node {
    T data;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;

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

template <typename T>
int depth(const Node<T>* node) {
    int d = 0;
    while (node->parent != nullptr) {
        node = node->parent;
        ++d;
    }
    return d;
}

template <typename T>
int height(const Node<T>* node) {
    if (node == nullptr) return -1;          // null dianggap height -1
    int hl = height(node->left);
    int hr = height(node->right);
    return 1 + std::max(hl, hr);
}

template <typename T>
int level(const Node<T>* node) {
    return depth(node);                       // level = depth dalam konvensi root=0
}

int main() {
    // Bangun tree contoh:
    //         A
    //        / \
    //       B   C
    //      / \   \
    //     D   E   F
    //         |
    //         H
    auto a = new Node<char>('A');
    auto b = new Node<char>('B');
    auto c = new Node<char>('C');
    auto d = new Node<char>('D');
    auto e = new Node<char>('E');
    auto f = new Node<char>('F');
    auto h = new Node<char>('H');

    a->left = b;  b->parent = a;
    a->right = c; c->parent = a;
    b->left = d;  d->parent = b;
    b->right = e; e->parent = b;
    c->right = f; f->parent = c;
    e->left = h;  h->parent = e;

    std::cout << "Node  Depth Height Level\n";
    for (Node<char>* n : {a, b, c, d, e, f, h}) {
        std::cout << n->data << "     "
                  << depth(n) << "     "
                  << height(n) << "     "
                  << level(n) << '\n';
    }
    std::cout << "Height tree (root A) = " << height(a) << '\n';

    // Cleanup
    delete a; delete b; delete c; delete d; delete e; delete f; delete h;
    return 0;
}

Output yang Dihasilkan:

Node  Depth Height Level
A     0     3     0
B     1     2     1
C     1     1     1
D     2     0     2
E     2     1     2
F     2     0     2
H     3     0     3
Height tree (root A) = 3

1. Struct Node: setiap node menyimpan data, dua pointer child (left, right) untuk binary tree, dan parent untuk traversal naik. Pointer parent tidak wajib, namun berguna untuk komputasi depth dan operasi seperti successor BST.
2. Fungsi depth: iteratif naik dari node ke root melalui parent. Setiap langkah menambah 1. Kompleksitas O(depth) — bisa O(n) pada skewed tree.
3. Fungsi height: rekursif. height(null) = -1 dipilih agar height(leaf) = 1 + max(-1, -1) = 0 sesuai konvensi CLRS.
4. Fungsi level: dalam konvensi root = 0, level = depth. Beberapa buku memakai root = 1, di situ level = depth + 1.
5. Hasil untuk H: depth = 3 (path A→B→E→H), height = 0 (leaf). Sesuai ekspektasi.

Ancestor dan Descendant #

Ancestor dari sebuah node adalah semua node yang dilewati path dari root ke node tersebut. Descendant adalah kebalikannya: semua node yang bisa dicapai dengan menuruni dari node tersebut.

Degree dan Subtree #

Degree sebuah node adalah jumlah child-nya. Pada binary tree, degree maksimal 2. Pada tree umum (n-ary), degree tidak terbatas.

Subtree dari sebuah node v adalah tree yang terbentuk dari v beserta seluruh descendantnya. Subtree root B pada contoh di atas berisi node B, D, E, H.

Ringkasan #

• Root = node puncak tanpa parent; leaf = node tanpa child; internal node = sisanya.
• Depth = jarak edge dari root ke node; height = jarak edge terpanjang dari node ke leaf; level = depth dalam konvensi root = 0.
• Parent/child/sibling mendeskripsikan hubungan langsung; ancestor/descendant hubungan tak langsung sepanjang path.
• Subtree = tree yang terbentuk dari sebuah node beserta seluruh descendantnya.
• Degree = jumlah child; pada binary tree degree maksimal 2.
• Implementasi depth memakai parent pointer iteratif; height memakai rekursi 1 + max(h_left, h_right).