Pertanyaan tentang jenis grafik khusus, yaitu yang terhubung dan bebas siklus.
Pohon indeks biner memiliki sangat sedikit atau relatif tidak memiliki literatur dibandingkan dengan struktur data lainnya. Satu-satunya tempat di mana itu diajarkan adalah tutorial topcoder . Meskipun tutorialnya lengkap dalam semua penjelasannya, saya tidak bisa mengerti intuisi di balik pohon...
Keduanya tampak sangat mirip dan memiliki struktur yang hampir identik. Apa bedanya? Apa kompleksitas waktu untuk operasi yang berbeda
Tampaknya di mana pun saya melihat, struktur data sedang dilaksanakan menggunakan pohon merah-hitam ( std::setdalam C ++, SortedDictionarydi C #, dll.) Baru saja membahas (a, b), pohon merah-hitam & AVL di kelas algoritme saya, inilah yang saya dapatkan (juga dari bertanya di sekitar profesor,...
Apa perbedaan antara algoritma spanning tree minimum dan algoritma jalur terpendek? Dalam kelas struktur data saya, kami membahas dua algoritma spanning tree minimum (Prim dan Kruskal) dan satu algoritma jalur terpendek (Dijkstra). Minimum spanning tree adalah pohon dalam grafik yang membentang...
Ada algoritma standar ini untuk menemukan jalur terpanjang di pohon-pohon yang tidak diarahkan menggunakan dua pencarian kedalaman-pertama: Mulai DFS dari simpul acak dan temukan simpul terjauh darinya; katakan itu .v ′vvvv′v′v' Sekarang mulai DFS dari untuk menemukan titik terjauh dari itu....
Mari kita asumsikan definisi pohon merah-hitam berikut: Ini adalah pohon pencarian biner. Setiap node berwarna merah atau hitam. Akar hitam. Dua node yang dihubungkan oleh sebuah edge tidak bisa berwarna merah pada saat bersamaan. Ini seharusnya definisi yang bagus untuk daun NIL, seperti pada...
Saya belajar tentang pohon radix (alias percobaan terkompresi) dan Patricia mencoba, tetapi saya menemukan informasi yang bertentangan tentang apakah mereka sebenarnya sama atau tidak. Pohon radix dapat diperoleh dari trie normal (tidak terkompresi) dengan menggabungkan node dengan orang tua mereka...
Secara intuitif, "pohon seimbang" harus pohon di mana sub-pohon kiri dan kanan di setiap node harus memiliki "kurang lebih sama" jumlah node. Tentu saja, ketika kita berbicara tentang pohon merah-hitam * (lihat definisi di akhir) yang seimbang, kita benar-benar berarti bahwa mereka adalah tinggi...
Saat menerapkan kamus ('Saya ingin mencari data pelanggan dengan ID pelanggan mereka'), struktur data yang digunakan adalah tabel hash dan pohon pencarian biner. Saya tahu misalnya bahwa perpustakaan C ++ STL mengimplementasikan kamus (mereka menyebutnya peta) menggunakan pohon pencarian biner...
Kami tahu post-order, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] dan pre-order pre L(x) => [x] pre N(x,l,r) => [x] ++ (pre l) ++ (pre r) dan resp traversal berurutan. sekuensialisasi. in L(x) => [x] in N(x,l,r) => (in l) ++ [x] ++ (in r) Orang dapat...
Tautan ini menyediakan algoritme untuk menemukan diameter pohon tak berarah menggunakan BFS / DFS . Meringkas: Jalankan BFS pada sembarang simpul dalam grafik, mengingat simpul yang Anda temukan terakhir. Jalankan BFS dari Anda mengingat simpul v yang ditemukan terakhir. d (u, v) adalah diameter...
(Saya seorang siswa dengan latar belakang matematika dan saya ingin tahu bagaimana cara menghitung jumlah jenis pohon biner tertentu.) Melihat halaman Wikipedia untuk Binary Trees , saya perhatikan pernyataan ini bahwa jumlah pohon biner yang berakar berukurannnn akan menjadi Angka Katalan ini...
Wikipedia serta sumber lain yang saya temukan daftar voidtipe C sebagai tipe unit sebagai lawan dari tipe kosong. Saya menemukan ini membingungkan karena menurut saya voidlebih cocok dengan definisi tipe kosong / bawah. Tidak ada nilai yang dihuni void, sejauh yang saya tahu. Suatu fungsi dengan...
Saya telah melihat dua definisi pohon biner seimbang, yang terlihat berbeda bagi saya. Pohon biner seimbang jika untuk setiap node itu berpendapat bahwa jumlah node dalam di subtree kiri dan jumlah node dalam di subtree kanan berbeda paling banyak 1. Pohon biner seimbang jika untuk setiap dua...
Saya telah menemukan beberapa alat pemrograman visual open source seperti Blockly dan teman-teman, dan proyek lain yang dihosting di Github, tetapi tidak dapat menemukan yang bekerja langsung dengan pohon sintaksis abstrak. Mengapa demikian? Saya bertanya karena begitu saya menemukan bahwa setiap...
Saya tidak begitu mengerti mengapa rotasi dalam struktur data splay tree memperhitungkan tidak hanya induk dari simpul penilaian, tetapi juga kakek-nenek (operasi zig-zag dan zig-zig). Mengapa yang berikut ini tidak berfungsi: Ketika kita memasukkan, misalnya, simpul baru ke pohon, kami memeriksa...
Saya mencoba beberapa kasus dan menemukan dua pohon spanning dari grafik sederhana memiliki beberapa tepi yang sama. Maksudku, aku tidak bisa menemukan contoh balasan sejauh ini. Tapi aku juga tidak bisa membuktikan atau membantahnya. Bagaimana cara membuktikan atau menyangkal dugaan...
Dalam pertanyaan sebelumnya , ada definisi pohon seimbang berat dan pertanyaan tentang pohon merah-hitam. Pertanyaan ini untuk menanyakan pertanyaan yang sama, tetapi untuk pohon AVL . Pertanyaannya adalah, mengingat definisi pohon seimbang seperti dalam pertanyaan lain,μμ\mu Apakah ada...
Diberikan grafik berbobot dan tidak terarah G: Kondisi mana yang harus benar sehingga ada beberapa pohon rentang minimum untuk G? Saya tahu bahwa MST itu unik ketika semua bobotnya berbeda, tetapi Anda tidak bisa membalikkan pernyataan ini. Jika ada tepi muliple dengan bobot yang sama dalam...
Jika grafik berbobot memiliki dua pohon rentang minimum yang berbeda dan , maka apakah benar bahwa untuk setiap tepi dalam , jumlah tepi dalam dengan jumlah tepi pada dengan bobot yang sama dengan (termasuk sendiri) sama dengan jumlah tepi dalam dengan bobot yang sama dengan ? Jika pernyataan itu...