Pohon merah dan hitam adalah pohon pencarian seimbang biner. Setiap node memiliki bit penyimpanan untuk mewakili warna node, yang bisa merah atau hitam.
Pohon merah dan hitam memiliki sifat berikut:
(1) Setiap node berwarna merah atau hitam
(2) simpul root berwarna hitam
(3) Jika sebuah simpul berwarna merah, kedua putranya berwarna hitam
(4) Untuk setiap node, semua jalur dari simpul itu ke keturunannya berisi jumlah node hitam yang sama.
Melalui sifat-sifat pohon merah-hitam, dijamin bahwa semua implementasi berbasis pohon merah-hitam dapat memastikan bahwa waktu menjalankan operasi adalah logaritmik (kecuali pencarian jangkauan. Waktu tambahan yang dibutuhkan sebanding dengan jumlah kunci yang dikembalikan).
Java's TreeMap diimplementasikan melalui pohon merah dan hitam.
Jika Anda tidak menggambar, mudah untuk bingung. Berikut ini adalah diagram untuk menggambarkan operasi penyisipan pohon merah dan hitam.
Setelah memasukkan simpul merah ke pohon merah dan hitam, akan ada 6 situasi: n mewakili simpul yang dimasukkan, P mewakili simpul induk, U mewakili simpul paman, g mewakili node kakek, dan x mewakili simpul operasi saat ini
Kodenya adalah sebagai berikut:
RedBlackBST kelas publik <Key memperluas yang sebanding <Yey>, value> {private node root; private static final boolean red = true; private static final boolean black = false; node kelas pribadi {kunci kunci pribadi; // Kunci Nilai Pribadi Val; // Nilai simpul pribadi kiri, kanan, induk; // Pohon anak kiri dan kiri dan node induk warna boolean pribadi; // Warna tautan yang ditunjukkan oleh simpul node induknya (tombol kunci, nilai val, node induk, warna boolean) {this.key = key; this.val = val; this.color = warna; }} nilai publik get (tombol kunci) {node x = root; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; lain jika (cmp> 0) x = x.right; lain mengembalikan x.val; } return null; } public void put (tombol tombol, val val) {if (root == null) {// Jika itu adalah simpul root, buat node sebagai root hitam = node baru (tombol, val, null, hitam); kembali; } // Temukan Posisi Posisi Penyisipan yang sesuai Parent = NULL; Node cur = root; while (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; lain cur = cur.left; } Node n = node baru (tombol, val, induk, merah); // ord node baru normal adalah merah // masukkan simpul baru di bawah induk if (key.compareto (parent.key)> 0) parent.right = n; Parent.LEFT.LEFT = N; // Setelah memasukkan simpul baru, Anda harus menyesuaikan warna dan sifat beberapa node di pohon untuk memastikan bahwa fitur pohon merah dan hitam tidak dihancurkan. fixafterinsersion (n); } private node parentof (node x) {return (x == null? null: x.parent); } private boolean colorof (node x) {return (x == null? null: x.right); } private node leftof (node x) {return (x == null? null: x.right); } private node rightof (node x) {return (x == null? null: x.right); } private void setColor (node x, boolean color) {if (x! = null) x.color = warna; } private void fixafterInsion (node x) {while (x! = null && colorof (parentof (x)) == merah) {node grandpa = parentof (parentof (x)); Node induk = parentof (x); if (parent == leftof (grandpa)) {// case 1 || case2 || case3 node paman = rightof (kakek); if (colorof (paman) == merah) {// case1, paman adalah setcolor merah (induk, hitam); // simpul induk adalah setcolor hitam (paman, hitam); // Node paman adalah setcolor hitam (kakek, merah); // node kakek adalah merah x = kakek; // Karena node kakek berwarna merah dari hitam ke merah, atribut merah dan hitam dari node induk dan leluhurnya perlu disesuaikan} else {// case2 || case3, pamannya hitam if (x == rightOf (parent)) {// case2 x = induk; rotateleft (x); } // case3 setColor (induk, hitam); setColor (kakek, merah); Rotateright (Kakek); }} else {// case4 || Kasus 5 || case6 node paman = kiri (kakek); if (colorof (paman) == merah) {// case4 || case5 || case6 setColor (induk, hitam); setColor (paman, hitam); setColor (kakek, merah); x = kakek; } else {// case5 || case6, pamannya hitam if (x == leftof (parent)) {// case5 x = parent; Rotateright (x); } // case6 setColor (induk, hitam); setColor (kakek, merah); rotateleft (kakek); }}}} private void rotateleft (node x) {if (x == null) return; Node y = x.right; x.right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void rotateright (node x) {if (x == null) return; Node y = x.left; x.left = y.right; if (y.right! = null) y.right.parent = x; y.right = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}Penting untuk menggambar diagram untuk Rotateleft dan Rotateright di atas:
Artikel di atas didasarkan pada prinsip operasi penyisipan pohon merah dan hitam dan metode implementasi java (berbagi) yang merupakan semua konten yang saya bagikan dengan Anda. Saya harap Anda dapat memberi Anda referensi dan saya harap Anda dapat mendukung wulin.com lebih lanjut.