I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Red black tree sort

Red black tree sort is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Implement red-black tree sorting of fixed width integers. Here, the left branch will only contain nodes with a smaller key and the right branch will only contain nodes with a larger key.

Start with an empty tree, add 30 nodes each with arbitrary (aka "random") keys, then traverse the tree, printing the values from the left node, the key value, then the values from the right node, displaying their value and their color (red or black). Since we are using a red-black tree here, this would eliminate any duplicate values.

Then delete an arbitrary 15 nodes and display the resulting tree.

You may use an implementation at Algebraic data types as a starting point, if you find that helpful.

For the purpose of this task, it would be best to verify the integrity of the red-black tree after every insert and after every delete.

## F#

### The Functions

` // Red black tree sort. Nigel Galloway: June 17th., 2022let fromSeq n=n|>Seq.fold(fun n g->insert g n) Emptylet toSeq g=let rec fN g=seq{match g with N(i,g,e,l)->yield l; yield! fN g; yield! fN e |_->()} in fN glet delSeq n g=toSeq g|>Seq.except n|>fromSeqlet rec printN n s t=match n with N(i,g,e,l)->printN g (s+"    ") "L";printfn "%s %s %A %d" s t i l; printN e (s+"    ") "R" |_->() `

` let n=fromSeq [85; 57; 51; 50; 86; 39; 95; 49; 44; 48; 21; 83; 11; 59; 88; 66; 4; 40; 24; 82; 63; 22; 37; 32; 91; 74; 28; 75; 62; 81]printfn "Populated Red Black Tree"; printN n "" "X"let g=delSeq [32; 40; 57; 63; 66; 75; 86; 59; 83; 51; 24; 62; 82; 39; 37] nprintfn "\nRed Black Tree after deletions"; printN g "" "X" `
Output:
```Populated Red Black Tree
L Red 4
L Black 11
L Black 21
R Black 22
L Red 24
L Red 28
L Black 32
L Red 37
R Black 39
R Red 40
R Black 44
L Red 48
R Black 49
L Black 50
L Black 51
R Black 57
L Black 59
R Red 62
R Black 63
X Black 66
L Black 74
L Black 75
L Red 81
R Black 82
R Black 83
L Black 85
R Black 86
L Black 88
R Red 91
R Black 95

Red Black Tree after deletions
L Red 4
L Black 11
L Black 21
R Black 22
R Red 28
X Black 44
L Black 48
L Black 49
R Black 50
R Red 74
L Black 81
R Black 85
L Red 88
R Black 91
R Red 95
```

## FreeBASIC

Code originally by AGS. https://www.freebasic.net/forum/viewtopic.php?t=16113

`#define NULL Cast(Any Ptr,0) Enum nodecolor    BLACK = 0    RED = 1End Enum Type RBNode        Dim izda As RBNode Ptr    Dim dcha As RBNode Ptr    Dim parent As RBNode Ptr    Dim kolor As nodecolor    Dim key As Integer    Dim value As String    Dim nonzero As Integer    Declare Constructor(Byval key As Integer = 0, value As String = "", Byval clr As nodecolor = RED)    Declare Destructor()End Type Constructor RBNode(Byval key As Integer, value As String, Byval clr As nodecolor = RED)    This.key = key    This.value = value    This.izda = NULL    This.dcha = NULL    This.parent = NULL    This.kolor = clr    This.nonzero = 1End Constructor     Destructor RBNode() End Destructor Function integer_compare(Byval key1 As Integer, Byval key2 As Integer) As Integer       If (key1 = key2) Then        Return 0    Elseif (key1 < key2) Then        Return -1    Elseif (key1 > key2) Then        Return 1    End IfEnd Function Type RBTree    Dim sentinel As RBNode Ptr    Dim root As RBNode Ptr    Dim count As Integer     Dim Compare As Function(Byval key1 As Integer, Byval key2 As Integer) As Integer    Declare Constructor(Byval cmp As Function(Byval key1 As Integer, Byval key2 As Integer) As Integer)    Declare Sub rotateLeft(Byval x As RBNode Ptr)    Declare Sub rotateRight(Byval x As RBNode Ptr)    Declare Sub insertFixup(Byval x As RBNode Ptr)     Declare Function insertNode(Byval key As Integer, value As String) As RBNode Ptr    Declare Sub deleteFixup(Byval x As RBNode Ptr)      Declare Sub deleteNode(Byval z As RBNode Ptr)    Declare Function findNode(Byval key As Integer) As RBNode Ptr    Declare Destructor() End Type Constructor RBTree(Byval cmp As Function(Byval key1 As Integer, Byval key2 As Integer) As Integer)    This.sentinel = New RBNode(0,"",BLACK)    This.sentinel->izda = sentinel    This.sentinel->dcha = sentinel    This.root = This.sentinel    This.count = 0    This.Compare = cmpEnd Constructor  Destructor RBTree()    'The tree is transformed into a tree in which     'left children are always leaves. This is done by rotation.     'After rotating any left child is a leaf (not a tree)    'so a izda child can simply be deleted.      'Usually a stack is used to keep track of what nodes have    'been removed. By using rotation there is no need for a stack.     Dim parent As RBNode Ptr    Dim child As RBNode Ptr     If (This.root <> This.sentinel Andalso This.root <> NULL) Then        parent = This.root        While (parent <> This.sentinel)                If (parent->izda = This.sentinel) Then                        child = parent->dcha                Delete parent                parent = 0            Else                        'rotate                child = parent->izda                parent->izda = child->dcha                child->dcha = parent            End If            parent = child        Wend      Else        If (This.sentinel <> 0) Then            Delete This.sentinel            This.sentinel = 0        End If            End IfEnd Destructor   Sub RBTree.rotateLeft(Byval x As RBNode Ptr)        'rotate node x to right     Var y = x->dcha     'establish x->dcha link    x->dcha = y->izda    If (y->izda <> This.sentinel) Then        y->izda->parent = x    End If     'establish y->parent link    If (y <> This.sentinel) Then        y->parent = x->parent    End If    If (x->parent) Then        If (x = x->parent->izda) Then            x->parent->izda = y        Else            x->parent->dcha = y        End If    Else        This.root = y    End If     'link x and y    y->izda = x    If (x <> This.sentinel) Then        x->parent = y    End IfEnd Sub Sub RBTree.rotateRight(Byval x As RBNode Ptr)    'rotate node x to right     Var y = x->izda     ' establish x->left link    x->izda = y->dcha    If (y->dcha <> This.sentinel) Then        y->dcha->parent = x    End If     ' establish y->parent link    If (y <> This.sentinel) Then        y->parent = x->parent    End If    If (x->parent) Then        If (x = x->parent->dcha) Then            x->parent->dcha = y        Else            x->parent->izda = y        End If    Else        This.root = y    End If     'link x and y    y->dcha = x    If (x <> This.sentinel) Then        x->parent = y    End IfEnd Sub Sub RBTree.insertFixup(Byval x As RBNode Ptr)    'maintain tree balance after inserting node x     'check Red-Black properties    While (x <> This.Root Andalso x->parent->kolor = RED)        'we have a violation        If (x->parent = x->parent->parent->izda) Then            Var y = x->parent->parent->dcha            If (y->kolor = RED) Then                'uncle is RED                x->parent->kolor = BLACK                y->kolor = BLACK                x->parent->parent->kolor = RED                x = x->parent->parent            Else                'uncle is BLACK                If (x = x->parent->dcha) Then                    'make x a izda child                    x = x->parent                    This.rotateLeft(x)                End If                'recolor and rotate                x->parent->kolor = BLACK                x->parent->parent->kolor = RED                This.rotateRight(x->parent->parent)            End If        Else            ' mirror image of above code            Var y = x->parent->parent->izda            If (y->kolor = RED) Then                ' uncle is RED                x->parent->kolor = BLACK                y->kolor = BLACK                x->parent->parent->kolor = RED                x = x->parent->parent            Else                ' uncle is BLACK                If (x = x->parent->izda) Then                    x = x->parent                    This.rotateRight(x)                End If                x->parent->kolor = BLACK                x->parent->parent->kolor = RED                This.rotateLeft(x->parent->parent)            End If        End If    Wend    This.root->kolor = BLACKEnd Sub Function RBTree.insertNode(Byval key As Integer, value As String) As RBNode Ptr    'Insert a node in the RBTree     'find where node belongs    Dim current As RBNode Ptr = This.root    Dim parent As RBNode Ptr    While (current <> This.sentinel)        Var rc = This.Compare(key, current->key)        If (rc = 0) Then Return current        parent = current        If (rc < 0) Then            current = current->izda        Else            current = current->dcha        End If    Wend    ' setup new node    Dim x As RBNode Ptr = New RBNode(key, value)    x->izda  = This.sentinel    x->dcha = This.sentinel    x->parent = parent     This.count = This.count + 1     ' insert node in tree    If (parent) Then        If (This.Compare(key, parent->key) < 0) Then            parent->izda = x        Else            parent->dcha = x        End If    Else        This.root = x    End If     This.insertFixup(x)    Return xEnd Function Sub RBTree.deleteFixup(Byval x As RBNode Ptr)    'maintain tree balance after deleting node x     Dim w As RBNode Ptr    While (x <> This.root Andalso x->kolor = BLACK)        If (x = x->parent->izda) Then            w = x->parent->dcha            If (w->kolor = RED) Then                w->kolor = BLACK                x->parent->kolor = RED                This.rotateLeft(x->parent)                w = x->parent->dcha            End If             If (w->izda->kolor = BLACK And w->dcha->kolor = BLACK) Then                w->kolor = RED                x = x->parent            Else                If (w->dcha->kolor = BLACK) Then                    w->izda->kolor = BLACK                    w->kolor = RED                    This.rotateRight(w)                    w = x->parent->dcha                End If                 w->kolor = x->parent->kolor                x->parent->kolor = BLACK                w->dcha->kolor = BLACK                This.rotateLeft(x->parent)                x = This.root            End If        Else            w = x->parent->izda            If (w->kolor = RED) Then                w->kolor = BLACK                x->parent->kolor = RED                This.rotateRight(x->parent)                w = x->parent->izda            End If             If (w->dcha->kolor = BLACK And w->izda->kolor = BLACK) Then                w->kolor = RED                x = x->parent            Else                If (w->izda->kolor = BLACK) Then                    w->dcha->kolor = BLACK                    w->kolor = RED                    This.rotateLeft(w)                    w = x->parent->izda                End If                 w->kolor = x->parent->kolor                x->parent->kolor = BLACK                w->izda->kolor = BLACK                This.rotateRight(x->parent)                x = This.root            End If        End If    Wend    x->kolor = BLACKEnd Sub Sub RBTree.deleteNode(Byval z As RBNode Ptr)    'delete node z from tree     Dim y As RBNode Ptr    Dim x As RBNode Ptr     If (0 =  z Orelse z = This.sentinel) Then Return     If (z->izda = This.sentinel Orelse z->dcha = This.sentinel) Then        'y has a This.sentinel node as a child        y = z    Else        'find tree successor with a This.sentinel node as a child        y = z->dcha        While (y->izda <> This.sentinel)            y = y->izda        Wend    End If     'x is y's only child    If (y->izda <> This.sentinel) Then        x = y->izda    Else        x = y->dcha    End If     'remove y from the parent chain    x->parent = y->parent    If (y->parent) Then        If (y = y->parent->izda) Then            y->parent->izda = x        Else            y->parent->dcha = x        End If    Else        This.root = x    End If     If (y <> z) Then          z->key = y->key        z->value = y->value    End If     If (y->kolor = BLACK) Then        This.deleteFixup(x)    End If     Delete y     This.count = This.count - 1End Sub Function RBtree.findNode(Byval key As Integer) As RBNode Ptr    'find node with key equal to key    Var current = This.root     While (current <> This.sentinel)        Var rc = This.Compare(key, current->key)        If (rc = 0) Then            Return current        Else            If (rc < 0) Then                current = current->izda            Else                current = current->dcha            End If        End If    Wend    Return 0End Function Type GraphicsNode    Dim node As RBNode Ptr      Dim lvl As Ubyte    Dim nxt As GraphicsNode Ptr    Dim prev As GraphicsNode Ptr    Dim x As Uinteger    Dim y As UintegerEnd Type Type NodeQueue    Dim startx As Integer    Dim starty As Integer    Dim first As GraphicsNode Ptr    Dim last  As GraphicsNode Ptr    Dim levels(2 To 11) As Integer => {100,50,25,12,10,10,10,10,10}    Dim count As Integer    Declare Constructor    Declare Destructor    Declare Function Enqueue(Byref item As GraphicsNode Ptr) As Integer    Declare Function Dequeue(Byref item As GraphicsNode Ptr) As GraphicsNode Ptr    Declare Sub PrintNode(Byval item As GraphicsNode Ptr, Byval x As Integer, Byval y As Integer)    Declare Sub PrintTree(Byval tree As RBTree Ptr)End Type Constructor NodeQueue()''Draw first node in the middle of the screen'(just below the top of the screen)    This.startx = 350    This.starty = 100    This.first = NULL    This.last = NULL      This.count = 1    '800x600, 32 bits kolor    Screen 19,32    color , Rgb(255,255,155)    Cls    WindowTitle "Red black tree sort"End Constructor Destructor NodeQueue() End Destructor Function NodeQueue.Enqueue(Byref item As GraphicsNode Ptr) As Integer    'Insertion into an empty que    If (This.first = NULL) Then        This.first = item        This.last = item        This.Count += 1        Return 0    Else        Var tmp = This.last        This.last = item        This.last->prev = tmp        tmp->nxt = This.last        This.last->nxt = NULL        This.Count += 1        Return 0    End If     Return -1    End Function Function NodeQueue.Dequeue(Byref item As GraphicsNode Ptr) As GraphicsNode Ptr    'Dequeueing from an empty queue or a queue with one node    If (This.last = This.first) Then        'Dequeueing from an empty queue        If (This.last = NULL) Then            This.Count -= 1            Return NULL        Else                  'Dequeueing from a queue with one node            item->node = This.First->node            item->x = This.First->x            item->y = This.First->y            item->lvl = This.first->lvl                  Delete This.first            This.first = NULL            This.last = NULL            This.Count -= 1            Return item        End If    Else          'Dequeueing from a queue with more than one node        Var tmp = This.Last        item->node = This.Last->node        item->x = This.Last->x        item->y = This.Last->y        item->lvl = This.Last->lvl              This.last = This.last->prev        This.last->nxt = NULL        Delete tmp        Return item    End If    Return NULLEnd Function Sub NodeQueue.PrintNode(Byval item As GraphicsNode Ptr, Byval x As Integer, Byval y As Integer)    'Draw a black line from parent node to child node    Line (x,y)-(item->x,item->y), Rgb(0,0,0)    'Draw node (either red or black)    If (item->node->kolor = RED) Then        Circle (item->x,item->y),5, Rgb(255,0,0),,,,F    Else        Circle (item->x,item->y),5, Rgb(0,0,0),,,,F    End If    Draw String (item->x,item->y - 40), Str(item->node->key), Rgb(0,0,0)    Draw String (item->x-8,item->y - 25),"""" & item->node->value & """", Rgb(0,0,0)End Sub Sub NodeQueue.PrintTree(Byval tree As RBTree Ptr)    Dim item As GraphicsNode Ptr     Dim current As GraphicsNode Ptr = New GraphicsNode      Dim tmp As GraphicsNode Ptr    Dim lvl As Integer = 1    Dim x As Integer = This.startx    Dim y As Integer = This.starty     'check for empty tree    If (tree->root = tree->sentinel) Then Return     'Start with printing the root    current->node = tree->root    current->x = x    current->y = y    current->lvl = lvl      This.PrintNode(current,x,y)    Do        'Print izda node (position it at izda side of current node)        If (current->node->izda <> tree->sentinel) Then            item = New GraphicsNode            item->lvl = lvl + 1                  If (item->lvl <= 9) Then                item->x = x - This.levels(lvl+1)            Else                item->x = x - 10            End If            item->y = y + 50            item->node = current->node->izda            This.PrintNode(item,x,y)            This.Enqueue(item)        End If        'Print dcha node (position it at dcha side of current node        If (current->node->dcha <> tree->sentinel) Then            item = New GraphicsNode            item->lvl = lvl + 1            If (item->lvl <= 9) Then                item->x = x + This.levels(lvl+1)            Else                item->x = x + 10            End If            item->y = y + 50            item->node = current->node->dcha            This.PrintNode(item,x,y)            This.Enqueue(item)        End If        'Continue drawing from first node in the queue        'Nodes in izda tree will be drawn first as these are put in        'the queue first        Var tmp = This.Dequeue(current)        'If count smaller then entire tree has been drawn        If (This.count < 1) Then Exit Do        x = current->x        y = current->y        lvl = current->lvl    LoopEnd Sub       Dim x As Integer PtrDim i As IntegerVar tree = New RBTree(@integer_compare) Open Cons For Output As #1For i = 0 To 29    Print #1, "Insert "; i    tree->Insertnode(i,Str(i))    Sleep()    Dim print_tree As NodeQueue Ptr    print_tree = New NodeQueue    print_tree->PrintTree(tree)    Delete print_tree  Next i Print #1, !"\nStarting Deletion after keypress"Var print_tree = New NodeQueueprint_tree->PrintTree(tree)Sleep()Delete print_tree randomize timerFor i = 0 To 14    Dim as integer j = int(rnd * 15) + int(rnd * 16)    Print #1, "Delete"; j    Var n = tree->FindNode(j)    If (n) Then tree->Deletenode(n)    Sleep()    Dim print_tree As NodeQueue Ptr    print_tree = New NodeQueue    print_tree->PrintTree(tree)    Delete print_tree  Next i Bsave "FreeBASIC_Red-black-tree_sort.bmp", 0Print #1, !"\nEnding program after keypress"Sleep()Close #1Delete tree`
Output:

