TREE(pohon)

                Pengertian Tree dalam Struktur Data

                      Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkanhubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemenKHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untukjelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

—  Parent : predecssor satu level di atas suatu node.

—  Child : successor satu level di bawah suatu node.

—  Sibling : node-node yang memiliki parent yang sama dengan suatu node.

—  Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

—  Size : banyaknya node dalam suatu tree.

—  Height : banyaknya tingkatan/level dalam suatu tree.

—  Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

—  Leaf : node-node dalam tree yang tak memiliki seccessor.

—  Degree : banyaknya child yang dimiliki suatu node.

Pengertian Binaary Tree dalam Struktur data  Pohonbiner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal duasubtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap nodedalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Jumlah maksimum node pada setiap tingkat adalah 2ⁿ, Node pada binary treemaksimumnya berjumlah 2ⁿ-1.

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 terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

istilah-istilah umum dalam tree

Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

a) Prodecessor : node yang berada diatas node tertentu.

b) Successor : node yang berada di bawah node tertentu.

c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

e) Parent : predecssor satu level di atas suatu node.

f) Child : successor satu level di bawah suatu node.

g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

i) Size : banyaknya node dalam suatu tree.

j) Height : banyaknya tingkatan/level dalam suatu tree.

k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

l) Leaf : node-node dalam tree yang tak memiliki seccessor.

m) Degree : banyaknya child yang dimiliki suatu node.

contoh program tree

uses crt;

Type

Tree = ^Simpul;

Simpul = Record

Info : char;

Kiri : Tree;

Kanan : Tree;

End;

Function BARU(Hrf : Char) : Tree;

Var Temp : Tree;

Begin

New(Temp);

Temp^.Info := Hrf;

Temp^.Kiri := NIL; Temp^.Kanan := NIL;

BARU := Temp;

End;

Procedure MASUK(Var Pohon : Tree; Hrf : Char);

Begin

If Pohon = NIL Then

Pohon := BARU(Hrf)

Else

Begin

If Pohon^.Info > Hrf then

MASUK(Pohon^.Kiri,Hrf)

Else If Pohon^.Info < Hrf then

MASUK(Pohon^.Kanan,Hrf)

Else

Writeln('Karakter', Hrf, 'Sudah ada di Tree');

End;

End;

Procedure PREORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

Write(Temp^.Info,' ');

PREORDER(Temp^.Kiri);

PREORDER(Temp^.Kanan);

End;

End;

Procedure INORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

INORDER(Temp^.Kiri);

Write(Temp^.Info,' ');

INORDER(Temp^.Kanan);

End;

End;

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Penambahan node di AVL Tree

                                  Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan:Single rotation dan Double rotation

Single Rotation

     Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar 2.

Sebutkan beberapa jenis tree yang memiliki sifat khusus

v Create : Membentuk binary tree baru yang masih kosong.

                v Clear : Mengosongkan binary tree yang sudah ada.

                v Empty : Function untuk memeriksa apakah binary tree masih kosong.

                v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

                v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

                v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

                v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.