Prerrequisitos: árboles rojos y negros.
Un árbol rojo y negro inclinado a la izquierda o (LLRB) , es una variante del árbol rojo y negro, que es mucho más fácil de implementar que el propio árbol rojo y negro y garantiza todas las operaciones de búsqueda, eliminación e inserción en tiempo O (logn).
¿Qué Nodes son ROJOS y cuáles son negros?
Los Nodes que tienen doble borde entrante son de color ROJO.
Los Nodes que tienen un solo borde entrante son de color NEGRO.
Características de LLRB
1. El Node raíz es siempre de color NEGRO.
2. Cada nuevo Node insertado es siempre de color ROJO.
3. Cada hijo NULL de un Node se considera de color NEGRO.
Por ejemplo: solo 40 está presente en el árbol.
root
|
40 <-- as 40 is the root so it
/ \ is also Black in color.
NULL NULL <-- Black in color.
4. No debe haber un Node que tenga un hijo ROJO DERECHO y un hijo NEGRO IZQUIERDO (o un hijo NULL ya que todos los NULL son NEGROS) si está presente, gire el Node a la izquierda e intercambie los colores del Node actual y su hijo IZQUIERDO para mantener consistencia para la regla 2, es decir, el nuevo Node debe ser de color ROJO.
CASE 1.
root root
| ||
40 LeftRotate(40) 50
/ \\ ---> / \
NULL 50 40 NULL
root
|
ColorSwap(50, 40) 50
---> // \
40 NULL
5. No debe haber un Node que tenga un hijo IZQUIERDO ROJO y un nieto IZQUIERDO ROJO, si está presente, gire el Node a la derecha e intercambie los colores entre el Node y su hijo DERECHO para seguir la regla 2.
CASE 2.
root root
| ||
40 RightRotate(40) 20
// \ ---> // \
20 50 10 40
// \
10 50
root
|
ColorSwap(20, 40) 20
---> // \\
10 40
\
50
6. No debe haber un Node que tenga un hijo ROJO IZQUIERDO y un hijo ROJO DERECHO, si está presente Invierta los colores de todos los Nodes, es decir, Node_actual, hijo IZQUIERDO y hijo DERECHO.
CASE 3.
root root
| !color(20, 10, 30) ||
20 ---> 20
// \\ / \
10 30 10 30
root
As the root is always black |
---> 20
/ \
10 30
¿Por qué estamos siguiendo las reglas mencionadas anteriormente? Porque al seguir las características/reglas anteriores, podemos simular todas las propiedades del árbol rojo-negro sin preocuparnos por la compleja implementación del mismo.
Ejemplo:
Insert the following data into LEFT LEANING RED-BLACK
TREE and display the inorder traversal of tree.
Input : 10 20 30 40 50 25
Output : 10 20 30 40 50 25
root
|
40
// \
20 50
/ \
10 30
//
25
Enfoque:
Las inserciones en el LLRB son exactamente como insertar en un árbol de búsqueda binario . La diferencia es que después de insertar el Node en el árbol, volveremos sobre nuestros pasos hasta la raíz e intentaremos aplicar las reglas anteriores para LLRB.
Al hacer las rotaciones anteriores y el cambio de color, puede suceder que nuestra raíz se vuelva de color ROJO, por lo que también nosotros. Tenemos que asegurarnos de que nuestra raíz permanezca siempre de color NEGRO.
C++
// C++ program to implement insert operation
// in Red Black Tree.
#include <bits/stdc++.h>
using namespace std;
typedef struct node
{
struct node *left, *right;
int data;
// red ==> true, black ==> false
bool color;
}node;
// Utility function to create a node.
node* createNode(int data, bool color)
{
node *myNode = new node();
myNode -> left = myNode -> right = NULL;
myNode -> data = data;
// New Node which is created is
// always red in color.
myNode -> color = true;
return myNode;
}
// Utility function to rotate node anticlockwise.
node* rotateLeft(node* myNode)
{
cout << "left rotation!!\n";
node *child = myNode -> right;
node *childLeft = child -> left;
child -> left = myNode;
myNode -> right = childLeft;
return child;
}
// Utility function to rotate node clockwise.
node* rotateRight(node* myNode)
{
cout << "right rotation\n";
node *child = myNode -> left;
node *childRight = child -> right;
child -> right = myNode;
myNode -> left = childRight;
return child;
}
// Utility function to check whether
// node is red in color or not.
int isRed(node *myNode)
{
if (myNode == NULL)
return 0;
return (myNode -> color == true);
}
// Utility function to swap color of two
// nodes.
void swapColors(node *node1, node *node2)
{
bool temp = node1 -> color;
node1 -> color = node2 -> color;
node2 -> color = temp;
}
// Insertion into Left Leaning Red Black Tree.
node* insert(node* myNode, int data)
{
// Normal insertion code for any Binary
// Search tree.
if (myNode == NULL)
return createNode(data, false);
if (data < myNode -> data)
myNode -> left = insert(myNode -> left, data);
else if (data > myNode -> data)
myNode -> right = insert(myNode -> right, data);
else
return myNode;
// case 1.
// when right child is Red but left child is
// Black or doesn't exist.
if (isRed(myNode -> right) &&
!isRed(myNode -> left))
{
// Left rotate the node to make it into
// valid structure.
myNode = rotateLeft(myNode);
// Swap the colors as the child node
// should always be red
swapColors(myNode, myNode -> left);
}
// case 2
// when left child as well as left grand
// child in Red
if (isRed(myNode -> left) &&
isRed(myNode -> left -> left))
{
// Right rotate the current node to make
// it into a valid structure.
myNode = rotateRight(myNode);
swapColors(myNode, myNode -> right);
}
// case 3
// when both left and right child are Red in color.
if (isRed(myNode -> left) && isRed(myNode -> right))
{
// Invert the color of node as well
// it's left and right child.
myNode -> color = !myNode -> color;
// Change the color to black.
myNode -> left -> color = false;
myNode -> right -> color = false;
}
return myNode;
}
// Inorder traversal
void inorder(node *node)
{
if (node)
{
inorder(node -> left);
cout<< node -> data << " ";
inorder(node -> right);
}
}
// Driver code
int main()
{
node *root = NULL;
/* LLRB tree made after all insertions are made.
1. Nodes which have double INCOMING edge means
that they are RED in color.
2. Nodes which have single INCOMING edge means
that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25 */
root = insert(root, 10);
// To make sure that root remains
// black is color
root -> color = false;
root = insert(root, 20);
root -> color = false;
root = insert(root, 30);
root -> color = false;
root = insert(root, 40);
root -> color = false;
root = insert(root, 50);
root -> color = false;
root = insert(root, 25);
root -> color = false;
// Display the tree through inorder traversal.
inorder(root);
return 0;
}
// This code is contributed by rutvik_56
C
// C program to implement insert operation
// in Red Black Tree.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node
{
struct node *left, *right;
int data;
// red ==> true, black ==> false
bool color;
} node;
// utility function to create a node.
node* createNode(int data, bool color)
{
node *myNode = (node *) malloc(sizeof(node));
myNode -> left = myNode -> right = NULL;
myNode -> data = data;
// New Node which is created is
// always red in color.
myNode -> color = true;
return myNode;
}
// utility function to rotate node anticlockwise.
node* rotateLeft(node* myNode)
{
printf("left rotation!!\n");
node *child = myNode -> right;
node *childLeft = child -> left;
child -> left = myNode;
myNode -> right = childLeft;
return child;
}
// utility function to rotate node clockwise.
node* rotateRight(node* myNode)
{
printf("right rotation\n");
node *child = myNode -> left;
node *childRight = child -> right;
child -> right = myNode;
myNode -> left = childRight;
return child;
}
// utility function to check whether
// node is red in color or not.
int isRed(node *myNode)
{
if (myNode == NULL)
return 0;
return (myNode -> color == true);
}
// utility function to swap color of two
// nodes.
void swapColors(node *node1, node *node2)
{
bool temp = node1 -> color;
node1 -> color = node2 -> color;
node2 -> color = temp;
}
// insertion into Left Leaning Red Black Tree.
node* insert(node* myNode, int data)
{
// Normal insertion code for any Binary
// Search tree.
if (myNode == NULL)
return createNode(data, false);
if (data < myNode -> data)
myNode -> left = insert(myNode -> left, data);
else if (data > myNode -> data)
myNode -> right = insert(myNode -> right, data);
else
return myNode;
// case 1.
// when right child is Red but left child is
// Black or doesn't exist.
if (isRed(myNode -> right) && !isRed(myNode -> left))
{
// left rotate the node to make it into
// valid structure.
myNode = rotateLeft(myNode);
// swap the colors as the child node
// should always be red
swapColors(myNode, myNode -> left);
}
// case 2
// when left child as well as left grand child in Red
if (isRed(myNode -> left) && isRed(myNode -> left -> left))
{
// right rotate the current node to make
// it into a valid structure.
myNode = rotateRight(myNode);
swapColors(myNode, myNode -> right);
}
// case 3
// when both left and right child are Red in color.
if (isRed(myNode -> left) && isRed(myNode -> right))
{
// invert the color of node as well
// it's left and right child.
myNode -> color = !myNode -> color;
// change the color to black.
myNode -> left -> color = false;
myNode -> right -> color = false;
}
return myNode;
}
// Inorder traversal
void inorder(node *node)
{
if (node)
{
inorder(node -> left);
printf("%d ", node -> data);
inorder(node -> right);
}
}
// Driver function
int main()
{
node *root = NULL;
/* LLRB tree made after all insertions are made.
1. Nodes which have double INCOMING edge means
that they are RED in color.
2. Nodes which have single INCOMING edge means
that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25 */
root = insert(root, 10);
// to make sure that root remains
// black is color
root -> color = false;
root = insert(root, 20);
root -> color = false;
root = insert(root, 30);
root -> color = false;
root = insert(root, 40);
root -> color = false;
root = insert(root, 50);
root -> color = false;
root = insert(root, 25);
root -> color = false;
// display the tree through inorder traversal.
inorder(root);
return 0;
}
Java
// Java program to implement insert operation
// in Red Black Tree.
class node
{
node left, right;
int data;
// red ==> true, black ==> false
boolean color;
node(int data)
{
this.data = data;
left = null;
right = null;
// New Node which is created is
// always red in color.
color = true;
}
}
public class LLRBTREE {
private static node root = null;
// utility function to rotate node anticlockwise.
node rotateLeft(node myNode)
{
System.out.printf("left rotation!!\n");
node child = myNode.right;
node childLeft = child.left;
child.left = myNode;
myNode.right = childLeft;
return child;
}
// utility function to rotate node clockwise.
node rotateRight(node myNode)
{
System.out.printf("right rotation\n");
node child = myNode.left;
node childRight = child.right;
child.right = myNode;
myNode.left = childRight;
return child;
}
// utility function to check whether
// node is red in color or not.
boolean isRed(node myNode)
{
if (myNode == null)
return false;
return (myNode.color == true);
}
// utility function to swap color of two
// nodes.
void swapColors(node node1, node node2)
{
boolean temp = node1.color;
node1.color = node2.color;
node2.color = temp;
}
// insertion into Left Leaning Red Black Tree.
node insert(node myNode, int data)
{
// Normal insertion code for any Binary
// Search tree.
if (myNode == null)
return new node(data);
if (data < myNode.data)
myNode.left = insert(myNode.left, data);
else if (data > myNode.data)
myNode.right = insert(myNode.right, data);
else
return myNode;
// case 1.
// when right child is Red but left child is
// Black or doesn't exist.
if (isRed(myNode.right) && !isRed(myNode.left))
{
// left rotate the node to make it into
// valid structure.
myNode = rotateLeft(myNode);
// swap the colors as the child node
// should always be red
swapColors(myNode, myNode.left);
}
// case 2
// when left child as well as left grand child in Red
if (isRed(myNode.left) && isRed(myNode.left.left))
{
// right rotate the current node to make
// it into a valid structure.
myNode = rotateRight(myNode);
swapColors(myNode, myNode.right);
}
// case 3
// when both left and right child are Red in color.
if (isRed(myNode.left) && isRed(myNode.right))
{
// invert the color of node as well
// it's left and right child.
myNode.color = !myNode.color;
// change the color to black.
myNode.left.color = false;
myNode.right.color = false;
}
return myNode;
}
// Inorder traversal
void inorder(node node)
{
if (node != null)
{
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}
public static void main(String[] args) {
/* LLRB tree made after all insertions are made.
1. Nodes which have double INCOMING edge means
that they are RED in color.
2. Nodes which have single INCOMING edge means
that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25 */
LLRBTREE node = new LLRBTREE();
root = node.insert(root, 10);
// to make sure that root remains
// black is color
root.color = false;
root = node.insert(root, 20);
root.color = false;
root = node.insert(root, 30);
root.color = false;
root = node.insert(root, 40);
root.color = false;
root = node.insert(root, 50);
root.color = false;
root = node.insert(root, 25);
root.color = false;
// display the tree through inorder traversal.
node.inorder(root);
}
}
// This code is contributed by ARSHPREET_SINGH
C#
// C# program to implement insert
// operation in Red Black Tree.
using System;
class node
{
public node left, right;
public int data;
// red ==> true, black ==> false
public Boolean color;
public node(int data)
{
this.data = data;
left = null;
right = null;
// New Node which is created
// is always red in color.
color = true;
}
}
public class LLRBTREE
{
private static node root = null;
// utility function to rotate
// node anticlockwise.
node rotateLeft(node myNode)
{
Console.Write("left rotation!!\n");
node child = myNode.right;
node childLeft = child.left;
child.left = myNode;
myNode.right = childLeft;
return child;
}
// utility function to rotate
// node clockwise.
node rotateRight(node myNode)
{
Console.Write("right rotation\n");
node child = myNode.left;
node childRight = child.right;
child.right = myNode;
myNode.left = childRight;
return child;
}
// utility function to check whether
// node is red in color or not.
Boolean isRed(node myNode)
{
if (myNode == null)
return false;
return (myNode.color == true);
}
// utility function to swap
// color of two nodes.
void swapColors(node node1, node node2)
{
Boolean temp = node1.color;
node1.color = node2.color;
node2.color = temp;
}
// insertion into Left
// Leaning Red Black Tree.
node insert(node myNode, int data)
{
// Normal insertion code for
// any Binary Search tree.
if (myNode == null)
return new node(data);
if (data < myNode.data)
myNode.left = insert(myNode.left, data);
else if (data > myNode.data)
myNode.right = insert(myNode.right, data);
else
return myNode;
// case 1.
// when right child is Red
// but left child is
// Black or doesn't exist.
if (isRed(myNode.right) &&
!isRed(myNode.left))
{
// left rotate the node to make
// it into valid structure.
myNode = rotateLeft(myNode);
// swap the colors as the child
// node should always be red
swapColors(myNode, myNode.left);
}
// case 2
// when left child as well as
// left grand child in Red
if (isRed(myNode.left) &&
isRed(myNode.left.left))
{
// right rotate the current node
// to make it into a valid structure.
myNode = rotateRight(myNode);
swapColors(myNode, myNode.right);
}
// case 3
// when both left and right
// child are Red in color.
if (isRed(myNode.left) &&
isRed(myNode.right))
{
// invert the color of node as well
// it's left and right child.
myNode.color = !myNode.color;
// change the color to black.
myNode.left.color = false;
myNode.right.color = false;
}
return myNode;
}
// Inorder traversal
void inorder(node node)
{
if (node != null)
{
inorder(node.left);
Console.Write(node.data + " ");
inorder(node.right);
}
}
// Driver Code
static public void Main(String []args)
{
/* LLRB tree made after all
insertions are made.
1. Nodes which have double INCOMING
edge means that they are RED in color.
2. Nodes which have single INCOMING edge
means that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25
*/
LLRBTREE node = new LLRBTREE();
root = node.insert(root, 10);
// to make sure that root
// remains black is color
root.color = false;
root = node.insert(root, 20);
root.color = false;
root = node.insert(root, 30);
root.color = false;
root = node.insert(root, 40);
root.color = false;
root = node.insert(root, 50);
root.color = false;
root = node.insert(root, 25);
root.color = false;
// display the tree through
// inorder traversal.
node.inorder(root);
}
}
// This code is contributed
// by Arnab Kundu
Python3
"""
Python program to implement insert operation
in Red Black Tree.
"""
from typing import Any
import enum
class Color(enum.Enum):
""" Enums for the colors"""
RED = True
BLACK = False
class Node:
"""A Red Black Tree node,
the default color of a node is RED
"""
def __init__(self, value: Any):
self.val: Any = value
self.color: Color = Color.RED
self.left = None
self.right = None
def __repr__(self):
return f'Node(val={self.val}, color={self.color.value}, left={self.left}, right={self.right})'
class RBT:
"""Red Black Tree Class"""
def __init__(self):
self.root = None
def insert(self, value: Any) -> None:
"""Insertion and updation of root"""
self.root = self.__insert(self.root, value)
self.root.color = Color.BLACK
def __insert(self, root: Node, val: Any) -> Node:
"""Recursive insertion of the root"""
if root is None:
return Node(val)
if val < root.val:
root.left = self.__insert(root.left, val)
elif val > root.val:
root.right = self.__insert(root.right, val)
else:
root.val = val
if self.is_red(root.right) and not self.is_red(root.left):
root = self.rotate_left(root)
if self.is_red(root.left) and self.is_red(root.left.left):
root = self.rotate_right(root)
if self.is_red(root.left) and self.is_red(root.right):
self.flip_color(root)
return root
@staticmethod
def is_red(node: Node) -> bool:
"""Utility function to check if the node is RED color.
Empty nodes are considered BLACK
Args:
node: A RBT node
Returns: Boolean value if the node is Red or not
"""
if node is None:
return False
return node.color == Color.RED
@staticmethod
def flip_color(node: Node) -> None:
""" Flips the color if both left and right child are RED"""
node.color = Color.RED
node.left.color = Color.BLACK
node.right.color = Color.BLACK
def rotate_left(self, node: Node) -> Node:
"""Rotate the node left send the new node
if the right node is Red
Args:
node: The node which has a Red node on Right
Returns: the rotated new node
"""
new_root = node.right
node.right = new_root.left
new_root.left = node
new_root.color = node.color
node.color = Color.RED
print("Left Rotation !!")
return new_root
def rotate_right(self, node: Node) -> Node:
"""Rotate the node right send the new node
if the left node is Red and left of left is Red
Args:
node: The node which has both left child and left of left child Red
Returns: the rotated new node
"""
new_root = node.left
node.left = new_root.right
new_root.right = node
new_root.color = node.color
node.color = Color.RED
print("Right Rotation !!")
return new_root
def inorder(self) -> None:
"""Inorder Traversal for root"""
self.__inorder(self.root)
def __inorder(self, root: Node) -> None:
"""Recursive Inorder Traversal for any node"""
if root is None:
return
self.__inorder(root.left)
print(root.val, end=" ")
self.__inorder(root.right)
if __name__ == "__main__":
'''
LLRB tree made after all insertions are made.
1. Nodes which have double INCOMING edge means
that they are RED in color.
2. Nodes which have single INCOMING edge means
that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25
'''
rbt = RBT()
rbt.insert(10)
rbt.insert(20)
rbt.insert(30)
rbt.insert(40)
rbt.insert(50)
rbt.insert(25)
rbt.inorder()
# This code is contributed by Supratim Samantray (super_sam)
Javascript
<script>
// Javascript program to implement insert operation
// in Red Black Tree.
class node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
// New Node which is created is
// always red in color.
this.color = true;
}
}
let root = null;
// utility function to rotate node anticlockwise.
function rotateLeft(myNode)
{
document.write("left rotation!!<br>");
let child = myNode.right;
let childLeft = child.left;
child.left = myNode;
myNode.right = childLeft;
return child;
}
// utility function to rotate node clockwise.
function rotateRight(myNode)
{
document.write("right rotation<br>");
let child = myNode.left;
let childRight = child.right;
child.right = myNode;
myNode.left = childRight;
return child;
}
// utility function to check whether
// node is red in color or not.
function isRed(myNode)
{
if (myNode == null)
return false;
return (myNode.color == true);
}
// utility function to swap color of two
// nodes.
function swapColors(node1,node2)
{
let temp = node1.color;
node1.color = node2.color;
node2.color = temp;
}
// insertion into Left Leaning Red Black Tree.
function insert(myNode,data)
{
// Normal insertion code for any Binary
// Search tree.
if (myNode == null)
return new node(data);
if (data < myNode.data)
myNode.left = insert(myNode.left, data);
else if (data > myNode.data)
myNode.right = insert(myNode.right, data);
else
return myNode;
// case 1.
// when right child is Red but left child is
// Black or doesn't exist.
if (isRed(myNode.right) && !isRed(myNode.left))
{
// left rotate the node to make it into
// valid structure.
myNode = rotateLeft(myNode);
// swap the colors as the child node
// should always be red
swapColors(myNode, myNode.left);
}
// case 2
// when left child as well as left grand child in Red
if (isRed(myNode.left) && isRed(myNode.left.left))
{
// right rotate the current node to make
// it into a valid structure.
myNode = rotateRight(myNode);
swapColors(myNode, myNode.right);
}
// case 3
// when both left and right child are Red in color.
if (isRed(myNode.left) && isRed(myNode.right))
{
// invert the color of node as well
// it's left and right child.
myNode.color = !myNode.color;
// change the color to black.
myNode.left.color = false;
myNode.right.color = false;
}
return myNode;
}
// Inorder traversal
function inorder(node)
{
if (node != null)
{
inorder(node.left);
document.write(node.data + " ");
inorder(node.right);
}
}
/* LLRB tree made after all insertions are made.
1. Nodes which have double INCOMING edge means
that they are RED in color.
2. Nodes which have single INCOMING edge means
that they are BLACK in color.
root
|
40
// \
20 50
/ \
10 30
//
25 */
root = insert(root, 10);
// to make sure that root remains
// black is color
root.color = false;
root = insert(root, 20);
root.color = false;
root = insert(root, 30);
root.color = false;
root = insert(root, 40);
root.color = false;
root = insert(root, 50);
root.color = false;
root = insert(root, 25);
root.color = false;
// display the tree through inorder traversal.
inorder(root);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
left rotation!! left rotation!! left rotation!! 10 20 25 30 40 50
Complejidad de tiempo: O(log n)
Referencias
Árboles rojos y negros inclinados a la izquierda
Este artículo es una contribución de Arshpreet Soodan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA