Pages

Data Structure 4

Image result for binary tree

Root : node yang berada di paling atas.

Edge : garis yang menghubungi parent dan child.

contoh: garis yang menghubungkan A dan B.

Height/Depth : maksimal degree dari node di dalam tree.

Height : 4.

Parent D adalah B.

Children D tidak ada, sedangkan children C adalah E dan F.

Leaf : node yang tidak memiliki children

contoh: D

Sibling : node yang memiliki orang tua yang sama

contoh : H dan I

Degree sebuah node : jumlah sub tree sebuah node

A dihubungkan ke B, maka A adalah ancestor dari B dan B adalah descendant dari A.

Binary Tree

tree yang setiap cabangnya memiliki maksimal 2 cabang.

cabang yang kanan disebut right child dan yang kiri disebut left child.

Perfect binary tree : binary tree yang setiap levelnya memiliki depth yang sama.

Complete binary tree : binary tree yang setiap levelnya, kecuali mungkinan yang terakhir terpenuhi dan semua node nya berada di kiri.

Skewed binary tree : binary tree yang masing-masing nodenya memiliki hanya 1 cabang.

Balanced binary tree : binary tree yang jarak root ke leaf nya sama dengan jarak antara cabang yang kanan dan yang kiri.