Modul 12 : Tree - fzl-22/modul-alstrukdat-sainsdata GitHub Wiki

1. Definisi Tree

Seperti yang pernah dijelaskan pada pertemuan awal bahwa data struktur terbagi menjadi 2 yaitu linear dan non-linear data structure. Selain disebut non-linear data structure, data structure tersebut juga sering disebut dengan hierarki data structure. Hal tersebut dikarenakan dalam penyusunannya, data di dalam struktur data ini seakan memiliki tingkatan/hirarki yang saling berelasi satu sama lain. Selain memiliki tingkatan penyusunan struktur data tree jika divisualisasikan mirip dengan pohon yang dibalik. Agar lebih jelas perhatikan visualisasi berikut:

Dari gambar di atas didapatkan beberapa terminologi dari data structure tree yaitu antara lain:

Root : Node teratas dalam struktur tree yang tidak memiliki parent atau induk node.
Child : Node yang merupakan turunan atau anak dari parent node.
Parent: Node yang memiliki satu atau lebih anak atau turunan.
Edge : Cabang atau penghubung antar node.
Sibling: Node yang berada pada level yang sama dalam struktur tree, dan memiliki parent node yang sama.
Leaf: Node yang tidak memiliki anak atau turunan.
Ancestor: Node yang berada pada jalur dari root node ke suatu node, termasuk parent node dari node tersebut.
Descendant: Node yang berada pada jalur dari suatu node ke leaf node di bawahnya, termasuk child node dari node tersebut.
Subtree: Tree yang terbentuk dari suatu node dan semua descendant node-nya.
Depth: Jarak dari root node ke suatu node dalam tree, dihitung dengan jumlah edge yang dilalui. (Root - Node)
Height: Jarak terpanjang dari suatu node ke leaf node di bawahnya, dihitung dengan jumlah edge yang dilalui. (Leaf - Node)
Level: Jumlah edge yang dilalui dari root node ke suatu node, dihitung mulai dari 0 (untuk root node).
Subtree: Tree yang terbentuk dari suatu node dan semua descendant node-nya.

1.2 Kenapa Tree?

Dalam linear data structure data atau element disusun secara sequential atau baris. Dalam bentuk ini time complexity untuk melakukan suatu operasi akan berkembang sejalan dengan berkembangnya jumlah atau ukuran data sedangkan pada non-linear data structure terutama tree pengaksesan element lebih efisien dan lebih cepat. Untuk lebih jelasnya perhatikan contoh berikut:

Bayangkan kita ingin mengakses nilai 70, pada linear data structure terutama linked list kita perlu melakukan pengaksesan satu persatu dari awal node hingga node bernilai 70 pada node akhir. Namun, perhatikan jika linked list tersebut diubah menjadi tree.

Dengan menggunakan tree maka kita dapat melewati beberapa pengaksesan node yang tidak diperlukan untuk mencari nilai 70 dengan melewati ruas subtree bagian kiri dan langsung melakukan pengaksesan pada subtree bagian kanan sehingga jumlah pengaksesan node dapat dikurangi.

2. Membuat Tree

Pada pertemuan kali ini kita akan mengimplementasikan tree menggunakan pendekatan class. Namun, jika kalian sudah melihat kode program di bawah dan merasa kebingungan maka perhatikan penjelasan singkat berikut ini. Kode program rumit di bawah sebenarnya mengusung konsep nested list atau list di dalam list. Jika kita sederhanakan kode program di bawah maka akan menjadi seperti berikut:

# ROOT NODE
Elektronik = []

# NODE CHILDREN
Laptop = ["Windows", "Linux", "Mac"]
Smartphone = ["Samsung", "Xiaomi", "Realme"]
TV = ["LG", "Thosiba"]

# ADD EDGE
Elektronik.append(Laptop)
Elektronik.append(Smartphone)
Elektronik.append(TV)

Kode di atas adalah ilustrasi sederhana dari cara menyusun dan menambahkan node pada struktur data tree. Namun berbeda dengan kode di atas yang node hanya berupa list, pada implementasi di bawah node adalah sebuah object yang menyimpan/menghubungkan childrennya melalui atribute children dengan tipe data list.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self):
        level = self.get_level()
        space = ''
        if (level > 0):
            space = " " * level + "|" + "_" * self.get_level()
        print(space + self.data)
        if len(self.children) > 0:
            for child in self.children:
                child.print_tree()

    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level += 1
            p = p.parent
        return level

def build_node():
    root = TreeNode("Elektronik")

    # Laptop Tree
    laptop = TreeNode("Laptop")
    laptop.add_child(TreeNode("Windows"))
    laptop.add_child(TreeNode("Linux"))
    laptop.add_child(TreeNode("Mac"))

    # Smartphone
    smartphone = TreeNode("Smartphone")
    smartphone.add_child(TreeNode("Samsung"))
    smartphone.add_child(TreeNode("Xiaomi"))
    smartphone.add_child(TreeNode("Realme"))

    # TV
    TV = TreeNode("TV")
    TV.add_child(TreeNode("LG"))
    TV.add_child(TreeNode("Thosiba"))

    # Root
    root.add_child(laptop)
    root.add_child(smartphone)
    root.add_child(TV)

    return root

