Mempertahankan pemesanan yang efisien di mana Anda dapat memasukkan elemen "di antara" dua elemen lainnya dalam pemesanan?

Bayangkan saya memiliki pemesanan pada banyak elemen seperti:

Di mana panah$X \leftarrow Y$ berarti . Ini juga transitif: .$X < Y$$\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$

Agar dapat menjawab pertanyaan dengan efisien seperti , diperlukan semacam pelabelan atau struktur data. Misalnya, Anda bisa nomor node dari kiri ke kanan, dan dengan demikian Anda dapat melakukan bilangan bulat perbandingan untuk menjawab pertanyaan: . Akan terlihat seperti ini:$A \stackrel {?}{<} D$$A \stackrel {?}{<} D \implies 1 < 4 \implies T$

Di mana nomornya adalah pemesanan, dan surat itu hanya nama.

Tetapi bagaimana jika Anda perlu memasukkan elemen "di antara" dua elemen lain dalam pemesanan, seperti:

Bagaimana Anda bisa mempertahankan pemesanan seperti itu? Dengan penomoran sederhana, Anda mengalami masalah bahwa tidak ada bilangan bulat "di antara" untuk digunakan.$2,3$

Ini dikenal sebagai masalah "pemeliharaan pesanan" . Ada solusi yang relatif sederhana menggunakan waktu diamortisasi untuk kueri dan menyisipkan. Sekarang, dengan "relatif sederhana", maksud saya Anda harus memahami beberapa blok bangunan, tetapi begitu Anda mendapatkannya, sisanya tidak sulit dilihat.$O(1)$

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

Ide dasarnya adalah struktur data dua tingkat. Level teratas seperti solusi pohon AVL oleh Realz Slaw, tetapi

• Node diberi label secara langsung dengan bit string panjang dengan urutan yang cocok dengan urutannya di pohon. Karena itu, perbandingan membutuhkan waktu yang konstan$O(\lg n)$

• Pohon dengan rotasi yang lebih sedikit daripada pohon AVL digunakan, seperti pohon kambing hitam atau pohon yang seimbang berat badannya, sehingga relabelling lebih jarang terjadi.

Tingkat bawah adalah daun pohon. Level itu menggunakan panjang label yang sama, , tetapi hanya memegang item di setiap daun dalam daftar sederhana yang ditautkan. Ini memberi Anda bit ekstra yang cukup untuk memberi label ulang secara agresif.$O(\lg n)$$O(\lg n)$

Daun menjadi terlalu besar atau terlalu kecil setiap menyisipkan, mendorong perubahan di tingkat atas, yang membutuhkan waktu diamortisasi ( waktu kasus terburuk). Amortisasi, ini hanya .$O(\lg n)$$O(\lg n)$$\Omega(n)$$O(1)$

Ada struktur yang jauh lebih kompleks untuk melakukan pembaruan dalam kasus terburuk.$O(1)$

Alih-alih penomoran sederhana, Anda dapat menyebarkan angka-angka pada rentang yang besar (ukuran konstan), seperti integer minimum dan maksimum integer CPU. Kemudian Anda dapat terus menempatkan angka "di antara" dengan rata-rata dua angka di sekitarnya. Jika angka menjadi terlalu ramai (misalnya Anda berakhir dengan dua bilangan bulat yang berdekatan dan tidak ada angka di antaranya), Anda dapat melakukan satu kali penomoran ulang seluruh pemesanan, mendistribusikan ulang angka-angka secara merata di seluruh rentang.

Tentu saja, Anda dapat mengalami batasan bahwa semua angka dalam kisaran konstanta besar digunakan. Pertama, ini biasanya bukan masalah, karena ukuran bilangan bulat pada mesin cukup besar sehingga jika Anda memiliki lebih banyak elemen kemungkinan besar tidak akan masuk ke dalam memori. Tetapi jika itu adalah masalah, Anda bisa memberi nomor baru pada mereka dengan rentang integer yang lebih besar.

Jika urutan input tidak patologis, metode ini dapat mengamortisasi angka baru.

Menjawab pertanyaan

