Un árbol rojo y negro es un árbol de búsqueda binario equilibrado. Cada nodo tiene un bit de almacenamiento para representar el color del nodo, que puede ser rojo o negro.
Los árboles rojos y negros tienen las siguientes propiedades:
(1) Cada nodo es rojo o negro
(2) El nodo raíz es negro
(3) Si un nodo es rojo, sus dos hijos son negros
(4) Para cada nodo, todas las rutas desde ese nodo hasta sus descendientes contienen el mismo número de nodos negros.
A través de las propiedades del árbol rojo-negro, se garantiza que todas las implementaciones basadas en el árbol rojo-negro pueden garantizar que el tiempo de ejecución de la operación sea logarítmico (excepto la búsqueda de rango. El tiempo extra que toma es proporcional al número de claves devueltas).
Treemap de Java se implementa a través de árboles rojos y negros.
Si no dibuja una imagen, es fácil confundirse. El siguiente es un diagrama para ilustrar la operación de inserción del árbol rojo y negro.
Después de insertar un nodo rojo en el árbol rojo y negro, habrá 6 situaciones: n representa el nodo insertado, p representa el nodo principal, U representa el nodo del tío, g representa el nodo del abuelo y x representa el nodo de operación actual
El código es el siguiente:
public class RedBlackBst <Key extiende <Key>, Value> {Root de nodo privado; RED BOOLEO FINAL STÁTICO PRIVADO = VERDADERO; Private estático final Boolean negro = falso; nodo de clase privada {clave privada clave; // valor privado clave val; // Value el nodo privado a la izquierda, derecha, padre; // Árboles infantiles izquierdos y delanteros y nodo principal de color booleano privado; // El color del enlace apuntado por su nodo público nodo principal (clave clave, valor val, nodo parent, color booleano) {this.key = key; this.val = val; this.color = color; }} Public Value get (clave clave) {nodo x = root; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; else if (cmp> 0) x = x.right; else return x.val; } return null; } public void put (clave clave, valor val) {if (root == null) {// Si es un nodo raíz, cree el nodo como raíz negro = nuevo nodo (clave, val, nulo, negro); devolver; } // Encuentra un nodo de posición de inserción adecuado parent = null; Nodo cur = root; while (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } Nodo n = nuevo nodo (clave, val, padre, rojo); // ord normal el nuevo nodo es rojo // inserte el nuevo nodo en matriz if (key.compareto (parent.key)> 0) parent.right = n; el más parent.left = n; // Después de insertar un nuevo nodo, debe ajustar los colores y propiedades de algunos nodos en el árbol para garantizar que las características del árbol rojo y negro no se destruyan. fixafterinsertion (n); } privado nodo parentf (nodo x) {return (x == null? null: x.parent); } private boolean colorof (nodo x) {return (x == null? null: x.right); } nodo privado izquierdo (nodo x) {return (x == null? null: x.right); } REDEMO DE NODO PRIVADO (nodo x) {return (x == null? null: x.right); } private void setColor (nodo x, color booleano) {if (x! = null) x.color = color; } private void Fixafterinsertion (nodo x) {while (x! = null && colorOf (parentOf (x)) == rojo) {nodo abuelo = parentOf (parentOf (x)); Nodo parent = parentof (x); if (parent == LeftOf (abuelo)) {// Caso 1 || case2 || Case3 nodo tío = rectof (abuelo); if (colorOf (tío) == rojo) {// case1, el tío es rojo setcolor (padre, negro); // El nodo principal es Black SetColor (tío, negro); // El nodo del tío es negro setcolor (abuelo, rojo); // El nodo del abuelo es rojo x = abuelo; // porque el nodo del abuelo es rojo de negro a rojo, los atributos rojos y negros del nodo principal y sus antepasados deben ser reajustados} else {// case2 || case3, el tío es negro si (x == rectof (parent)) {// case2 x = parent; rotateleft (x); } // case3 setColor (padre, negro); SetColor (abuelo, rojo); Rotateright (abuelo); }} else {// case4 || Caso 5 || Case6 nodo tío = LeftOf (abuelo); if (colorOf (tío) == rojo) {// case4 || case5 || Case6 SetColor (padre, negro); setColor (tío, negro); SetColor (abuelo, rojo); x = abuelo; } else {// case5 || Case6, el tío es negro si (x == izquierda (parent)) {// case5 x = parent; Rotateright (x); } // case6 setColor (padre, negro); SetColor (abuelo, rojo); Rotateleft (abuelo); }}}} private void rotateleft (nodo x) {if (x == null) return; Nodo 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 gotateright (nodo x) {if (x == null) return; Nodo 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; }}Es necesario dibujar un diagrama para el Rotateleft y Rotateright arriba:
El artículo anterior se basa en el principio de la operación de inserción de árboles rojos y negros y el método de implementación de Java (compartir), que es todo el contenido que comparto con usted. Espero que pueda darle una referencia y espero que pueda apoyar más a Wulin.com.