tree = build_node()
tree.print_tree()

Output:

Elektronik
 |_Laptop
  |__Windows
  |__Linux
  |__Mac
 |_Smartphone
  |__Samsung
  |__Xiaomi
  |__Realme
 |_TV
  |__LG
  |__Thosiba

2.1 Binary Tree

Struktur Data tree dapat dipecah lagi menjadi beberapa jenis yang salah satunya adalah Binary Tree. Binary Tree merupakan tree yang setiap nodenya hanya diizinkan memiliki maksimal 2 node saja atau node kiri dan node kanan atau salah satunya. Implementasi dari Binary Tree ini adalah Binary Search yang pernah kita pelajari di pertemuan sebelumnya. Berikut merupakan ilustrasi dari Binary Tree:

Untuk

Dengan menggunakan binary tree kita dapat melakukan pengaksesan terhadap setiap nodenya atau mengunjungi semua node pada tree. Untuk melakukan hal tersebut terutama pada binary tree kita dapat melakukan traversal tree menggunakan 3 algoritma yaitu Pre-Order Traversal, In-Order Traversal, dan Post-Order Traversal.

3. Tree Traversal

Mari kita lakukan 3 macam tree traversal tadi menggunakan binary tree berikut:

Berikut kode program untuk membuat binary tree di atas:

class CreateNode:
    def __init__(self, data):
        self.data = data
        self.children_left = None
        self.children_right = None

Root = CreateNode(25)

# Level 1
Root.children_left = CreateNode(15)
Root.children_right = CreateNode(50)

# Level 2 (KIRI)
Root.children_left.children_left = CreateNode(10)
Root.children_left.children_right = CreateNode(22)
# Level 2 (KANAN)
Root.children_right.children_left = CreateNode(35)
Root.children_right.children_right = CreateNode(70)

# Level 3 (KIRI)
Root.children_left.children_left.children_left = CreateNode(4)
Root.children_left.children_left.children_right = CreateNode(12)
Root.children_left.children_right.children_left = CreateNode(18)
Root.children_left.children_right.children_right = CreateNode(24)
# Level 3 (KANAN)
Root.children_right.children_left.children_left = CreateNode(31)
Root.children_right.children_left.children_right = CreateNode(44)
Root.children_right.children_right.children_left = CreateNode(66)
Root.children_right.children_right.children_right = CreateNode(90)

3.1 Pre-Order Traversal

Ketika melakukan pre-order traversal maka traversal akan dilakukan dengan mengoutputkan nilai node yang dikunjungi terlebih dahulu kemudian mengunjungi tiap-tiap node tree dan sub tree dari ruas sebelah kiri. Karena node pertama yang dikunjungi adalah root maka output pertama adalah nilai dari root sehingga disebut dengan Pre-Order Traversal.

Root -> Left -> Right

class CreateNode:
    def __init__(self, data):
        self.data = data
        self.children_left = None
        self.children_right = None

def PreOrder(self):
        if self:
            print(self.data, end=' ')
            if self.children_left:
                self.children_left.PreOrder()
            if self.children_right:
                self.children_right.PreOrder()

3.2 In-Order Traversal

Ketika melakukan In-Order Traversal maka akan dilakukan traversal dengan mengunjungi node hingga ditemukan node leaf kemudian dioutputkan nilainya. Traversal dilakukan dengan mengunjungi ruas kiri terlebih dahulu dari tree dan subtree yang kemudian setelah ruas kiri selesai maka akan dilanjutkan ke ruas kanan. Namun untuk berpindah ke ruas kanan, maka akan melewati root terlebih dahulu dan mengoutputkan nilainya, karena itu lah traversal ini disebut In-Order Traversal

Left -> Root -> Right

class CreateNode:
    def __init__(self, data):
        self.data = data
        self.children_left = None
        self.children_right = None

    def InOrder(self):
        if self:
            if self.children_left:
                self.children_left.InOrder()
            print(self.data, end=' ')
            if self.children_right:
                self.children_right.InOrder()

3.3 Post-Order Traversal

Pada Post-Order Traversal traversal dilakukan dengan mengunjungi node pada ruas kiri terlebih dahulu hingga ditemukan ujung / node leafnya kemudian dioutputkan nilainya, setelah itu akan melanjutkan traversal ke ruas kanan hingga ditemukan node leafnya kemudian dioutputkan nilainya. Perbedaannya dengan In-Order adalah jika in order sebelum mengunjungi ruas kanan maka akan dioutputkan nilai penghubung antara ruas kiri dan kanan, tetapi pada Post-Order akan dikunjungi dulu ruas kanannya kemudian nilai penghubung antar ruas akan diouputkan.

Left -> Right -> Root

class CreateNode:
    def __init__(self, data):
        self.data = data
        self.children_left = None
        self.children_right = None

def PostOrder(self):
        if self:
            if self.children_left:
                self.children_left.PostOrder()
            if self.children_right:
                self.children_right.PostOrder()
            print(self.data, end=' ')