Saturday, 24 June 2017

BST Sebagai Segment Tree

Tahukah Anda bahwa BST dapat digunakan untuk menjawab dynamic range query, seperti mencari nilai terkecil/terbesar dari suatu rentang array? Atau juga hal-hal lebih kompleks lainnya seperti mencari subarray dengan jumlahan terbesar. Tulisan ini akan menjelaskan konsep membuat BST yang mampu melayani query tersebut, lalu menjelaskan kenapa kita membutuhkannya.

Sebagai catatan, BST yang saya maksud di sini adalah Binary Search Tree yang balanced, alias BBST.


Konsep Dasar

Terdapat beberapa konsep tentang BST yang perlu dipahami terlebih dahulu. Simak penjelasannya satu per satu.


BST dapat digunakan untuk merepresentasikan sebuah sequence

Sebuah sequence dapat direpresentasikan dengan beberapa bentuk BST, selama hasil in-order-traversal-nya sama dengan sequence tersebut. Sebagai contoh:


Pada BST tersebut, angka-angkanya tidak merepresentasikan nilai dari node yang perlu kita atur posisinya supaya memenuhi syarat BST. Kita tidak mempertahankan bentuk tersebut di sini. Lebih tepatnya, posisi-posisi node pada BST ini menyatakan indeks dari node tersebut pada bentuk sequence.

Bayangkan jika BST tersebut runtuh dan "diratakan" dengan tanah. Anda dapat melihat masing-masing BST di gambar akan membentuk sequence yang sama.

--

Sebuah subtree BST merepresentasikan suatu subsequence

Perhatikan gambar berikut untuk melihat suatu subsequence yang direpresentasikan suatu subtree.

Berikut gambar seluruh subsequence yang direpresentasikan oleh setiap subtree.


--

Operasi pada BST berlangsung dengan konsep "root to leaf"

Untuk struktur data BST yang diimplementasikan dengan AVL tree, treap, atau bahkan splay tree, setiap operasi find/insert/delete selalu mempengaruhi node-node dari root sampai dengan leaf. Pada dasarnya ketiga operasi tersebut selalu memilki pola:
  1. Kunjungi suatu node.
  2. Bila node ini bukan "node yang dicari", pergi ke anak kiri atau kanan dari node ini dan ulangi langkah 1 secara rekursif.
  3. Bila dibutuhkan, lakukan rotasi.
Pada poin ke-2, "node yang dicari" dapat bermakna null untuk insert, atau angka yang dikehendaki untuk find/delete.

Lebih jelasnya perhatikan gambar berikut untuk insert elemen berlabel D. Subtree-subtree berlabel X, Y, dan Z sama sekali tidak disentuh pada operasi ini.


--

Rotasi hanya memodifikasi node-node "leaf to root"

Yang ini sebenarnya sangat berkaitan dengan bagian sebelumnya. Proses rotasi berlangsung pada akhir pengunjungan suatu node, sebelum dilakukan backtrack ke parent. Bila diperhatikan, rotasi hanya mempengaruhi node-node dari leaf yang dikunjungi sampai pada root.

Sebagai contoh, mari kita gunakan AVL Tree. Pada gambar berikut, setelah elemen berlabel D dimasukkan, dilakukan backtrack dari leaf ke root. Saat dikunjungi node berlabel B, dilakukan rotasi ke kanan. Kemudian saat backtrack lagi ke node A, dilakukan rotasi ke kiri. Pada akhirnya BST menjadi seimbang. Kembali perhatikan bahwa subtree-subtree X, Y, dan Z tidak mengalami perubahan nilai ataupun urutan pada sequence yang direpresentasikan. 

Sequence yang direpresentasikan selalu [X, A, Y, C, D, B, Z]


Menjawab Dynamic Range Query

Pada segment tree, kita menyimpan nilai agregat pada setiap segment, yang merepresentasikan nilai-nilai suatu subsequence. Pada BST kita juga akan menyimpan nilai agregat suatu subsequence, yaitu pada root subtree yang merepresentasikan subsequence tersebut. Dengan demikian, semua node akan menyimpan nilai agregat untuk subtree/subsequence yang dia representasikan. Kita dapat memilih sejumlah subtree, menggabungkan nilai agregatnya, dan menjawab suatu query.

Misalnya pada contoh berikut, kita hendak mencari nilai agregat dari indeks 1 sampai dengan 6 (zero based), yang aslinya berisi nilai [2, 1, 8, 5, 3, 7].


Kadang-kadang, kita tidak mengambil langsung seluruh elemen pada subtree/subsequence. Hal ini terjadi ketika sebuah node:
  1. Memiliki subtree yang tidak berada di dalam rentang query.
  2. Node tersebut merupakan anggota dari rentang query.
Pada kasus ini, node itu sendiri perlu dimasukkan ke dalam penggabungan nilai agregat, seperti yang ditunjukkan gambar di atas untuk node berisi nilai 2 dan 8.
Kini masalahnya sekedar mencari node yang merepresentasikan indeks pertama dan terakhir dari rentang query, lalu gabungkan nilai agregat sepanjang path yang dibentuk antara kedua node tersebut. Panjang path ini paling banyak adalah 2 kali tinggi dari BST, yang pada kasus ini adalah O(log N).

