Struktur Data - Elemen Set

Set adalah dasar untuk ilmu komputer seperti halnya matematika. Sedangkan set matematika tidak berubah, set yang dimanipulasi oleh algoritma dapat tumbuh, menyusut, atau berubah seiring waktu. Kita menyebutnya set dinamis. Algoritma mungkin memerlukan beberapa jenis operasi yang berbeda untuk dilakukan pada set. Sebagai contoh, banyak algoritma hanya membutuhkan kemampuan untuk memasukkan elemen ke dalam(insert elements into), menghapus elemen dari(delete elements from), dan menguji keanggotaan dalam satu set. Kita menyebut satu set dinamis yang mendukung operasi ini sebuah kamus atau dictionary.

Algoritma lainnya membutuhkan operasi yang lebih rumit. Misalnya, min-priority queues yang terdapat pada konteks struktur data heap, mendukung operasi memasukkan ‘insert elements into’ dan mengekstrak elemen terkecil dari satu set. Cara terbaik untuk menerapkan set dinamis tergantung pada operasi yang harus didukung.

Dalam implementasi khas dari set dinamis, setiap elemen diwakili oleh objek yang atributnya dapat diperiksa dan dimanipulasi jika kita memiliki pointer ke objek, kita sudah melihat contohnya dimateri linked list. Beberapa jenis kumpulan dinamis mengasumsikan bahwa salah satu atribut objek adalah kunci pengidentifikasi (identifying key). Jika tombolnya berbeda, kita dapat menganggap set dinamis sebagai satu set key values

Objek mungkin berisi data satelit, yang dibawa-bawa dalam atribut objek lain tetapi tidak digunakan oleh implementasi set. Mungkin juga memiliki atribut yang dimanipulasi oleh operasi yang ditetapkan; atribut ini mungkin berisi data atau penunjuk ke objek lain di set.

Beberapa set dinamis mengandaikan bahwa key diambil dari yang benar-benar dipesan set, seperti bilangan real, atau himpunan semua kata di bawah urutan abjad biasa. Pemesanan total atau total ordering memungkinkan kita untuk menentukan elemen minimum dari set, misalnya, atau untuk berbicara tentang elemen berikutnya yang lebih besar dari elemen yang diberikan dalam satu set.

Sekarang kita masuk ke Operasi pada set dinamis. Operasi pada set dinamis dapat dikelompokkan ke dalam dua kategori: queri, yang hanya mengembalikan informasi tentang set, dan memodifikasi operasi, yang mengubah set. Berikut ini adalah daftar operasi tipikal. Aplikasi khusus apa pun biasanya hanya membutuhkan sedikit dari ini untuk diimplementasikan. Ini penting ketika anda sudah mendalami struktur data.

SEARCH(S,k)

Kueri yang, diberi set S dan key value k, mengembalikan pointer x ke elemen dalam S sehingga x.key = k, atau NIL jika tidak ada elemen tersebut milik S.

INSERT(S,x)

Operasi modifikasi yang menambah set S dengan elemen yang ditunjukkan oleh x. Kita biasanya berasumsi bahwa atribut apa pun dalam elemen x yang dibutuhkan oleh implementasi set telah diinisialisasi.

DELETE(S,x)

Operasi pengubahan itu, memberikan pointer x ke elemen di set S, menghapus x dari S. (Perhatikan bahwa operasi ini mengambil pointer ke elemen x, bukan key value.)

MINIMUM(S)

Kueri total order set S yang mengembalikan pointer ke elemen S dengan Key terkecil.

MAXIMUM(S)

Kueri total order set S yang mengembalikan pointer ke elemen S dengan key terbesar SUCCESSOR(S,x) Kueri yang memberikan elemen x yang key-nya berasal dari total order set S, mengembalikan pointer ke elemen yang lebih besar berikutnya di S, atau NIL jika x adalah elemen maksimum

PREDECESSOR(S,x)

Kueri yang memberikan elemen x yang key-nya berasal dari total order set S,mengembalikan pointer ke elemen terkecil berikutnya pada S, atau NIL jika x adalah elemen minimum

Dalam beberapa situasi, kita dapat memperpanjang kueri SUCCESSOR dan PREDECESSOR sehingga mereka berlaku untuk set dengan key tidak jelas. Untuk set pada key, anggapan normal adalah panggilan ke MINIMUM diikuti n-1 panggilan ke SUCCESSOR menyebutkan unsur-unsur dalam himpunan dalam susunan terurut.

Kita biasanya mengukur waktu yang dibutuhkan untuk menjalankan operasi yang ditetapkan dalam hal ukuran set. Nanti akan dibahas pada materi Red-Black Tree yang menjelaskan struktur data yang dapat mendukung salah satu operasi yang tercantum di atas pada satu set ukuran n dalam waktu O(lg )

Anda bisa mencari beberapa struktur data yang dapat di gunakan untuk menerapkan set dinamis; karena akan kita gunakan banyak dari ini nantinya untuk membangun algoritma yang efisien untuk berbagai masalah. Begitu pun esensi bekerja dengan struktur data sederhana seperti stack, queues atau linked lists. Ini juga menunjukkan bagaimana mengimplementasikan objek dan pointer dalam lingkungan pemrograman yang tidak mendukung program alam. Jika Anda telah mengambil kursus pemrograman pengantar, maka banyak dari materi ini yang seharusnya Anda kenal.

Oke cukup sekian pengantar dari Struktur Data set ini, pengembangannya nanti akan kita bahas dimateri selanjutnya.