Tree : Struktur Data

TREE

Tree - Sebuah pohon pencarian biner adalah pohon di mana setiap node memiliki anak kiri dan kanan. Baik anak, atau keduanya anak-anak, mungkin hilang. Gambar 3-2 mengilustrasikan sebuah pohon pencarian biner. Dengan asumsi k mewakili nilai node yang diberikan, maka pohon pencarian biner juga memiliki properti berikut: semua anak di sebelah kiri node memiliki nilai lebih kecil dari k, dan semua anak-anak di sebelah kanan node memiliki nilai lebih besar dari k. Bagian atas pohon itu dikenal sebagai akar, dan node terkena di bagian bawah dikenal sebagai daun. Pada Gambar 3-2, akar adalah simpul 20 dan daun node 4, 16, 37, dan 43. Ketinggian pohon adalah panjang jalan terpanjang dari akar ke daun. Untuk contoh ini ketinggian pohon adalah 2.
Dalam mempelajari tree, seharusnya kita juga harus memperlajari macam macam dari sorting. Karena itu saling berkaitan.

 

Binary tree

Sebuah pohon pencarian biner adalah pohon di mana setiap node memiliki anak kiri dan kanan. Baik anak, atau keduanya anak-anak, mungkin hilang. Gambar 3-2 mengilustrasikan sebuah pohon pencarian biner. Dengan asumsi k mewakili nilai node yang diberikan, maka pohon pencarian biner juga memiliki properti berikut: semua anak di sebelah kiri node memiliki nilai lebih kecil dari k, dan semua anak-anak di sebelah kanan node memiliki nilai lebih besar dari k. Bagian atas pohon itu dikenal sebagai akar, dan node terkena di bagian bawah dikenal sebagai daun. Pada Gambar 3-2, akar adalah simpul 20 dan daun node 4, 16, 37, dan 43. Ketinggian pohon adalah panjang jalan terpanjang dari akar ke daun. Untuk contoh ini ketinggian pohon adalah 2.

 

Penyisipan dan penghapusan

Mari kita memeriksa sisipan dalam pohon pencarian biner untuk menentukan kondisi yang dapat menyebabkan pohon seimbang. Untuk menyisipkan 18 di pohon pada Gambar 3-2, pertama kita mencari nomor itu. Hal ini menyebabkan kita untuk tiba di simpul 16 dengan tempat untuk pergi. Sejak 18> 16, kita hanya menambahkan node 18 untuk anak kanan dari simpul 16 (Gambar 3-4).

Sekarang kita dapat melihat bagaimana pohon yang tidak seimbang dapat terjadi. Jika data yang disajikan dalam urutan menaik, setiap node akan ditambahkan ke kanan dari node sebelumnya. Ini akan membuat satu rantai panjang, atau linked list. Namun, jika data disajikan untuk dimasukkan dalam urutan acak, maka pohon yang lebih seimbang adalah mungkin.

Penghapusan mirip, tapi mengharuskan properti pohon pencarian biner dipertahankan. Misalnya, jika simpul 20 pada Gambar 3-4 dihapus, maka harus diganti oleh simpul 37. Hal ini menyebabkan pohon ditunjukkan dalam Gambar 3-5. Alasan untuk pilihan ini adalah sebagai berikut. Penerus untuk simpul 20 harus dipilih sedemikian rupa sehingga semua node ke kanan lebih besar. Oleh karena itu kita perlu memilih node dihargai terkecil kanan simpul 20. Untuk membuat seleksi, rantai sekali ke kanan (node ​​38), dan kemudian rantai ke kiri sampai node terakhir ditemukan (node ​​37). Ini adalah penerus untuk simpul 20.

 

Implementasi

Implementasi ANSI-C untuk pohon pencarian biner disertakan. Typedef T dan perbandingan operator compLT dan compEQ harus diubah untuk mencerminkan data yang tersimpan di pohon. Setiap Node terdiri dari kiri, kanan, dan pointer menunjuk orang tua setiap anak dan orang tua. Data disimpan di bidang data. Pohon ini berdasarkan pada akar, dan awalnya NULL. Fungsi insertNode mengalokasikan node baru dan memasukkan di pohon. Fungsi deleteNode menghapus dan membebaskan simpul dari pohon. Fungsi findNode mencari pohon untuk nilai tertentu.
(Baca juga: teknik sorting dalam struktur data)

Tweet

Subscribe to receive free email updates: