Struktur data part 3

Berhubung saya suka sama cara dosen ngejelasinnya mata kuliah ini, maka saya mau bahas tentang tubes saya. Apa yang dijelasin di algoritma yang udah saya post sebelumnya. 

Yang saya bahas cuma double linked list dan binnary tree aja, soalnya tubesnya cuman dua itu aja...

1. Algoritma tree c++ 

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan
hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.

Tree biasa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.  

Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan
satu sama lain (disebut Subtree). Untuk lebih jelasnya, di bawah akan diuraikan istilah-
istilah umum dalam tree.

Predecessor : Node yang berada di atas node tertentu
Successor : Node yang berada dibawah node tertentu
Ancestor : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Descendant : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Parent : Predecessor 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 punyak predecessor
Leaf : Node-node dalam tree yang tak memiliki successor
Degree : Banyaknya child yang dimiliki suatu node

Binary Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal
dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut
tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Implementasi Binary Tree
Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double
linkedlist.

dikutip dari : modul algoritma dan struktur data II stikom bali 

2. Double linked list 

implementasi binary tree

Elemen-elemen dihubungkan dengan dua pointer dalam satu elemen. Struktur ini
menyebabkan list melintas baik ke depan maupun ke belakang.
Masing-masing elemen pada double linked list terdiri dari tiga bagian, disamping
data dan pointer next, masing-masing elemen dilengkapi dengan pointer prev yang
menunjuk ke elemen sebelumnya. Double linked list dibentuk dengan menyusun
sejumlah elemen sehingga pointer next menunjuk ke elemen yang mengikutinya dan
pointer prev menunjuk ke elemen yang mendahuluinya.
Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen
pertama menunjuk NULL. Untuk menunjukkan tail dari double linked list tersebut, maka
pointer next dari elemen terakhir menunjuk NULL. Susunan elemen yang dihubungkan
dalam bentuk double linked list dapat dilihat pada Gambar 2.3

Untuk melintas kembali melalui double linked list, kita gunakan pointer prev dari
elemen yang berurutan pada arah tail ke head. Double linked list mempunyai fleksibilitas
yang lebih tinggi daripada single linked list dalam perpindahan pada list. Bentuk ini
sangat berguna ketika akan meletakkan suatu elemen pada list dan dapat memilih
dengan lebih bijaksana bagaimana memindahkannya. Sebagai contoh, salah satu
fleksibilitas dari double linked list adalah dalam hal memindahkan elemen daripada
menggunakan single linked list.