Struktur Data Hirarkis: Terminologi

10 Maret 1999

Motivasi

• banyak aplikasi menggunakan informasi dan data yang secara alami memiliki struktur hirarkis
• berguna dalam membantu memecahkan banyak masalah algoritmis

Tree Statis vs. Dinamis

• Dalam sejumlah aplikasi data yang tersimpan serta struktur hirarkisnya tidak akan berubah sejak mulai proses, hingga proses selesai. Untuk aplikasi tersebut digunakan struktur tree yang statis.
• Untuk aplikasi lain data dan informasi yang digunakan berubah-ubah, mungkin karena munculnya data baru, dihilangkannya suatu data tersimpan atau perubahan harga data tersimpan yang umumnya mengakibatkan perubahan struktur hirarkis tersebut. Untuk itu digunakan struktur tree dinamis.

Terminologi

• Tree (atau pohon)

sejumlah node yang berhubungan secara hirarkis dimana suatu node pada suatu hirarki merupakan cabang dari node dengan hirarki yang lebih tinggi dan juga memiliki cabang ke beberapa node lainnya dengan hirarki yang lebih rendah.
• Root (atau akar)

Node dengan hirarki tertinggi dinamakan root.
• leaf (atau daun)

node yang tidak memiliki cabang.
• Internal node (atau node dalam)

node yang bukan merupakan leave.
• edge (atau sisi atau cabang)

menyatakan hubungan hirarkis antara kedua node yang terhubungkan, biasanya digambarkan berarah (berupa panah) untuk menunjukkan node asal edge lebih tinggi dari node tujuan dari edge.
• Level (atau tingkat) suatu node

bilangan yang menunjukan hirarki daroi suatu node, root memiliki level 0, node cabang dari root memiliki level 1, node cabang berikutnya dari node level 1 memiliki level 2, dan seterusnya.
• Height (atau tinggi) suatu tree

sama dengan level dengan angka terbesar (hirarki terendah) suatu node yang ada dalam tree atau bisa juga didefinisikan sebagai jumlah sisi terbanyak dari root hingga suatu leaf yang ada di tree.
• Depth (atau kedalaman) suatu node

Jumlah sisi dari root hingga node ybs.
• Subtree (atau subpohon)

sebagian dari tree mulai dari suatu node N melingkupi node-node yang berada dibawah hirarkinya sehingga dapat dipandang sebagai suatu tree juga yang mana N sebagai root dari tree ini.
• Tree kosong

Suatu tree yang tidak memiliki suatu node pun.
• Tree dengan urutan

letak geometris node-node yang merupakan cabang yang sama dari suatu node adalah penting; biasanya urutan dari kiri ke kanan.

Terminologi akibat hubungan “kekeluargaan” antar node.
 

• anak

node cabang dari suatu node
• ayah

node mana bahwa suatu node menjadi cabangnya
• sibling

node-node yang berayah sama; sibling kiri/kanan adalah node yang terletak tepat disebelah kirinya/kanannya
• descendant

seluruh node berada di bawah hirarki suatu node
• ancestor

node-node yang mana saja sehingga suatu node tertentu menjadi descendant mereka

Terminologi akibat hubungan geometris antar node:

 
• anak ke i

anak suatu node, pada urutan dari kiri ke kanan, dengan nomor urutan ke i
• anak kiri, anak tengah, kanan

pada suatu hubungan sibling dengan jumlah node 3 maka anak pertama adalah anak kiri, anak kedua adalah anak tengah, dan anak ke tiga adalah anak kanan.
• node paling atas root.

Binary Tree

• suatu kelas dari tree yang memiliki sifat: setiap node hanya dapat bercabang satu, atau dua atau tidak memiliki cabang.
• Definisi rekursif dari Binary Tree: suatu binary tree adalah tree kosong atau suatu node yang hanya memiliki subtree kiri dan subtree kanan yang merupakan binary tree.

Subkelas-subkelas binary tree:

• Full Binary Tree

Subkelas binary tree di mana setiap internal node tepat memiliki dua cabang. sayang, anda harus menggunakan browser yang java 1.1.* enable.....
 
• Perfect Binary Tree

subkelas full binary tree yang mana semua node leaf berada pada level yang sama. sayang, anda harus menggunakan browser yang java 1.1.* enable.....
 
• Complete Binary Tree

Suatu binary tree yang memiliki sifat
• node-node leafnya hanya berada pada satu level terendah terletak merapat ke sebelah kiri atau
• node-node leafnya berada di dua level terendah dengan bagian tree hingga level sebelum terendah membentuk perfect binary tree.
sayang, anda harus menggunakan browser yang java 1.1.* enable.....

Secara rekursif, bisa juga didefinikan bahwa CBT suatu binary tree yang memiliki kemungkinan:

• jika tingginya 0 adalah adalah binary tree node tunggal.
• jika tinginya 1 adalah binary binary tree dengan anak kiri dan anak kanan atau binary tree hanya dengan anak kiri.
• jika tingginya h, adalah suatu perfect binary tree atau suatu binary tree dengan root memiliki:
• subtree kiri dari root merupakan perfect  binary tree dengan tinggi h-1 dan subtree kanan merupakan complete binary tree dengan tinggi h-1, atau
• subtree kiri dari root merupakan complete binary tree dengan tinggi h-1 dan subtree kanan merupakan perfect binary tree dengan tinggi h-2.

 
• Extended binary tree

Binary tree dengan penggambaran tree-tree kosong dengan legend node yang lain.

Representasi Sikuensial untuk Binary Tree

• Node-node mulai dari root ke leaf level, demi level dari kiri kekanan diberi bernomor, misalnya mulai dari 0, 1, 2, 3, dan seterusnya hingga node leaf pada level terendah dan pada posisi terkanan.
sayang, anda harus menggunakan browser yang java 1.1.* enable.....
• Cara penomoran lain adalah mulai dari 1, 2, dst. dengan mengkosongkan elemen pertama array seperti pada buku teks.) Penomoran ini adalah angka-angka indeks dari sel dalam array yang akan ditempati node-node ybs. dari tree.

 

• root

berada di 0
• P dengan ayah P

jika node P berada di I maka ayahnya akan berada di  floor((I-1)/2)
• P dengan anak kiri/kanan P

Jika node P berada di I maka anak kirinya akan berada di  (I*2+1) dan anak kanan berada di (I*2+2)
• node-node level ke L

menempati sebanyak 2^L sel mulai sel ke (2^L - 1), (2^L), (2^L + 1), . . hingga.sek ke (2^L  + 2^L - 2) sibling node bernomor ganjil memiliki siblingnya bernomor genap sebelumnya (di sebelah kirinya), dansebaliknya yang bernomor genap memiliki sibling node bernomor ganjil sesudahnya (disebelah kanannya).

Pertanyaan

• Berapakah tinggi dari dari suatu complete binary tree dengan jumlah node adalah n? Jawab:  floor(log₂ n)
• Berapakah indeks dari node leaf pertama (indeks paling kecil dari leaf) yang ada pada complete binary tree dengan jumlah node n (indeks mulai dari 0, 1, . . . )? Jawab:  floor(n/2)
• Bagaimanakah hubungan-hubungan di atas apabila pengisian array mulai dari elemen ke satu (bukan ke nol sebagaimana di atas)?

Contoh heaptree di dalam pengurutan Heapsort yaitu suatu pengurutan berbasis priority queue.