Pohon (struktur data): Perbedaan antara revisi

[[ImageBerkas:binary_tree.svg|thumbjmpl|Sebuah contoh sederhana pohon tidak terurut.]]

Dalam [[ilmu komputer]], sebuah '''Pohon''' adalah suatu [[struktur data]] yang digunakan secara luas yang menyerupai [[struktur pohon]] dengan sejumlah simpul[[Pohon (struktur data)#Simpul (''node'')|simpul]] yang terhubung.

Sebuah '''Simpul''' dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data terpisah atau sebuah bagian pohon itu sendiri. Setiap simpul dalam sebuah pohon memiliki nol atau lebih '''simpul anak''' (''child nodes''), yang berada dibawahnya dalam pohon (menurut perjanjian, pohon berkembang ke bawah, tidak seperti yang dilakukannya di alam). Sebuah simpul yang memiliki anak dinamakan '''simpul orang tuaayah''' (''parent node'') atau '''simpul leluhur''' (''ancestor node'') atau [[Superior (hierarchy)|superior]]. Sebuah simpul palikpaling banyak memiliki satu orang tuaayah. Tinggi dari pohon adalah panjang maksimal jalan ke sebuah daun dari simpul tersebut. Tinggi dari akar adalah ''tinggi'' dari pohon. Kedalaman dari sebuah simpul adalah panjang jalan darike akarakarnya menujudari kesimpul sebuah dauntersebut.

[[ImageBerkas:AVLtreef.svg|thumbjmpl|9, 14, 19, 67 dan 76 adalah daun.]]

Sebuah '''simpul dalam''' adalah semua simpul dari pohon yang memiliki anak dan bukan merupakan daun. Beberapa pohon hanya menyimpan data didalamdi dalam simpul dalam, meskipun ini mempengaruhimemengaruhi dinamika penyimpanan data dalam pohon. Sebegai contoh, dengan daun yang kosong, seseorang dapat menyimpan sebuah pohon kosong dengan satu daun. Bagaimanapun juga dengan daun yang dapat menyimpan data, tidak dimungkinkan untuk menyimpan pohon kosong kecuali jika seseorang memberikan beberapa jenis penanda data di daun yang menandakan bahwa daun tersebut seharusnya kosong (dengan demikian pohon itu seharusnya kosong juga).

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, mengandung mengandungmembentuk sebuah sub pohon dari ''P''. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang berhubunganterhubung dengan simpul apapunlain yang lainmanapun dinamakan '''sub pohon asli''' (''proper subtree'').

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 didalamnyadi 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.

Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada [[heap (programming)|heap]] (bedakan dengan (not to be confused with the [[heap (struktur data)|heap struktur data]]) yang mengacu pada anaknya, orang tuanyaayahnya, atau keduanya, atau seperti data materi dalam [[array]], dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh [[binary heap]])

dalamDalam [[teori grafik]], sebuah pohon adalah sebuah grafik [[asiklis]] yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal diluardi luar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orangtua-orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil '''hutan'''

Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orangtuaorang 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 orangtuaayah dikunjungi sebelum anaknya dinamakan ''pre-order walk''; sebuah penelusuran dimana anaknya dikunjungi sebelum orang tuaayahnya masing-masing dinamakan ''post-order walk''.

* [[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–423308–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–217214–217. Chapters 12–1412–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), hal.253–320253–320.

* [http://www.nist.gov/dads/HTML/tree.html Descripsi dari ''Dictionary of Algorithms and Data Structures'']

* [http://www.aei.mpg.de/~peekas/tree/ STL-like C++ tree class]{{Pranala mati|date=Maret 2021 |bot=InternetArchiveBot |fix-attempted=yes }}

* [http://www2.informatik.uni-halle.de/lehre/leda/MANUAL/List_data_structures.html List of data structures dari LEDA] {{Webarchive|url=https://web.archive.org/web/20071023190126/http://www2.informatik.uni-halle.de/lehre/leda/MANUAL/List_data_structures.html |date=2007-10-23 }}

[[Kategori:StrukturPohon (struktur data)| ]]

[[Kategori:Ilmu komputerFonologi]]