Binary Tree

       Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi dari data. Dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan ke dua subtree tersebut harus dipisah.

  -Node : elemen pohon yang berisi informasi dan penunjuk percabangan
  -Tingkat (level) : akar ditentukan bertingkat 1
  -Derajat (degree) : banyaknya turunan dari suatu node.
  -Daun (leaf) : node yang berderajat 0, dinamakan juga sebagai node eksternal.
  -Tinggi (high)/ kedalam (depth) : tingkat maksimum node dalam pohon dikurangi 1

        Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut:

• Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.
• Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.

        Beberapa Operasi dasar dalam Binary tree :

• Insertion

        

           Penyisipan sebuah elemen baru dalam binary search tree, elemen tersebut pasti akan menjadi leaf.

Menambah elemen X pada binary search tree:
                    1. mulai dari root.

2. Jika X lebih kecil dari root, maka X harus diletakkan pada sub-tree sebelah kiri.

3. Jika X lebih besar dari root, then X harus diletakkan pada sub-tree sebelah kanan.

• Delete

Penghapusan dapat terjadi pada tiga kondisi yaitu :

1. Jika penghapusan terjadi pada Leaf maka dapat langsung dilakukan penghapusan.

2. 

   Hapus pada Leaf

3. jika node punya satu anak: node parent menjadikan anak dari node yang dihapus (cucu) sebagian anaknya. (mem-by-pass node yang dihapus).



jika yang didelete mempunyai 1 anak

4.  
5. jika yang dihapus memiliki dua anak maka node dihapus dan menggantikan posisi node tersebut dengan node terkecil dari sub tree sebelah kanan (Successor).



Ambil successor

6.  

• transversal (Print out)

1. PreOrder :
Kunjungan PreOrder LRO atau sering disebut dengan depth first order menggunakan urutan sebagai berikut:
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kiri.
Kunjungi cabang kanan.

2.  InOrder  :
Kunjungan InOrder LRO atau sering disebut dengan symmetric order menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kanan.

3.  PostOrder :
Kunjungan PostOrder LRO menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Cetak isi simpul yang dikunjungi.

get in java