Perbandingan bilangan bulat sederhana dapat menjawab pertanyaan $\left(X \stackrel{?}{<}Y\right)$.

Waktu permintaan akan sangat cepat ( $\mathcal{O}\left(1\right)$) jika menggunakan bilangan bulat mesin, karena ini adalah perbandingan bilangan bulat sederhana. Menggunakan rentang yang lebih besar akan membutuhkan bilangan bulat yang lebih besar, dan perbandingan akan diperlukan$\mathcal{O}\left(\log{|integer|}\right)$.

Insersi

Pertama, Anda akan mempertahankan daftar pemesanan yang tertaut, yang ditunjukkan dalam pertanyaan. Penyisipan di sini, diberikan node untuk menempatkan elemen baru di antaranya, akan$\mathcal{O}\left(1\right)$.

Memberi label elemen baru biasanya cepat $\mathcal{O}\left(1\right)$karena Anda akan menghitung numeber baru dengan mudah dengan rata-rata angka di sekitarnya. Terkadang Anda mungkin kehabisan angka "di antara", yang akan memicu$\mathcal{O}\left(n\right)$ prosedur penomoran ulang waktu.

Menghindari pemberian nomor baru

Anda bisa menggunakan float sebagai ganti bilangan bulat, jadi ketika Anda mendapatkan dua bilangan bulat "berdekatan", mereka bisa dirata-ratakan. Dengan demikian Anda dapat menghindari pemberian nomor baru ketika dihadapkan dengan dua pelampung integer: cukup bagi mereka menjadi dua. Namun, pada akhirnya tipe floating point akan kehabisan keakuratan, dan dua float "adacent" tidak akan dapat dirata-rata (rata-rata bilangan di sekitarnya mungkin akan sama dengan salah satu bilangan di sekitarnya).

Anda juga dapat menggunakan bilangan bulat "desimal place", tempat Anda mempertahankan dua bilangan bulat untuk suatu elemen; satu untuk angka dan satu untuk desimal. Dengan cara ini, Anda dapat menghindari pemberian nomor baru. Namun, bilangan bulat desimal pada akhirnya akan meluap.

Menggunakan daftar bilangan bulat atau bit untuk setiap label dapat sepenuhnya menghindari pemberian nomor baru; ini pada dasarnya setara dengan menggunakan angka desimal dengan panjang tak terbatas. Perbandingan akan dilakukan secara leksikografis, dan waktu perbandingan akan meningkat hingga panjang daftar yang terlibat. Namun, ini bisa membuat label tidak seimbang; beberapa label mungkin hanya membutuhkan satu bilangan bulat (tidak ada desimal), yang lain mungkin memiliki daftar panjang (desimal panjang). Ini adalah masalah, dan penomoran ulang dapat membantu di sini juga, dengan mendistribusikan kembali penomoran (di sini daftar angka) secara merata pada rentang yang dipilih (berkisar di sini mungkin berarti panjang daftar) sehingga setelah dinomori ulang, daftar semua panjangnya sama .

Metode ini sebenarnya digunakan dalam algoritma ini ( implementasi , struktur data yang relevan ); dalam proses algoritme, urutan sewenang-wenang harus dipertahankan dan penulis menggunakan bilangan bulat dan memberi nomor baru untuk mencapai hal ini.

Mencoba untuk tetap pada angka membuat ruang kunci Anda agak terbatas. Orang bisa menggunakan string panjang variabel sebagai gantinya, menggunakan logika perbandingan "a" <"ab" <"b". Masih ada dua masalah yang masih harus dipecahkan A. Kunci bisa menjadi panjang sewenang-wenang B. Perbandingan kunci panjang bisa menjadi mahal

Anda dapat mempertahankan pohon AVL tanpa kunci atau sejenisnya.

Ini akan bekerja sebagai berikut: Pohon mempertahankan pemesanan pada node seperti halnya pohon AVL biasanya, tetapi alih-alih menentukan kunci di mana simpul "harus" terletak, tidak ada kunci, dan Anda harus secara eksplisit memasukkan node "setelah "node lain (atau dengan kata lain" di antara "dua node), di mana" setelah "berarti itu datang setelah itu dalam urutan traversal pohon. Dengan demikian pohon akan mempertahankan pemesanan untuk Anda secara alami, dan itu juga akan seimbang, karena AVL dibangun dalam rotasi. Ini akan menjaga semuanya terdistribusi secara otomatis.

Insersi

Selain penyisipan teratur ke dalam daftar, seperti yang ditunjukkan dalam pertanyaan, Anda akan mempertahankan pohon AVL yang terpisah. Penyisipan ke daftar itu sendiri adalah$\mathcal{O}\left(1\right)$, karena Anda memiliki simpul "sebelum" dan "setelah".

Waktu penyisipan ke pohon adalah $\mathcal{O}\left(\log {n}\right)$, sama seperti penyisipan ke pohon AVL. Penyisipan melibatkan memiliki referensi ke simpul yang ingin Anda masukkan setelahnya, dan Anda cukup memasukkan simpul baru ke kiri simpul paling kiri dari anak kanan; lokasi ini "berikutnya" dalam urutan pohon (berikutnya dalam urutan melintang). Kemudian lakukan rotasi AVL khas untuk menyeimbangkan kembali pohon. Anda dapat melakukan operasi serupa untuk "masukkan sebelum"; ini berguna ketika Anda perlu memasukkan sesuatu ke awal daftar, dan tidak ada simpul "sebelum".

Menjawab pertanyaan

Untuk menjawab pertanyaan dari $\left(X \stackrel{?}{<}Y\right)$, Anda cukup menemukan semua leluhur $X$ dan $Y$di pohon, dan Anda menganalisis lokasi di mana di pohon leluhur berbeda; yang menyimpang ke "kiri" adalah yang lebih rendah dari keduanya.

Prosedur ini memakan waktu $\mathcal{O}\left(\log{n}\right)$waktu memanjat pohon ke akar dan mendapatkan daftar leluhur. Meskipun benar bahwa ini tampaknya lebih lambat daripada perbandingan bilangan bulat, kenyataannya adalah, itu sama; hanya perbandingan integer pada CPU yang dibatasi oleh konstanta besar untuk membuatnya$\mathcal{O}\left(1\right)$; jika Anda melimpahi konstanta ini, Anda harus mempertahankan beberapa integer ($\mathcal{O}\left(\log{n}\right)$ bilangan bulat sebenarnya) dan melakukan hal yang sama $\mathcal{O}\left(\log{n}\right)$perbandingan. Sebagai alternatif, Anda dapat "mengikat" ketinggian pohon dengan jumlah konstan, dan "menipu" dengan cara yang sama dengan mesin dengan bilangan bulat: sekarang kueri akan tampak$\mathcal{O}\left(1\right)$.

Demonstrasi operasi penyisipan

Untuk menunjukkan, Anda dapat memasukkan beberapa elemen dengan urutannya dari daftar di pertanyaan:

Langkah 1

Dimulai dari $D$

Daftar:

Pohon:

Langkah 2

Memasukkan $C$, $\emptyset < C < D$.

Daftar:

Pohon:

Catatan, Anda secara eksplisit dimasukkan $C$ "sebelum" $D$, bukan karena huruf C sebelum D, tetapi karena $C < D$ dalam daftar.

Langkah 3

Memasukkan $A$, $\emptyset < A < C$.

Daftar:

Pohon:

Rotasi AVL:

Langkah 4

Memasukkan $B$, $A < B < C$.

Daftar:

Pohon:

Tidak perlu rotasi.

Langkah 5

Memasukkan $E$, $D < E < \emptyset$

Daftar:

Pohon:

Langkah 6

Memasukkan $F$, $B < F < C$

Kami hanya meluruskannya "setelah" $B$ di pohon, dalam hal ini hanya dengan melampirkannya $B$benar; jadi$F$ sekarang tepat setelah $B$ dalam traversal berurutan pohon.

Daftar:

Pohon:

Rotasi AVL:

Demonstrasi operasi perbandingan

$A \stackrel{?}{<} F$

ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

$D \stackrel{?}{<} F$

ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

$B \stackrel{?}{<} A$

ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

Sumber grafik

• gist.github.com/realazthat/9299877a83cba4720aec