En la inserción ascendente de árboles rojos y negros , se utiliza la inserción «simple» del árbol de búsqueda binaria, seguida de la corrección de las infracciones del árbol RB en el camino de regreso a la raíz. Esto se puede hacer fácilmente con la ayuda de la recursividad. Mientras está en Inserción de arriba hacia abajo, las correcciones se realizan mientras se desplaza hacia abajo en el árbol hasta el punto de inserción. Cuando se realiza la inserción real, no se necesitan más correcciones, por lo que no es necesario volver a subir por el árbol.
Por lo tanto, el objetivo de la inserción Top-Down es atravesar desde la raíz hasta el punto de inserción de tal manera que se mantengan las propiedades de RB. Este enfoque iterativo hace que la inserción de arriba hacia abajo sea más rápida que la inserción de abajo hacia arriba.
Las dos operaciones básicas a realizar para corregir violaciones y equilibrar son:
- Recolorear
- Rotación
El siguiente es el algoritmo detallado.
El objetivo principal de este algoritmo es crear un punto de inserción en el que el padre del nuevo Node sea negro, o el tío del nuevo Node sea negro.
Sea N el nuevo Node a insertar.
- Si Y y Z son negros:
- Si el padre de X es negro:
- El padre P de X es rojo, el abuelo es negro y X y P son hijos izquierdos o derechos del abuelo G:
- Volver a colorear X, Y, Z
- Rotar P alrededor de G
- Color P negro
- Color G rojo
- El padre de X es rojo, el abuelo es negro y X y P son hijos opuestos del abuelo G
- Volver a colorear X, Y, Z
- Rotar X alrededor de P
- Rotar X alrededor de G
- Cambiar el color de X y G
A continuación la implementación del siguiente enfoque:
Java
// Java implementation for Top-Down
// Red-Black Tree Insertion creating
// a red black tree and storing an
// English sentence into it using Top
// down insertion approach
import static java.lang.Integer.max;
// Class for performing
// RBTree operations
public class RbTree {
TreeNode Root = null;
// Function to calculate
// the height of the tree
int HeightT(TreeNode Root)
{
int lefth, righth;
if (Root == null
|| (Root.children == null
&& Root.children[1] == null)) {
return 0;
}
lefth = HeightT(Root.children[0]);
righth = HeightT(Root.children[1]);
return (max(lefth, righth) + 1);
}
// Function to check if
// dir is equal to 0
int check(int dir)
{
return dir == 0 ? 1 : 0;
}
// Function to check if a
// node's color is red or not
boolean isRed(TreeNode Node)
{
return Node != null
&& Node.color.equals("R");
}
// Function to perform
// single rotation
TreeNode SingleRotate(TreeNode Node,
int dir)
{
TreeNode temp
= Node.children[check(dir)];
Node.children[check(dir)]
= temp.children[dir];
temp.children[dir] = Node;
Root.color = "R";
temp.color = "B";
return temp;
}
// Function to perform double rotation
TreeNode DoubleRotate(TreeNode Node,
int dir)
{
Node.children[check(dir)]
= SingleRotate(Node.children[check(dir)],
check(dir));
return SingleRotate(Node, dir);
}
// Function to insert a new
// node with given data
TreeNode Insert(RbTree tree,
String data)
{
if (tree.Root == null) {
tree.Root
= new TreeNode(data);
if (tree.Root == null)
return null;
}
else {
// A temporary root
TreeNode temp = new TreeNode("");
// Grandparent and Parent
TreeNode g, t;
TreeNode p, q;
int dir = 0, last = 0;
t = temp;
g = p = null;
t.children[1] = tree.Root;
q = t.children[1];
while (true) {
if (q == null) {
// Inserting root node
q = new TreeNode(data);
p.children[dir] = q;
}
// Sibling is red
else if (isRed(q.children[0])
&& isRed(q.children[1])) {
// Recoloring if both
// children are red
q.color = "R";
q.children[0].color = "B";
q.children[1].color = "B";
}
if (isRed(q) && isRed(p)) {
// Resolving red-red
// violation
int dir2;
if (t.children[1] == g) {
dir2 = 1;
}
else {
dir2 = 0;
}
// If children and parent
// are left-left or
// right-right of grand-parent
if (q == p.children[last]) {
t.children[dir2]
= SingleRotate(g,
last == 0
? 1
: 0);
}
// If they are opposite
// childs i.e left-right
// or right-left
else {
t.children[dir2]
= DoubleRotate(g,
last == 0
? 1
: 0);
}
}
// Checking for correct
// position of node
if (q.data.equals(data)) {
break;
}
last = dir;
// Finding the path to
// traverse [Either left
// or right ]
dir = q.data.compareTo(data) < 0
? 1
: 0;
if (g != null) {
t = g;
}
// Rearranging pointers
g = p;
p = q;
q = q.children[dir];
}
tree.Root = temp.children[1];
}
// Assign black color
// to the root node
tree.Root.color = "B";
return tree.Root;
}
// Print nodes at each
// level in level order
// traversal
void PrintLevel(TreeNode root, int i)
{
if (root == null) {
return;
}
if (i == 1) {
System.out.print("| "
+ root.data
+ " | "
+ root.color
+ " |");
if (root.children[0] != null) {
System.out.print(" "
+ root.children[0].data
+ " |");
}
else {
System.out.print(" "
+ "NULL"
+ " |");
}
if (root.children[1] != null) {
System.out.print(" "
+ root.children[1].data
+ " |");
}
else {
System.out.print(" "
+ "NULL"
+ " |");
}
System.out.print(" ");
return;
}
PrintLevel(root.children[0],
i - 1);
PrintLevel(root.children[1],
i - 1);
}
// Utility Function to
// perform level order
// traversal
void LevelOrder(TreeNode root)
{
int i;
for (i = 1;
i < HeightT(root) + 1;
i++) {
PrintLevel(root, i);
System.out.print("\n\n");
}
}
}
// Class for representing
// a node of the tree
class TreeNode {
// Class variables
String data, color;
TreeNode children[];
public TreeNode(String data)
{
// Color R- Red
// and B - Black
this.data = data;
this.color = "R";
children
= new TreeNode[2];
children[0] = null;
children[1] = null;
}
}
// Driver Code
class Driver {
public static void main(String[] args)
{
// Tree Node Representation
// -------------------------------------------
// DATA | COLOR | LEFT CHILD | RIGHT CHILD |
// -------------------------------------------
RbTree Tree = new RbTree();
String Sentence, Word;
Sentence = "old is gold";
String Word_Array[]
= Sentence.split(" ");
for (int i = 0;
i < Word_Array.length;
i++) {
Tree.Root
= Tree.Insert(Tree,
Word_Array[i]);
}
// Print Level Order Traversal
System.out.println("The Level"
+ "Order Traversal"
+ "of the tree is:");
Tree.LevelOrder(Tree.Root);
System.out.println("\nInserting a"
+ " word in the tree:");
Word = "forever";
Tree.Root = Tree.Insert(Tree,
Word);
System.out.println("");
Tree.LevelOrder(Tree.Root);
}
}
C#
// C# implementation for Top-Down
// Red-Black Tree Insertion creating
// a red black tree and storing an
// English sentence into it using Top
// down insertion approach
using System;
// Class for performing
// RBTree operations
class RbTree
{
public TreeNode Root = null;
// Function to calculate
// the height of the tree
public int HeightT(TreeNode Root)
{
int lefth, righth;
if (Root == null ||
(Root.children == null &&
Root.children[1] == null))
{
return 0;
}
lefth = HeightT(Root.children[0]);
righth = HeightT(Root.children[1]);
return (Math.Max(lefth, righth) + 1);
}
// Function to check if
// dir is equal to 0
public int check(int dir)
{
return dir == 0 ? 1 : 0;
}
// Function to check if a
// node's color is red or not
public bool isRed(TreeNode Node)
{
return Node != null &&
Node.color.Equals("R");
}
// Function to perform
// single rotation
public TreeNode SingleRotate(TreeNode Node, int dir)
{
TreeNode temp = Node.children[check(dir)];
Node.children[check(dir)] = temp.children[dir];
temp.children[dir] = Node;
Root.color = "R";
temp.color = "B";
return temp;
}
// Function to perform double rotation
public TreeNode DoubleRotate(TreeNode Node, int dir)
{
Node.children[check(dir)] =
SingleRotate(Node.children[check(dir)],
check(dir));
return SingleRotate(Node, dir);
}
// Function to insert a new
// node with given data
public TreeNode Insert(RbTree tree,
String data)
{
if (tree.Root == null)
{
tree.Root = new TreeNode(data);
if (tree.Root == null)
return null;
}
else
{
// A temporary root
TreeNode temp = new TreeNode("");
// Grandparent and Parent
TreeNode g, t;
TreeNode p, q;
int dir = 0, last = 0;
t = temp;
g = p = null;
t.children[1] = tree.Root;
q = t.children[1];
while (true)
{
if (q == null)
{
// Inserting root node
q = new TreeNode(data);
p.children[dir] = q;
}
// Sibling is red
else if (isRed(q.children[0]) &&
isRed(q.children[1]))
{
// Recoloring if both
// children are red
q.color = "R";
q.children[0].color = "B";
q.children[1].color = "B";
}
if (isRed(q) && isRed(p))
{
// Resolving red-red
// violation
int dir2;
if (t.children[1] == g)
{
dir2 = 1;
}
else
{
dir2 = 0;
}
// If children and parent
// are left-left or
// right-right of grand-parent
if (q == p.children[last])
{
t.children[dir2] =
SingleRotate(g, last == 0 ? 1 : 0);
}
// If they are opposite
// childs i.e left-right
// or right-left
else
{
t.children[dir2] =
DoubleRotate(g, last == 0 ? 1 : 0);
}
}
// Checking for correct
// position of node
if (q.data.Equals(data))
{
break;
}
last = dir;
// Finding the path to
// traverse [Either left
// or right ]
dir = q.data.CompareTo(data) < 0 ? 1 : 0;
if (g != null)
{
t = g;
}
// Rearranging pointers
g = p;
p = q;
q = q.children[dir];
}
tree.Root = temp.children[1];
}
// Assign black color
// to the root node
tree.Root.color = "B";
return tree.Root;
}
// Print nodes at each
// level in level order
// traversal
public void PrintLevel(TreeNode root, int i)
{
if (root == null)
{
return;
}
if (i == 1)
{
Console.Write("| " + root.data +
" | " + root.color + " |");
if (root.children[0] != null)
{
Console.Write(" " +
root.children[0].data + " |");
}
else
{
Console.Write(" " + "NULL" + " |");
}
if (root.children[1] != null)
{
Console.Write(" " +
root.children[1].data + " |");
}
else
{
Console.Write(" " + "NULL" + " |");
}
Console.Write(" ");
return;
}
PrintLevel(root.children[0], i - 1);
PrintLevel(root.children[1], i - 1);
}
// Utility Function to perform
// level order traversal
public void LevelOrder(TreeNode root)
{
int i;
for (i = 1; i < HeightT(root) + 1; i++)
{
PrintLevel(root, i);
Console.Write("\n\n");
}
}
}
// Class for representing
// a node of the tree
public class TreeNode
{
// Class variables
public String data, color;
public TreeNode []children;
public TreeNode(String data)
{
// Color R- Red
// and B - Black
this.data = data;
this.color = "R";
children = new TreeNode[2];
children[0] = null;
children[1] = null;
}
}
// Driver Code
public class Driver
{
public static void Main(String[] args)
{
// Tree Node Representation
// -------------------------------------------
// DATA | COLOR | LEFT CHILD | RIGHT CHILD |
// -------------------------------------------
RbTree Tree = new RbTree();
String Sentence, Word;
Sentence = "old is gold";
char[] spearator = { ' ', ' ' };
String []Word_Array = Sentence.Split(spearator,
StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < Word_Array.Length; i++)
{
Tree.Root = Tree.Insert(Tree,
Word_Array[i]);
}
// Print Level Order Traversal
Console.WriteLine("The Level" +
"Order Traversal" +
"of the tree is:");
Tree.LevelOrder(Tree.Root);
Console.WriteLine("\nInserting a" +
" word in the tree:");
Word = "forever";
Tree.Root = Tree.Insert(Tree, Word);
Console.WriteLine("");
Tree.LevelOrder(Tree.Root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 implementation for Top-Down
# Red-Black Tree Insertion creating
# a red black tree and storing an
# English sentence into it using Top
# down insertion approach
# Class for performing
# RBTree operations
class RbTree:
Root = None
# Function to calculate
# the height of the tree
def HeightT(self,Root):
lefth, righth=0, 0
if (Root == None or (Root.children == None and Root.children[1] == None)):
return 0
lefth = self.HeightT(Root.children[0])
righth = self.HeightT(Root.children[1])
return (max(lefth, righth) + 1)
# Function to check if
# dir is equal to 0
@staticmethod
def check(dir):
return 1 if dir == 0 else 0
# Function to check if a
# node's color is red or not
@staticmethod
def isRed(Node):
return Node != None and Node.color=="R"
# Function to perform
# single rotation
def SingleRotate(self, Node, dir):
temp = Node.children[self.check(dir)]
Node.children[self.check(dir)] = temp.children[dir]
temp.children[dir] = Node
self.Root.color = "R"
temp.color = "B"
return temp
# Function to perform double rotation
def DoubleRotate(self, Node, dir):
Node.children[self.check(dir)] = self.SingleRotate(Node.children[self.check(dir)], self.check(dir))
return self.SingleRotate(Node, dir)
# Function to insert a new
# node with given data
def Insert(self, tree, data):
if (tree.Root == None):
tree.Root = TreeNode(data)
if (tree.Root == None):
return None
else:
# A temporary root
temp = TreeNode("")
# Grandparent and Parent
g, t=None,None
p, q=None,None
dir = 0; last = 0
t = temp
g = p = None
t.children[1] = tree.Root
q = t.children[1]
while (True):
if (q == None):
# Inserting root node
q = TreeNode(data)
p.children[dir] = q
# Sibling is red
elif (self.isRed(q.children[0]) and self.isRed(q.children[1])):
# Recoloring if both
# children are red
q.color = "R"
q.children[0].color = "B"
q.children[1].color = "B"
if (self.isRed(q) and self.isRed(p)):
# Resolving red-red
# violation
dir2=0
if (t.children[1] == g):
dir2 = 1
else:
dir2 = 0
# If children and parent
# are left-left or
# right-right of grand-parent
if (q == p.children[last]):
t.children[dir2] = self.SingleRotate(g, 1 if last == 0 else 0)
# If they are opposite
# childs i.e left-right
# or right-left
else:
t.children[dir2] = self.DoubleRotate(g,1 if last == 0 else 0)
# Checking for correct
# position of node
if (q.data==data):
break
last = dir
# Finding the path to
# traverse [Either left
# or right ]
dir = 1 if q.data<data else 0
if (g != None):
t = g
# Rearranging pointers
g = p
p = q
q = q.children[dir]
tree.Root = temp.children[1]
# Assign black color
# to the root node
tree.Root.color = "B"
return tree.Root
# Print nodes at each
# level in level order
# traversal
def PrintLevel(self, root, i):
if (root == None):
return
if (i == 1):
print("| {} | {} |".format(root.data,root.color),end='')
if (root.children[0] != None):
print(" {} |".format(root.children[0].data),end='')
else:
print(" None |",end='')
if (root.children[1] != None):
print(" {} |".format(root.children[1].data),end='')
else:
print(" None |",end='')
return
self.PrintLevel(root.children[0], i - 1)
self.PrintLevel(root.children[1], i - 1)
# Utility Function to perform
# level order traversal
def LevelOrder(self, root):
for i in range(self.HeightT(root) + 1):
self.PrintLevel(root, i)
print('\n')
# Class for representing
# a node of the tree
class TreeNode:
def __init__(self, data):
# Color R- Red
# and B - Black
self.data = data
self.color = "R"
self.children = [None,None]
# Driver Code
if __name__=='__main__':
# Tree Node Representation
# -------------------------------------------
# DATA | COLOR | LEFT CHILD | RIGHT CHILD |
# -------------------------------------------
Tree = RbTree()
Sentence, Word='',''
Sentence = "old is gold"
Word_Array = Sentence.split()
for i in range(len(Word_Array)):
Tree.Root = Tree.Insert(Tree, Word_Array[i])
# Print Level Order Traversal
print("The Level Order Traversal the tree is:")
Tree.LevelOrder(Tree.Root)
print("\nInserting a word in the tree:")
Word = "forever"
Tree.Root = Tree.Insert(Tree, Word)
Tree.LevelOrder(Tree.Root)
# This code is contributed by Amartya Ghosh
Producción:
The LevelOrder Traversalof the tree is: | is | B | gold | old | | gold | R | NULL | NULL | | old | R | NULL | NULL | Inserting a word in the tree: | is | B | gold | old | | gold | B | forever | NULL | | old | B | NULL | NULL | | forever | R | NULL | NULL |
Referencias:
Red Black Trees – UMBC CSEE
Publicación traducida automáticamente
Artículo escrito por RajatAgrawal7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA