Pohon (struktur data)
Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung.
asnbdasd
Sub pohon (Subtrees)
Sebuah sub pohon adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri. Simpul apapun dalam pohon P, bersama dengan seluruh simpul dibawahnya, membentuk sebuah sub pohon dari P. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang terhubung dengan simpul lain manapun dinamakan sub pohon asli (proper subtree).
Penyusunan pohon
Terdapat dua jenis pohon. Sebuah pohon tidak terurut (unordered tree) adalah sebuah pohon dalam arti struktural semata-mata, yang dapat dikatakan memberikan sebuah simpul yang tidak memiliki susunan untuk anak dari simpul tersebut. Sebuah pohon dengan suatu susunan ditentukan, sebagai contoh dengan mengisi bilangan asli berbeda ke setiap anak dari simpul tersebut, dinamakan sebuah pohon terurut (ordered tree), dan struktur data yang dibangun di dalamnya dinamakan pohon terurut struktur data (ordered tree data structures). Sejauh ini pohon terurut merupakan bentuk umum dari pohon struktur data. Pohon biner terurut merupakan suatu jenis dari pohon terurut.
Hutan
Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.
- inorder
- lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- kunjungi akar dari pohon pertama.
- lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- preorder
- kunjungi akar dari pohon pertama.
- lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- postorder
- lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
- lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
- kunjungi akar dari pohon pertama.
Penggambaran pohon
Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada heap (bedakan dengan heap struktur data) yang mengacu pada anaknya, ayahnya, atau keduanya, atau seperti data materi dalam array, dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh binary heap)
Pohon sebagai grafik
Dalam teori grafik, sebuah pohon adalah sebuah grafik asiklis yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal diluar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil hutan
Metode traversal
Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orang tua dan anak, dinamakan menelusuri pohon, dan tindakannya adalah sebuah jalan dari pohon. Seringkali, sebuah operasi mungkin dapat dilakukan sebagai penunjuk ysng mengacu pada simpul khusus. Sebuah penelusuran dimana setiap simpul ayah dikunjungi sebelum anaknya dinamakan pre-order walk; sebuah penelusuran dimana anaknya dikunjungi sebelum ayahnya masing-masing dinamakan post-order walk.
Operasi umum
- Menghitung seluruh materi (item)
- Pencarian untuk sebuah materi
- Menambahkan sebuah materi pada sebuah posisi tertentu dalam pohon
- Menghapus sebuah materi
- Mengeluarkan seluruh bagian dari sebuah pohon pruning
- Menambahkan seluruh bagian ke sebuah pohon grafting
- Menemukan akar untuk simpul apapun
Penggunaan umum
- Memanipulasi data secara hierarki
- Membuat informasi mudah untuk dicari
- Memanipulasi data sorted lists
Referensi
- Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Edisi Ketiga. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, hal.308–423.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, dan Clifford Stein. Introduction to Algorithms, Edisi Kedua. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, hal.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), hal.253–320.