Binary Tree - 1801376815 - Arifiadi Nurrizqi

Binary Tree

Binary Tree adalah sebuah pohon dari struktur data dimana setiap simpul memiliki paling banyak 2 anak pada node.

Jenis-jenis binary tree:
1. Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki 2 anak dan tiap subtree harus mempunyai panjang path yang sama.

2. Complete Binary Tree
Mirip dengan Full Binary Tree yang tiap subtree nya boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 anak.

3. Skewed Binary Tree
Binary Tree ini yang semua node nya (kecuali leaf) hanya memiliki 1 anak.

Implementasi Binary Tree

Binary Tree dapat diimplementasikan dalam pascal dengan menggunakan double linked list. Untuk nodenya, bisa di deklerasikan yaitu:

Type Tree = ^node;
node = record
isi = tipedata;
left,right : tree;

end;

contoh ilustrasi tree yang disusun dengan double linked list:

( LC = anak kiri | RC = anak kanan )

Binary Search Tree

Binary Search Tree adalah tree yang bersifat bahwa semua anak kiri harus lebih kecil daripada anak kanan dan parent. Juga semua anak kanan harus lebih besar dari anak kiri serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree secara umum:

Pada dasarnya operasi dalam binary search tree ini sama dengan binary tree biasa, kecuali pada operasi insert, update, delete.

Terdapat 3 operasi pada Binary Search Tree, yaitu:

1. Insert : Pada binary search tree ini insert dilakukan setelah ditemukan lokasi yang tepat.

2. Update : Seperti binary tree biasa, namun disini update akan berpengaruh pada posisi node tersebut. Setelah itu akan di update akan mengakibatkan tree tersebut bukan binary search tree lagi, maka harus dilakukan perubahan data pada binary search tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi binary search tree.

3. Delete : Sama dengan Update, namun delete dalam binary search tree juga mempengaruhi strutur dari tree tsb.

(keadaan awal merupakan lanjutan pada gambar sebelumnya)

Pada operasi diatas, delete dilakukan terhadap node dengan 2 anak. Maka untuk menggantikannya, dengan diambil node paling kiri dari kanan subtree yaitu 13.

Arifiadi Nurrizqi

1801376815