Hal yang perlu diperhatikan adalah ketidakberadaannya informasi indeks pada node. Kita tidak mengetahui indeks ke berapa yang sedang direpresentasikan oleh suatu node, padahal informasi ini diperlukan untuk memeriksa apakah node tersebut berada di dalam rentang query.

Beruntungnya, informasi indeks suatu node dapat dicari dengan mudah. Untuk setiap node, simpan banyaknya node yang ada pada subtree-nya. Saat melakukan pencarian rekursif, kita dapat menghitung indeks ke berapa node tersebut ketika BST "diratakan" menjadi sequence. Anda yang pernah menggunakan BST untuk menjawab dynamic order statistic mungkin langsung memahami apa yang baru dijelaskan.

Perhatikan gambar berikut.


Bila subtree kiri mengandung 3 elemen, dijamin elemen-elemen pada indeks 0, 1, dan 2 berada di subtree kiri. Selain itu, root berarti memiliki indeks 3. Apabila diketahui terdapat 8 elemen di bawah dan termasuk root, berarti elemen berindeks 4, 5, 6, dan 7 diketahui berada di subtree kanan. Lakukan strategi ini secara rekursif untuk menentukan indeks yang dimiliki suatu node.


Pemeliharaan Nilai Agregat

Cara menjawab dynamic range query di atas mengasumsikan nilai agregat telah dimiliki setiap node. Memangnya bagaimana kita bisa memiliki nilai agregat tersebut pada setiap node, padahal BST sering di-insert/delete/rotate?

Rahasianya ada pada observasi bahwa node-node yang dimodifikasi hanya yang dilalui dari root ke leaf. Jadi nilai agregat suatu node hanya berubah ketika node tersebut berinteraksi dengan node yang dilalui dari root ke leaf. Sisanya tidak disentuh, sehingga tidak perlu diubah.

Setiap sesudah menyelesaikan semua modifikasi suatu node, tepat sebelum backtrack ke parent node, lakukan update terhadap nilai agregat. Paling banyak dilakukan update sebanyak ketinggian dari BST. Tidak perlu khawatir terhadap node yang dirotasi, karena rotasi pasti terjadi di node yang berhubungan dengan path dari root ke leaf. Jika setiap operasi update nilai agregat memiliki kompleksitas O(1), maka kompleksitas keseluruhannya menjadi O(log N), baik untuk insert/delete/update.

Pada gambar berikut, hanya node-node A, B, C, dan D yang perlu di-update nilai agregatnya. Perubahan ini dilakukan semasa rotasi berlangsung. Gambar pertama menyatakan kondisi awal sesudah memasukkan node D. Subtree-subtree X, Y, dan Z tidak mengalami perubahan terhadap nilai agregat.



Dengan demikian kita menjamin nilai agregat seluruh node selalu terpelihara dengan baik; atau memiliki nilai yang up to date.


Baiklah... tapi buat apa?

Sekarang kita mampu membuat "segment tree" dari BST. Mengapa perlu bersusah-susah membuat hal sederhana dari suatu BST?

Jawabannya ada pada fitur utama BST, yaitu insert/delete yang dinamis. BST dapat digunakan ketika terdapat operasi insert/delete elemen, yang mengakibatkan elemen-elemen sesudahnya bergeser posisi. Sebenarnya segment tree bisa saja melayani query semacam itu, tapi dengan seluruh posisi yang mungkin dimasukkan sudah diketahui, lalu query-query dijawab secara offline. Untuk kasus yang mana query perlu dijawab sebelum membaca query berikutnya (interaktif atau query berikutnya perlu di-decode dengan jawaban query saat ini), BST-lah yang dapat diandalkan.

Sebagai contoh, Anda dapat mengerjakan soal SPOJ QMAX3VN. Saya akan menulis pembahasan berikut kodenya pada lain kesempatan, berhubung tulisan ini sudah panjang.


Penutup

Mampu menggunakan BST untuk keperluan lainnya memberikan pemahaman lebih dalam tentang BST. Siapa tahu dengan mengetahui sifat-sifat BST di atas, Anda menjadi terpikir kegunaan dan sifat lain dari BST.

Pengetahuan ini mungkin berguna bagi kalian yang akan menghadapi ICPC regional, misalnya di daerah-daerah Asia Timur. Semoga membekali kemampuan kalian!

3 comments :

  1. Kak wilgoz, is it possible to find 2d max sum in less than o(n^3) ?

    ReplyDelete
    Replies
    1. hmm setahu saya O(N^3) sudah cara paling cepat. Saya tidak bisa buktikan apakah mungkin ada cara yang lebih cepat dari O(N^3)

      Delete
    2. Kak kalo ada waktu jelasin tentang range tree . Terimakasih sebelumnya :)

      Delete