Apakah boleh untuk tidak sepenuhnya memahami RB Trees? [Tutup]

Jadi saya baru belajar pohon merah-hitam di Cormen dan wow! Biasanya saya suka memahami semua algoritma dan struktur data hingga saya bisa membangunnya kembali dari awal tanpa harus menyontek melihat kode semu. Saya sangat suka algoritma jadi saya senang belajar bagaimana mereka bekerja dan saya biasanya pergi baris demi baris dan mencoba beberapa kasus dengan melihat kode dan memeriksa apakah yang terjadi adalah apa yang saya pahami yang seharusnya terjadi.

Hanya memahami apa yang terjadi, saya BANYAK waktu untuk pohon RB. Bahkan dengan penjelasan buku itu, saya masih kesulitan memahami kode itu. Belum lagi saya tidak mengerti bagaimana / mengapa rotasi bekerja. Saya tidak menemukan itu intuitif sama sekali. Maksud saya, tiga (enam sebenarnya) kasus berbeda untuk dimasukkan dan kemudian 4 kasus untuk dihapus? Apakah mungkin untuk memahami hal ini? Tidak mungkin bagi saya untuk membangun kembali kode ini tanpa curang. Sampai pohon biner saya dapat mengimplementasikan hal-hal itu dari kepala saya, dengan beberapa penyesuaian akan selalu berhasil, tetapi pohon RB saya bahkan tidak akan mencoba. Maksudku, bahkan guru kadang-kadang bingung, jadi kurasa itu tidak mudah, tetapi pada saat yang sama, tidakkah kita harus memahami semua yang terjadi atau setidaknya mengapa? Buku tidak Saya tidak benar-benar menjelaskan bagaimana seseorang muncul dengan gagasan rotasi. Bagaimana seseorang memperhatikan bahwa dengan 2 rotasi Anda bisa menyelesaikan masalah penyisipan? Itu luar biasa!

Pertanyaan saya adalah, apakah saya benar-benar harus 100% memahami pohon RB? Saya merasa melewatkan hal-hal buruk tanpa sepenuhnya memahaminya. Terima kasih sebelumnya, teman-teman! (PS: tidak ada tag untuk RB-tree, sebenarnya bahkan tidak untuk tree, hanya binary-tree, jadi saya hanya menempatkan algoritma)

Anda tampaknya menyamakan gagasan "memahami" dengan "bisa menulis kode tanpa melihat buku." Ini adalah dua hal yang berbeda. Jika Anda dapat melihat bagaimana memutar simpul pohon mengatur ulang pohon untuk menjaga keseimbangan, maka Anda memahaminya. Mampu untuk segera mengingat semua kasus yang berlaku rotasi bukan itu intinya.

Saya sendiri, saya mungkin bisa mengetahui rotasi jika saya punya pena / kertas / beberapa jam untuk bermain dengannya. Tapi tentu saja saya tidak bisa menuliskannya tanpa pikir panjang. Jika saya benar-benar harus menulis algoritma seperti itu, saya akan mencarinya untuk memastikan saya mendapatkan semua detail dengan benar. Tentu saja, dalam hampir semua situasi saya akan menggunakan kode yang sudah ditulis.

Di mana semua ini mulai digunakan adalah ketika Anda menemukan situasi yang tidak cocok dengan salah satu algoritma. Anda tidak perlu menulis implementasi pohon Anda sendiri. Tetapi Anda dapat menemukan diri Anda, katakanlah, perlu meratakan ahli waris dari daftar yang memiliki hubungan ganda. Dalam hal itu, setelah memahami ide dasar di balik rotasi bisa sangat membantu.

Jika Anda benar-benar fasih dengan pemrograman fungsional, Anda mungkin menemukan pendekatan ini lebih baik bagi mereka (Okasaki 1999):

http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf

Jika tidak, setidaknya ingat dari kalimat pembuka:

Semua orang belajar tentang pohon pencarian biner seimbang dalam kelas ilmu komputer pengantar mereka, tetapi bahkan orang-orang yang takut akan hal itu benar-benar mengimplementasikan binatang buas semacam itu.

Anda tidak perlu memahami rotasi secara detail. Anda harus memahami hubungan antara pohon RB dan pohon 2-3-4 (lihat Sedgewick). Semua rotasi gila itu jauh lebih masuk akal ketika Anda menganggapnya sebagai pohon 2-3-4. Jika profesor Anda belum mengajarkan pohon RB sebagai detail implementasi untuk 2-3-4 pohon, Anda mungkin harus membaca sesuatu di 2-3-4 pohon. (Perawatan Sedgewick cukup bagus; Wikipedia tidak memilikinya.)

Secara lebih umum, memahami detail implementasi mengapa suatu algoritma berfungsi kadang-kadang hanya berguna. Memahami logika mengapa algoritma bekerja hampir selalu bermanfaat. Mampu membuat sendiri algoritma biasanya tidak diperlukan, meskipun semakin banyak algoritma yang Anda pahami, semakin besar peluang yang Anda miliki.

Jika Anda membutuhkan "RB Trees By Heart" untuk ujian Anda minggu depan, Anda harus menggigit peluru dan mempelajarinya. Dalam hal ini, Anda harus mempertimbangkan kembali metode pembelajaran Anda. Mungkin mencoba menjelaskan RB Trees ke teman sekelas akan membantu Anda lebih dari satu malam penulisan kode kesepian.

Jika RB Trees adalah basis untuk kursus Anda berikutnya setelah liburan, lewati saja sekarang (tanpa perasaan buruk) dan berkonsentrasilah pada kursus semester ini. Tapi tetap awasi matamu untuk topik yang bisa mempersiapkanmu untuk upaya kedua di RB Trees.

Jika Anda benar-benar merasa bahwa Anda tidak akan pernah benar-benar membutuhkannya (lih. Komentar Anna Lear), cium mereka selamat tinggal tanpa penyesalan - tidak ada yang tahu lebih banyak bahwa setetes di lautan pengetahuan (terlalu buruk bahwa guru sering berpikir drop mereka adalah yang paling penting).

Kunci keberhasilan pemrograman adalah jangan pernah menyerah :

Hari ini pohon RB-nya besok akan menjadi sesuatu yang lain. Pelajaran yang lebih besar adalah tidak menyerah .

Bagi saya, itulah salah satu inti dari pemrograman, tidak menyerah ...

Saya menyarankan agar Anda terus mencoba , dan ketika Anda gagal LAKUKANNYA .

"Sampai Anda mendapatkan, sampai klik, sampai berjalan."

Karena begitu Anda mengatasi gunung, langit menjadi cerah. Pikiran Anda berubah pemahaman, Anda untuk sementara waktu (sampai gunung berikutnya) . Peningkatan sementara ini bernilai lebih dari semua uang di dunia ..

Cara terbaik untuk memahaminya adalah dengan mencobanya :

• Ada 3 atau 6 rotasi. Ambil selembar kertas dan tulis satu per satu.
• Setelah Anda mendapatkannya, pergi dan terapkan Red Black Tree. Tidak apa-apa jika Anda harus mencari beberapa hal.

Begitulah cara kami melakukannya di kampus. Dan untuk pemeriksaan kami harus menjelaskan bagaimana sebagian itu bekerja.