Tree

 Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node lainnya. Struktur data tree terdiri atas kumpulan simpul atau node dimana tiap tiap simpul digunakan untuk menyimpan nilai dan sebuah list rujukan ke simpul lainnya. 

Pada struktur data tree terdapat beberapa istilah penting sebagai berikut.

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 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 disebut juga external node.

4. Root

Root atau akar adalah simpul teratas dari sebuah tree.

5. Internal node

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

6. Edge

Edge merujuk pada garis yang menghubungkan antara dua buah simpul dalam tree.

7. Height of node

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

8. Depth of node

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

9. Height of tree

Height of tree adalah jalur terpanjang dari simpul akar ke simpul daun dari sebuah tree.

10. Degree of node

Degree of node adalah jumlah cabang yang melekat pada simpul.

11. Subtree

Subtree adalah setiap simpul dari tree beserta turunannya. 

Jenis-jenis tree: 

1. General tree

General tree adalah struktur data tree yang tidak memiliki batasan jumlah node pada hierarki tree.

2. Binary tree

Binary tree adalah jenis tree yang simpulnya hanya dapat memiliki paling banyak dua simpul anak (child node).

3. Balanced tree

Apabila tinggi dari subtree sebelah kiri dan subtree sebelah kanan sama, kalaupun berbeda hanya berbeda satu. 

4. Binary search tree

Binary search tree digunakan untuk berbagai algoritma pencarian dan pengurutan.