Struktur Data Tree

 Struktur Data Tree: Pengertian, Jenis, dan Kegunaannya

Istilah-istilah pada Tree

Layaknya sebuah pohon yang memiliki akar, cabang, dan daun yang terhubung satu sama lain, pada struktur data tree terdapat beberapa istilah penting yang mirip seperti istilah di dunia nyata, antara lain:

 

1. Node

Node atau simpul adalah entitas pada struktur data tree yang mengandung sebuah nilai dan pointer yang menunjuk simpul di bawahnya (child node).

 

2. Child node

Child node atau simpul anak adalah simpul turunan dari simpul di atasnya.

3. Leaf Node

Leaf node atau simpul daun adalah simpul yang tidak memiliki child node dan merupakan node yang paling bawah dalam struktur data tree. Simpul ini biasa disebut juga sebagai external node

3. Root

Root atau akar adalah simpul teratas dari sebuah tree.

4. Internal node

Internal node adalah istilah untuk menyebut simpul yang memiliki minimal satu child node.

5. Edge

Edge merujuk pada garis yang menghubungkan antara dua buah simpul dalam tree. Jika sebuah tree memiliki N node maka tree tersebut akan memiliki (N-1) edge. Hanya ada satu jalur dari setiap simpul ke simpul lainnya.

6. Height of node

Height of node adalah jumlah edge dari sebuah node ke leaf node yang paling dalam

7. Depth of node

Depth of node adalah banyaknya edge dari root ke sebuah node.

8. Height of tree

Height of tree dapat diartikan sebagai panjang jalur terpanjang dari simpul akar ke simpul daun dari seuah tree

9. Degree of node

Jumlah cabang yang melekat pada simpul disebut Degree of node atau derajat simpul. Derajat simpul pada sebuah leaf node adalah 0. 

Selain Degree of node, terdapat juga Degree of tree yaitu derajat maksimum simpul di antara semua simpul pada tree

10. Subtree

Subtree adalah setiap simpul dari tree beserta turunannya.

Jenis-jenis Tree

Struktur data tree dapat diklasifikasikan ke dalam 4 jenis, yaitu: General tree, Binary tree, Balanced tree, dan Binary search tree.

1. General tree

Struktur data tree yang tidak memiliki batasan jumlah node pada hierarki tree disebut General tree. Setiap simpul atau node bebas memiliki berapapun child node. Tree jenis adalah superset dari semua jenis tree.

2. Binary tree  

Binary tree adalah jenis tree yang simpulnya hanya dapat memiliki paling banyak 2 simpul anak (child node). Kedua simpul tersebut biasa disebut simpul kiri (left node) dan simpul kanan (right node). Tree tipe ini lebih populer daripada jenis lainnya.

3. Balanced tree

Apabila tinggi dari subtree sebelah kiri dan subtree sebelah kanan sama atau kalaupun berbeda hanya berbeda 1, maka disebut sebagai balanced tree. 

4. Binary search tree

Sesuai dengan namanya, Binary search tree digunakan untuk berbagai algoritma pencarian dan pengurutan. Contohnya seperti AVL tree dan Red-black tree. Struktur data tree jenis ini memiliki nilai pada simpul sebelah kiri lebih kecil daripada induknya. Sedangkan nilai simpul sebelah kanan lebih besar dari induknya.