STRUKTUR DATA - Binary Tree

Binary tree adalah sebuah struktur data yang menyerupai pohon dan setiap simpulnya memiliki cabang maksimal 2. Pada setiap pohon biner memiliki Root dan Leaf. Root adalah simpul utama yang merupakan simpul awal pada suatu pohon biner. Sedangkan Leaf adalah adalah simpul terakhir yang tidak memiliki cabang lagi.

contohnya :

Pada pohon biner diatas, rootnya adalah 2 dan leafnya  adalah 2, 5, 11, 4.

Tipe-Tipe Pohon Biner
  • Perfect Binary Tree
  • Complete Binary Tree
  • Skewed Binary Tree
  • Balanced Binary Tree

Perfect Binary Tree

PBT adalah suatu pohon biner yang setiap levelnya memiliki kedalaman yang sama. Terkadang PBT juga termasuk CBT (complete binary tree).

Contoh :



Complete Binary Tree

CBT adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.

Contoh :



Skewed Binary Tree

SBT merupakan suatu pohon biner yang setiap simpulnya hanya memiliki satu anak atau satu cabang, sehingga membuatnya tidak seimbang.

Contoh :



Balanced Binary Tree

BBT adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.

contoh:





Comments

Post a Comment

POPULAR

STRUKTUR DATA - Linked List

Linked List Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.  Head adalah elemen yang berada pada posisi pertama dalam suatu linked list Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list Ada beberapa macam Linked List, yaitu : Single Linked List Double Linked List Circular Linked List Multiple Linked List Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL. contoh : contoh codingannya : struct Mahasiswa{       char nama[25];       int usia;       struct
Read more

STRUKTUR DATA - Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree

Balanced Binary Search Tree Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N  adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan seaching, kecepatan waktu merupakan hal yang cukup penting untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. untuk menetapkan tingginya, kita dapat menggunakan rumus berikut: O(log n) 2 contoh tree yang termasuk ke dalam balanced binary search tree, yaitu : - AVL Tree - Red Black Tree (RBT) AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisi
Read more

STRUKTUR DATA - B Tree and Heap & Deap

B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree  merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak. Aturan pada B-Tree : m = order Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak Root memiliki anak minimal 2, selama root bukan leaf Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1 Data yang tersimpan pada node harus terurut secara inorder Semua leaf berada pada level yang sama, level terbawah Berikut contoh B-Tree : B-Tree order 4 B-Tree order 6 Operasi : Searching Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-ta
Read more