## Python

This is based on the code of Shivali Bhadaniya , which I thought was reasonably intelligible.

`#!/usr/bin/python # Define Nodeclass Node():    def __init__(self,val):        self.val = val                                   # Value of Node        self.parent = None                               # Parent of Node        self.left = None                                 # Left Child of Node        self.right = None                                # Right Child of Node        self.color = 1                                   # Red Node as new node is always inserted as Red Node # Define R-B Treeclass RBTree():    def __init__(self):        self.NULL = Node ( 0 )        self.NULL.color = 0        self.NULL.left = None        self.NULL.right = None        self.root = self.NULL      # Insert New Node    def insertNode(self, key):        node = Node(key)        node.parent = None        node.val = key        node.left = self.NULL        node.right = self.NULL        node.color = 1                                   # Set root colour as Red         y = None        x = self.root         while x != self.NULL :                           # Find position for new node            y = x            if node.val < x.val :                x = x.left            else :                x = x.right         node.parent = y                                  # Set parent of Node as y        if y == None :                                   # If parent i.e, is none then it is root node            self.root = node        elif node.val < y.val :                          # Check if it is right Node or Left Node by checking the value            y.left = node        else :            y.right = node         if node.parent == None :                         # Root node is always Black            node.color = 0            return         if node.parent.parent == None :                  # If parent of node is Root Node            return         self.fixInsert ( node )                          # Else call for Fix Up      def minimum(self, node):        while node.left != self.NULL:            node = node.left        return node      # Code for left rotate    def LR ( self , x ) :        y = x.right                                      # Y = Right child of x        x.right = y.left                                 # Change right child of x to left child of y        if y.left != self.NULL :            y.left.parent = x         y.parent = x.parent                              # Change parent of y as parent of x        if x.parent == None :                            # If parent of x == None ie. root node            self.root = y                                # Set y as root        elif x == x.parent.left :            x.parent.left = y        else :            x.parent.right = y        y.left = x        x.parent = y      # Code for right rotate    def RR ( self , x ) :        y = x.left                                       # Y = Left child of x        x.left = y.right                                 # Change left child of x to right child of y        if y.right != self.NULL :            y.right.parent = x         y.parent = x.parent                              # Change parent of y as parent of x        if x.parent == None :                            # If x is root node            self.root = y                                # Set y as root        elif x == x.parent.right :            x.parent.right = y        else :            x.parent.left = y        y.right = x        x.parent = y      # Fix Up Insertion    def fixInsert(self, k):        while k.parent.color == 1:                        # While parent is red            if k.parent == k.parent.parent.right:         # if parent is right child of its parent                u = k.parent.parent.left                  # Left child of grandparent                if u.color == 1:                          # if color of left child of grandparent i.e, uncle node is red                    u.color = 0                           # Set both children of grandparent node as black                    k.parent.color = 0                    k.parent.parent.color = 1             # Set grandparent node as Red                    k = k.parent.parent                   # Repeat the algo with Parent node to check conflicts                else:                    if k == k.parent.left:                # If k is left child of it's parent                        k = k.parent                        self.RR(k)                        # Call for right rotation                    k.parent.color = 0                    k.parent.parent.color = 1                    self.LR(k.parent.parent)            else:                                         # if parent is left child of its parent                u = k.parent.parent.right                 # Right child of grandparent                if u.color == 1:                          # if color of right child of grandparent i.e, uncle node is red                    u.color = 0                           # Set color of childs as black                    k.parent.color = 0                    k.parent.parent.color = 1             # set color of grandparent as Red                    k = k.parent.parent                   # Repeat algo on grandparent to remove conflicts                else:                    if k == k.parent.right:               # if k is right child of its parent                        k = k.parent                        self.LR(k)                        # Call left rotate on parent of k                    k.parent.color = 0                    k.parent.parent.color = 1                    self.RR(k.parent.parent)              # Call right rotate on grandparent            if k == self.root:                            # If k reaches root then break                break        self.root.color = 0                               # Set color of root as black      # Function to fix issues after deletion    def fixDelete ( self , x ) :        while x != self.root and x.color == 0 :           # Repeat until x reaches nodes and color of x is black            if x == x.parent.left :                       # If x is left child of its parent                s = x.parent.right                        # Sibling of x                if s.color == 1 :                         # if sibling is red                    s.color = 0                           # Set its color to black                    x.parent.color = 1                    # Make its parent red                    self.LR ( x.parent )                  # Call for left rotate on parent of x                    s = x.parent.right                # If both the child are black                if s.left.color == 0 and s.right.color == 0 :                    s.color = 1                           # Set color of s as red                    x = x.parent                else :                    if s.right.color == 0 :               # If right child of s is black                        s.left.color = 0                  # set left child of s as black                        s.color = 1                       # set color of s as red                        self.RR ( s )                     # call right rotation on x                        s = x.parent.right                     s.color = x.parent.color                    x.parent.color = 0                    # Set parent of x as black                    s.right.color = 0                    self.LR ( x.parent )                  # call left rotation on parent of x                    x = self.root            else :                                        # If x is right child of its parent                s = x.parent.left                         # Sibling of x                if s.color == 1 :                         # if sibling is red                    s.color = 0                           # Set its color to black                    x.parent.color = 1                    # Make its parent red                    self.RR ( x.parent )                  # Call for right rotate on parent of x                    s = x.parent.left                 if s.right.color == 0 and s.right.color == 0 :                    s.color = 1                    x = x.parent                else :                    if s.left.color == 0 :                # If left child of s is black                        s.right.color = 0                 # set right child of s as black                        s.color = 1                        self.LR ( s )                     # call left rotation on x                        s = x.parent.left                     s.color = x.parent.color                    x.parent.color = 0                    s.left.color = 0                    self.RR ( x.parent )                    x = self.root        x.color = 0      # Function to transplant nodes    def __rb_transplant ( self , u , v ) :        if u.parent == None :            self.root = v        elif u == u.parent.left :            u.parent.left = v        else :            u.parent.right = v        v.parent = u.parent      # Function to handle deletion    def delete_node_helper ( self , node , key ) :        z = self.NULL        while node != self.NULL :                          # Search for the node having that value/ key and store it in 'z'            if node.val == key :                z = node             if node.val <= key :                node = node.right            else :                node = node.left         if z == self.NULL :                                # If Kwy is not present then deletion not possible so return            print ( "Value not present in Tree !!" )            return         y = z        y_original_color = y.color                          # Store the color of z- node        if z.left == self.NULL :                            # If left child of z is NULL            x = z.right                                     # Assign right child of z to x            self.__rb_transplant ( z , z.right )            # Transplant Node to be deleted with x        elif (z.right == self.NULL) :                       # If right child of z is NULL            x = z.left                                      # Assign left child of z to x            self.__rb_transplant ( z , z.left )             # Transplant Node to be deleted with x        else :                                              # If z has both the child nodes            y = self.minimum ( z.right )                    # Find minimum of the right sub tree            y_original_color = y.color                      # Store color of y            x = y.right            if y.parent == z :                              # If y is child of z                x.parent = y                                # Set parent of x as y            else :                self.__rb_transplant ( y , y.right )                y.right = z.right                y.right.parent = y             self.__rb_transplant ( z , y )            y.left = z.left            y.left.parent = y            y.color = z.color        if y_original_color == 0 :                          # If color is black then fixing is needed            self.fixDelete ( x )      # Deletion of node    def delete_node ( self , val ) :        self.delete_node_helper ( self.root , val )         # Call for deletion      # Function to print    def __printCall ( self , node , indent , last ) :        if node != self.NULL :            print(indent, end=' ')            if last :                print ("R----",end= ' ')                indent += "     "            else :                print("L----",end=' ')                indent += "|    "             s_color = "RED" if node.color == 1 else "BLACK"            print ( str ( node.val ) + "(" + s_color + ")" )            self.__printCall ( node.left , indent , False )            self.__printCall ( node.right , indent , True )     # Function to call print    def print_tree ( self ) :        self.__printCall ( self.root , "" , True )  if __name__ == "__main__":    bst = RBTree()     print("State of the tree after inserting the 30 keys:")    for x in range(1, 30):        bst.insertNode(x)    bst.print_tree()     print("\nState of the tree after deleting the 15 keys:")    for x in range(1, 15):        bst.delete_node(x)    bst.print_tree() `
Output:
```State of the tree after inserting the 30 keys:
R---- 8(BLACK)
L---- 4(BLACK)
|     L---- 2(BLACK)
|    |     L---- 1(BLACK)
|    |     R---- 3(BLACK)
|     R---- 6(BLACK)
|          L---- 5(BLACK)
|          R---- 7(BLACK)
R---- 16(BLACK)
L---- 12(RED)
|     L---- 10(BLACK)
|    |     L---- 9(BLACK)
|    |     R---- 11(BLACK)
|     R---- 14(BLACK)
|          L---- 13(BLACK)
|          R---- 15(BLACK)
R---- 20(RED)
L---- 18(BLACK)
|     L---- 17(BLACK)
|     R---- 19(BLACK)
R---- 24(BLACK)
L---- 22(RED)
|     L---- 21(BLACK)
|     R---- 23(BLACK)
R---- 26(RED)
L---- 25(BLACK)
R---- 28(BLACK)
L---- 27(RED)
R---- 29(RED)

State of the tree after deleting the 15 keys:
R---- 20(BLACK)
L---- 16(BLACK)
|     L---- 15(BLACK)
|     R---- 18(RED)
|          L---- 17(BLACK)
|          R---- 19(BLACK)
R---- 24(BLACK)
L---- 22(RED)
|     L---- 21(BLACK)
|     R---- 23(BLACK)
R---- 26(RED)
L---- 25(BLACK)
R---- 28(BLACK)
L---- 27(RED)
R---- 29(RED)```