Get best of the week

Pohon merah-hitam dalam javascript

gambar

Hai Habr! Baru-baru ini mempelajari pohon merah-hitam. Saya mencoba memvisualisasikan detail pengoperasian algoritma penyisipan dan penghapusan pada d3.js. Saya harap hasilnya akan membantu menghemat waktu bagi mereka yang mempelajari algoritma dalam javascript. Anda bisa melihatnya di sini . Kode sumber implementasi yang saya andalkan di sini . Di bawah detail pendek kucing.

Cari solusi yang ada


Tujuan utama dari gagasan ini adalah untuk memahami implementasi algoritma dan memvisualisasikannya. Langkah pertama adalah mencari implementasi dengan penjelasan lengkap dan kode js. Dalam proses pencarian, sedih bahwa penulis kadang-kadang belum menyelesaikan sumbernya, misalnya, ada algoritma penyisipan, tetapi tidak ada penghapusan. Atau mereka melakukan visualisasi seperti ini , tetapi mereka tidak memberikan tautan ke sumbernya. Lalu aku menemukan ini artikel yang sangat baik. Tapi setidaknya membunuh, saya masih tidak bisa mengerti mengapa penulis memasukkan kode dengan gambar dan tidak memberikan tautan ke kode sumber atas permintaan dalam komentar. Ada juga paket npm red-black-tree , seluruh kode sumbernya adalah: 'sedang berlangsung ...' di readme. Ditemukan juga implementasi yang populer pohon merah-hitam di js, di mana banyak paket dan jutaan unduhan per minggu tergantung, tetapi kode ada lima tahun.

Prioritas dan spesifikasi tugas


Otak Porakinin, saya memutuskan bahwa keterbacaan dan kelengkapan kode untuk tujuan pendidikan adalah prioritas, jadi saya mengambil sebagai dasar artikel yang disebutkan di awal, dan bukan paket npm. Implementasinya ternyata lebih nyaman dan visual dalam hal membaca kode. Dalam artikel tersebut, penulis mulai dengan pohon biner, kemudian meluas menjadi merah-hitam. Untuk visualisasi, tampaknya cukup logis untuk mewarisi dari pohon merah-hitam dan membuat pohon animasi. Oleh karena itu, setelah mengetik ulang kode dan memastikan itu berfungsi, saya mulai menggambar pohon animasi. D3.js. datang untuk menyelamatkan. Ada transisi indah yang memungkinkan Anda untuk memindahkan elemen ke posisi yang tepat dan dengan lancar mengubahnya menjadi keadaan yang sesuai, saat algoritma bekerja.

Arti pohon merah-hitam


Saya berpikir lama, seolah-olah dengan cara yang sederhana, untuk menjelaskan apa itu. Mungkin, semua sama, Anda perlu membaca teori dari berbagai sumber. Seperti kata pepatah: "Anda tidak akan membuang kata-kata dari sebuah lagu." Tetapi kesimpulan ringkasan sederhana dapat dirumuskan secara singkat. Intinya adalah bahwa ada beberapa kasus ketika memasukkan dan menghapus elemen, tergantung pada "kakek" mana, "ayah", "paman", "anak-anak", "saudara" mengecat dan bergeser (berbelok) ke sisi di mana ada lebih sedikit elemen . Akibatnya, tidak pernah terjadi bahwa jalur dari simpul terjauh ke simpul akar terlalu panjang, sehingga pencarian elemen yang diinginkan dalam struktur seperti itu sangat cepat. Nah, ini diimbangi oleh kompleksitas penyisipan dan penghapusan.

More articles:


All Articles