Pohon merah dan hitam
Pohon merah dan hitam adalah pohon yang sering disebutkan dalam struktur data dan algoritma tetapi tidak dapat dijelaskan secara rinci. Mereka juga pohon yang sering ditanyakan dalam wawancara teknis. Namun, apakah itu materi dalam buku atau online, mereka biasanya lebih kaku dan sulit dipahami. Bisakah Anda memahami pohon merah dan hitam dengan cara yang lebih intuitif? Artikel ini akan menjelaskan operasi penyisipan dan penghapusan pohon merah dan hitam dengan cara grafis.
Mempelajari struktur pohon adalah proses progresif. Pohon yang biasanya kami hubungi adalah pohon biner. Secara sederhana, setiap simpul non-daun memiliki dan hanya dua anak, yang disebut anak kiri dan anak yang tepat. Ada jenis pohon khusus di pohon biner yang disebut pohon pencarian biner. Pohon pencarian biner adalah pohon yang dipesan. Untuk setiap simpul non-daun, nilai subtree kirinya lebih kecil dari itu, dan nilai subtree kanannya lebih besar dari itu. Langkah lebih lanjut dari pohon pencarian biner adalah pohon keseimbangan biner. Selain memastikan pesanan, pohon keseimbangan biner juga dapat menjaga perbedaan tinggi antara subtree kiri dan kanan dari masing -masing node dan tidak lebih dari 1. Pohon seimbang umum adalah pohon AVL, treaps, pohon merah dan hitam, peregangan pohon, dan sebagainya.
Pohon merah dan hitam adalah pohon pencarian biner, tetapi menambahkan bit penyimpanan untuk setiap node untuk mewakili warna node, yang bisa merah atau hitam. Dengan membatasi bagaimana setiap node menaungi jalan mana pun dari akar ke daun, pohon merah-hitam memastikan bahwa tidak ada jalan yang akan dua kali lebih lama dari jalur lainnya, sehingga mendekati keseimbangan.
Pohon merah dan hitam memuaskan 5 properti:
Perhatikan bahwa di pohon merah-hitam, arahkan anak dari simpul daun pohon biner tradisional ke nihil, dan panggil nil simpul daun di pohon merah-hitam. Node NIL berisi pointer ke node induk, yang mungkin menjadi alasan mengapa null perlu diubah menjadi nol.
1. Masukkan operasi
Pertama, masukkan simpul baru dengan cara memasukkan pohon pencarian biner (node baru yang dimasukkan semuanya ada di node daun), dan tarik berwarna merah. Kemudian gambar ulang warnanya atau putar untuk mempertahankan sifat -sifat pohon merah dan hitam. Penyesuaian dibagi menjadi tiga situasi berikut:
1 simpul baru n tidak memiliki node induk (mis., Terletak di root)
Cat simpul baru n sebagai hitam.
2 simpul induk p dari simpul baru n berwarna hitam
Tidak perlu menyesuaikan diri.
3 simpul induk p dari simpul baru n berwarna merah
Karena pohon merah dan hitam tidak mengizinkan dua node merah berturut -turut (properti 4), perlu disesuaikan. Menurut warna simpul paman N, itu dibagi menjadi dua situasi: (kami mengambil simpul induk N sebagai anak kiri sebagai contoh, dan p sebagai anak yang tepat sebagai situasi yang sama, jadi saya tidak akan menjelaskannya secara rinci)
3.1 Paman Node U dari simpul baru N berwarna merah. Node induk P dan paman simpul u dari simpul baru n dicat hitam, dan node kakek g dicat merah, sehingga dapat memastikan bahwa jumlah node hitam yang terkandung di jalur dari G ke setiap node nol konsisten dengan yang asli. Tetapi karena kita mengubah G menjadi merah, jika ayah G juga merah, itu dapat menyebabkan dua node merah berturut-turut (melanggar alam 4), jadi perlu untuk memeriksa ulang apakah G melanggar sifat pohon merah dan hitam.
3.2 Paman Node U dari simpul baru n berwarna hitam. Jika simpul baru n adalah anak kiri dari simpul induknya P: Gambarlah node induknya p sebagai hitam, gambar node kakeknya g sebagai merah, dan kemudian putar g kanan suatu kali.
Jika simpul n baru adalah anak yang tepat dari simpul induknya P: Lakukan rotasi kiri pada simpul induknya, masalahnya akan diubah menjadi situasi anak kiri.
2. Hapus operasi
Metode dalam "Pengantar Algoritma" dan Wikipedia adalah untuk menghapus simpul hitam D, "Tekan ke bawah" hitam D ke simpul anaknya C, yaitu, C memiliki lapisan hitam tambahan di samping warnanya sendiri, dan kemudian terus memindahkan ke dalam pound, nodi yang tidak ada di sepanjang pohon sampai menandatangani Node Red, dan mengubahnya ke Black ke node yang menanggapi NODS pada NODS NODSER RED NODE, dan mengubahnya ke Black untuk memastikan bahwa nomor Black di NODS TERAP sehingga jumlah node hitam di semua jalur dikurangi satu dan tetap sama. Selama gerakan ke atas, beberapa warna simpul mungkin perlu diputar dan dimodifikasi untuk memastikan bahwa jumlah node hitam di jalur tetap tidak berubah.
Pendekatan ini mungkin bermanfaat bagi implementasi kode (yang dapat digunakan dengan cara berulang), tetapi tidak nyaman untuk dipahami (secara pribadi percaya). Untuk tujuan memahami prioritas, saya membuat klasifikasi berikut berdasarkan apakah anak dari simpul yang dihapus adalah nil:
1 Kedua anak yang simpul D dihapus adalah nol
1.1 Jika simpul yang dihapus adalah merah, cukup ganti D dengan nihil.
1.2 simpul yang dihapus adalah hitam (mari kita ambil d sebagai contoh)
1.2.1 Kedua anak dari simpul B, yang saudara lelakinya D, dihapus, nil
D'S Brother Node B dicat sebagai simpul merah dan induk P dicat hitam.
Setengah merah dan setengah hitam pada gambar berarti bahwa simpul mungkin merah atau hitam. Jika P ternyata merah, jumlah node hitam di jalur setelah modifikasi sama seperti sebelum penghapusan d; Jika P ternyata hitam, maka menghapus D akan menghasilkan satu jumlah node hitam yang lebih sedikit di jalur daripada sebelum penghapusan, jadi Anda perlu terus memeriksa apakah perubahan jumlah node hitam di jalur yang melewati P mempengaruhi sifat -sifat pohon merah dan hitam.
1.2.2 Node Brother B dari simpul D memiliki anak yang bukan nil
Anak harus merah, jika tidak jumlah node hitam di jalur dari simpul induk D ke setiap node daun akan bervariasi (pelanggaran 5).
Jika anak ini adalah anak yang tepat, gambar anak yang tepat dari B sebagai hitam, gambar B sebagai warna asli dari simpul induknya, gambar P sebagai hitam, dan kemudian putar P dengan satu kiri.
Jika anak ini adalah anak kiri, gambar anak kiri B sebagai hitam, B sebagai merah, dan kemudian putar B tepat sekali, masalahnya akan diubah menjadi situasi anak yang tepat.
1.2.3 Kedua anak dari simpul B, yang telah dihapus, bukan nil
Jika B berwarna merah, maka dua anak B harus berkulit hitam. Gambar B sebagai anak kiri hitam, B sebagai merah, dan kemudian lakukan rotasi kiri P.
Jika B berwarna hitam, maka dua anak B harus merah. Gambar node induk B sebagai hitam, anak kanan B sebagai hitam, warna asli B sebagai simpul induknya P, dan kemudian putar P dengan satu kiri.
2 Kedua anak yang simpul D dihapus bukan nil
Menurut pohon pencarian biner untuk menghapus node, temukan simpul penerus D, pertukaran isi D dan S (warnanya tetap tidak berubah), dan simpul yang dihapus menjadi S. jika S memiliki simpul yang bukan nol, kemudian terus menggantikan S dengan simpul Suscersor S sampai kedua anak dari simpul yang dihapus adalah nil. Masalahnya berubah menjadi situasi di mana kedua anak dari simpul yang dihapus adalah nol.
3 simpul yang dihapus D memiliki anak bukan nol
Anak ini c harus berupa simpul merah, jika tidak jumlah node hitam di jalur dari D ke setiap node nil akan berbeda (pelanggaran 5).
Isi D dan C dipertukarkan (warnanya tetap sama), simpul yang dihapus menjadi C, dan masalahnya berubah menjadi situasi di mana kedua anak dari simpul yang dihapus adalah nol.
Traversal pohon biner
Ada tiga jenis traversal di pohon biner: traversal preorder, traversal tengah dan postorder traversal. Ada dua jenis implementasi traversal: rekursi dan iterasi. Dalam artikel ini, kita akan membahas cara menggunakan kode yang lebih elegan untuk mengimplementasikan traversal pohon biner.
Pertama, saya akan mendefinisikan simpul pohon biner:
kelas publik treenode {int val; Treeenode tersisa; Treeenode benar; Treeenode publik (int x) {val = x; }}
1. Preorder Traversal
Sederhananya, traversal pre-order adalah untuk terlebih dahulu mengakses node induk, kemudian mengakses anak kiri, dan akhirnya mengakses anak yang tepat, yaitu, untuk melintasi urutan orang tua, kiri, dan kanan.
Implementasi rekursif sangat sederhana, kodenya adalah sebagai berikut:
solusi kelas publik {daftar <integer> result = ArrayList baru <Integer> (); Daftar Publik <Integer> PreorDtraversal (TreeNode root) {dfs (root); hasil pengembalian; } private void DFS (root TreeNode) {if (root == null) {return; } result.add (root.val); DFS (root.Left); dfs (root.right); }} Implementasi berulang membutuhkan tumpukan untuk menyimpan simpul yang tepat yang tidak diakses. Kodenya adalah sebagai berikut:
solusi kelas publik {Daftar publik <Integer> preordertraversal (TreeNode root) {list <integer> result = ArrayList baru <Integer> (); if (root == null) {hasil pengembalian; } Stack <treenode> stack = stack baru <treeNode> (); stack.push (root); while (! stack.isempty ()) {treenode curr = stack.pop (); result.add (Curr.Val); if (Curr.Right! = null) {stack.push (Curr.Right); } if (Curr.Left! = NULL) {stack.push (Curr.Left); }} hasil pengembalian; }}
2. Inorder Traversal
Sederhananya, traversal pesanan tengah adalah untuk mengakses anak kiri terlebih dahulu, kemudian mengakses simpul induk, dan akhirnya mengakses anak yang tepat, yaitu traversal dalam urutan kiri, orang tua, dan kanan.
Kode rekursif juga lebih mudah, seperti yang ditunjukkan di bawah ini:
solusi kelas publik {Daftar publik <Integer> inOrderTraversal (TreeNode root) {list <integer> result = ArrayList baru <Integer> (); berulang (root, hasil); hasil pengembalian; } private void recurse (root treenode, daftar <integer> hasil) {if (root == null) return; Recurse (root.Left, hasil); result.add (root.val); berulang (root.right, hasil); }} Metode penulisan di atas berbeda dari kode rekursif traversal preorder. Kami menggunakan variabel anggota untuk menyimpan hasil traversal dalam traversal preorder, dan di sini kami menggunakan parameter metode untuk menyimpan hasil traversal. Kedua metode penulisan baik -baik saja, gunakan apa pun yang Anda suka.
Implementasi berulang dari traversal orde menengah tidak sesederhana traversal preorder. Meskipun juga membutuhkan tumpukan, kondisi untuk penghentian berulang berbeda. Bayangkan untuk pohon biner, simpul yang kita akses pertama adalah simpul paling kiri. Kita tentu saja dapat mencapai simpul paling kiri melalui loop sementara, tetapi ketika kita kembali, bagaimana kita tahu jika anak kiri dari sebuah simpul telah diakses? Kami menggunakan variabel Curr untuk merekam node yang saat ini diakses. Ketika kita telah mengakses simpul yang tepat dari subtree, kita harus kembali ke simpul induk subtree. Pada saat ini, Curr adalah nol, sehingga kita dapat menggunakan ini untuk membedakan apakah subtree kiri sebuah node telah diakses. Kodenya adalah sebagai berikut:
solusi kelas publik {Daftar publik <Integer> inOrderTraversal (TreeNode root) {list <integer> result = ArrayList baru <Integer> (); Stack <treenode> stack = stack baru <treeNode> (); Treeenode Curr = root; while (Curr! = null ||! stack.isempty ()) {while (Curr! = null) {stack.push (Curr); Curr = Curr.Left; } Curr = stack.pop (); result.add (Curr.Val); Curr = Curr.Right; } hasil pengembalian; }}
3. Pos -Order Traversal
Sederhananya, traversal pasca-orde adalah untuk pertama-tama mengakses anak kiri, mengakses anak yang tepat, dan akhirnya mengakses simpul induk, yaitu traversal dalam urutan kiri, kanan, dan orang tua.
Dengan meniru traversal urutan tengah, Anda dapat dengan mudah menulis implementasi rekursif dari traversal pasca-orde:
solusi kelas publik {Daftar publik <Integer> posterDerTraversal (TreeNode root) {list <integer> result = ArrayList baru <Integer> (); berulang (root, hasil); hasil pengembalian; } private void recurse (root treenode, daftar <integer> hasil) {if (root == null) return; Recurse (root.Left, hasil); berulang (root.right, hasil); result.add (root.val); }} Iterasi traversal pasca-orde juga membutuhkan identifikasi untuk membedakan apakah anak-anak kiri dan kanan dari suatu node telah diakses. Jika tidak, anak -anak kiri dan kanan akan diakses secara bergantian. Jika telah diakses, node akan diakses. Untuk tujuan ini, kami menggunakan variabel pra untuk mewakili simpul yang kami kunjungi. Jika simpul yang kami kunjungi adalah anak kiri atau kanan dari simpul saat ini, itu berarti bahwa anak -anak kiri dan kanan dari simpul saat ini telah diakses, dan kemudian kami dapat mengakses node. Kalau tidak, kita perlu memasuki anak -anak kiri dan kanan untuk mengaksesnya secara bergantian. Kodenya adalah sebagai berikut:
solusi kelas publik {Daftar publik <Integer> posterDerTraversal (TreeNode root) {list <integer> result = new LinkedList <Integer> (); Stack <treenode> stack = stack baru <treeNode> (); if (root! = null) stack.push (root); Treenode pre = root; while (! stack.isempty ()) {treenode arus = stack.peek (); if (Curr.Left == Pre || Curr.Right == Pre || (Curr.Left == null && Curr.Right == null)) {result.add (Curr.val); stack.pop (); Pre = Curr; } else {if (curr.right! = null) stack.push (Curr.Right); if (Curr.Left! = null) stack.push (Curr.Left); }} hasil pengembalian; }} Ada implementasi lain yang relatif sederhana dari iterasi traversal pasca-orde. Kita tahu bahwa urutan traversal pre-order adalah orang tua, kiri, dan kanan, sedangkan urutan traversal pasca-orde kiri, kanan, dan induk. Jadi jika kita sedikit memodifikasi traversal pre-order dan mengubahnya menjadi urutan induk, kanan, dan kiri, maka itu hanya kebalikan dari urutan traversal pasca-orde. Setelah mengaksesnya dalam urutan ini, kita dapat membalikkan hasil akses pada akhirnya. Implementasi traversal pre-order yang berulang relatif mudah. Menurut metode penulisan di atas, kami dapat mengimplementasikannya sebagai berikut:
solusi kelas publik {Daftar publik <Integer> posterDerTraversal (TreeNode root) {list <integer> result = new LinkedList <Integer> (); Stack <treenode> stack = stack baru <treeNode> (); if (root! = null) stack.push (root); while (! stack.isempty ()) {treenode curr = stack.pop (); result.add (Curr.Val); if (Curr.Left! = null) stack.push (Curr.Left); if (Curr.Right! = null) stack.push (Curr.Right); } Collections.reverse (hasil); hasil pengembalian; }}
4. Ringkasan
Implementasi rekursif dari ketiga traversal itu mudah. Yang terbaik adalah menulis implementasi iterasi dari preorder traversal, dan hanya satu tumpukan yang diperlukan; Traversal orde tengah adalah yang paling sulit. Selain menentukan apakah tumpukan kosong, kondisi loop juga perlu menentukan apakah simpul saat ini kosong untuk menunjukkan apakah subtree kiri telah dilalui; Jika iterasi traversal berikutnya dikonversi menjadi iterasi traversal preorder, itu jauh lebih mudah. Kalau tidak, juga perlu untuk merekam node akses sebelumnya untuk menunjukkan apakah subtree kiri dan kanan dari node saat ini telah diakses.