Apa struktur data yang optimal untuk pohon peta.

Saya mencari struktur data, yang pada dasarnya adalah pohon peta, di mana peta di setiap node berisi beberapa elemen baru, serta elemen-elemen di peta node induknya. Dengan peta di sini yang saya maksud adalah peta pemrograman dengan kunci dan nilai, seperti peta di STL atau dict dengan python.

Misalnya, mungkin ada simpul root:

root = {'car':1, 'boat':2}

dan 2 anak, masing-masing menambahkan elemen ke peta induk

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

Saya ingin ini menjadi ruang seefisien mungkin, yaitu saya tidak ingin menyimpan salinan lengkap dari peta yang dihasilkan pada setiap node, tetapi idealnya pencarian masih O (log N), N menjadi jumlah total elemen pada simpul, bukan seluruh pohon.

Saya berpikir mungkin ada fungsi hash cerdas yang mungkin saya gunakan untuk ini, tetapi tidak bisa menghasilkan apa-apa.

Pendekatan naif akan menyimpan entri yang baru ditambahkan di peta di setiap node dan kemudian naik pohon jika tidak ada yang ditemukan. Saya tidak suka ini karena itu tergantung pada kedalaman pohon.

ds.data-structures tree hash-function phreeza
sumber

jadi setiap node mewakili peta yang memurnikan peta yang disimpan di induk?

Suresh Venkat

juga, maksud Anda memetakan dalam arti matematika atau kartografis?

Suresh Venkat

Maksud saya peta dalam arti matematika / CS. Seperti peta di STL misalnya.

phreeza

@ Suresh: Tampaknya itu bukan penyempurnaan. Jika saya menjawab pertanyaan dengan benar, simpul anak menambahkan elemen baru ke peta simpul induknya.

Jukka Suomela

dan untuk menjawab pertanyaan pertama, setiap node memurnikan peta dalam arti bahwa lebih banyak pasangan kunci / nilai ditambahkan.

phreeza

Jawaban:

Anda belum mengatakan pertanyaan apa, tapi saya akan menganggap query () mengambil simpul dan kunci dan menginginkan nilai yang terkait (atau nol jika tidak ada nilai seperti itu). Dalam hal ini, saya pikir secara umum Anda tidak bisa melakukan lebih baik daripada menyimpan peta terpisah di setiap node. Pertimbangkan misalnya pohon ulat di mana setiap simpul jalur memiliki satu simpul yang terhubung dengannya yang bercabang dua (total simpul 2n). Rooting di salah satu ujung jalan. Sekarang anggaplah ukuran alam semesta untuk kunci adalah m. Untuk setiap simpul v yang bercabang dan masing-masing kunci m yang mungkin, kunci tersebut dapat ada atau tidak ada di v, dan keduanya akan sesuai dengan batasan subtree Anda. Jadi, ada kemungkinan untuk apakah setiap kunci ada di setiap simpul garpu, jadi Anda membutuhkan mn bit ruang hanya untuk menyimpan informasi yang diperlukan. $2^{mn}$

Jelani Nelson
sumber

Tetapi contoh ini tidak menunjukkan bahwa Anda harus menyimpan informasi yang berlebihan (yaitu, bahwa Anda perlu menduplikasi entri simpul root pada setiap anak juga)!

Jukka Suomela

Saya bingung. Dalam pohon kedalaman dengan node jelas bahwa Anda tidak dapat menyimpan binding di ruang . Apakah contoh Anda menunjukkan sesuatu yang lebih?

1

$1$

n

$n$

m

$m$

o (m)

$o(m)$

Radu GRIGore

Pertama-tama, saya pikir apa yang Anda maksud dengan "peta" adalah "kamus" dalam istilah TCS. Kedua, saya tidak mengerti ungkapan "idealnya pencarian akan tetap ", karena dalam kamus pencarian membutuhkan O (1) waktu dengan berbagai tabel hash. Ketiga, Anda belum menyatakan apakah masalahnya statis atau dinamis; Saya mengasumsikan statis. $O(\log N)$

Kompleksitas optimal untuk masalah ini adalah pencarian sebelumnya), misalnya menggunakan van Emde Boas. Ini optimal jika ukuran kata Anda adalah ; lihat http://people.csail.mit.edu/mip/papers/pred/pred.pdf untuk batas pendahulunya yang optimal. $\Theta($ $O(\lg\lg N)$ $\Theta(\lg n)$

Cara yang tepat untuk menyerang masalah adalah membangun satu tabel hash global dan menangani hierarki secara terpisah untuk setiap kunci dalam tabel. Untuk satu kunci , kita tahu titik-titik di mana ia muncul. Pertimbangkan lintasan pohon secara berurutan. Node tempat muncul menentukan interval dalam urutan ini. Untuk menentukan apakah ada dalam tabel hash dari beberapa node , Anda harus bertanya apakah menusuk setiap segmen seperti yang didefinisikan di atas. Ini mudah dilakukan oleh pencarian sebelumnya, di mana kami membuat tabel pendahulunya untuk semua titik akhir interval. $x$ $x$ $x$ $v$ $v$

Untuk batas bawah, perhatikan bahwa bahkan satu pertanyaan penikaman sama sulitnya dengan pendahulunya (lihat pengurangan dari pencarian pendahulunya yang berwarna). Karena referensi makalah di atas menunjukkan perilaku penjumlahan langsung yang optimal untuk pencarian pendahulu, itu berarti algoritma yang dijelaskan di atas optimal untuk setiap rasio antara jumlah node dan jumlah total kunci.

Mihai
sumber