Jump to content

Red black tree sort

From Rosetta Code
Revision as of 19:04, 18 June 2023 by Lscrd (talk | contribs) (Created Nim solution.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

This task extends Algebraic data types#F.23 adding the following functions:

// Red black tree sort. Nigel Galloway: June 17th., 2022
let fromSeq n=n|>Seq.fold(fun n g->insert g n) Empty
let 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 g
let delSeq n g=toSeq g|>Seq.except n|>fromSeq
let 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" |_->()

The Task

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] n
printfn "\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 = 1
End 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 = 1
End 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 If
End 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 = cmp
End 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 If
End 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 If
End 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 If
End 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 = BLACK
End 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 x
End 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 = BLACK
End 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 - 1
End 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 0
End 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 Uinteger
End 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 NULL
End 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
    Loop
End Sub      

Dim x As Integer Ptr
Dim i As Integer
Var tree = New RBTree(@integer_compare)

Open Cons For Output As #1
For 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 NodeQueue
print_tree->PrintTree(tree)
Sleep()
Delete print_tree

randomize timer
For 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", 0
Print #1, !"\nEnding program after keypress"
Sleep()
Close #1
Delete tree
Output:

FreeBasic Red black tree sort image

Julia

See Red_black_tree_sort/Julia.

Nim

Translation of: Python
import std/strformat

type

  Color {.pure.} = enum Black = "BLACK", Red = "RED"

  Node = ref object
    val: Positive   # Value of node.
    parent: Node    # Parent of node.
    left: Node      # Left child of node.intint
    right: Node     # Right child of node.
    color: Color    # Color of node.

  RBTree = object
    null: Node
    root: Node


func initRBTree(): RBTree =
  result.null = Node(val: 0, color: Black)
  result.root = result.null


func leftRotate(tree: var RBTree; x: Node) =

  let y = x.right
  x.right = y.left              # Change right child of x to left child of y.
  if y.left != tree.null:
    y.left.parent = x

  y.parent = x.parent           # Change parent of y as parent of x.
  if x.parent.isNil:
    tree.root = y
  elif x == x.parent.left:
    x.parent.left = y
  else:
    x.parent.right = y
  y.left = x
  x.parent = y


func rightRotate(tree: var RBTree; x: Node) =

  let y = x.left
  x.left = y.right              # Change left child of x to right child of y.
  if y.right != tree.null:
    y.right.parent = x

  y.parent = x.parent           # Change parent of y as parent of x.
  if x.parent.isNil:
    tree.root = y
  elif x == x.parent.right:
    x.parent.right = y
  else :
    x.parent.left = y
  y.right = x
  x.parent = y


func fixInsert(tree: var RBTree; k: Node) =
  ## Fix up insertion.
  var k = k
  while k.parent.color == Red:
    if k.parent == k.parent.parent.right:
      let u = k.parent.parent.left
      if u.color == Red:
        u.color = Black
        k.parent.color = Black
        k.parent.parent.color = Red
        k = k.parent.parent         # Repeat the algorithm with parent node to check conflicts.
      else:
        if k == k.parent.left:
          k = k.parent
          tree.rightRotate(k)
        k.parent.color = Black
        k.parent.parent.color = Red
        tree.leftRotate(k.parent.parent)
    else:
      let u = k.parent.parent.right
      if u.color == Red:
        u.color = Black
        k.parent.color = Black
        k.parent.parent.color = Red
        k = k.parent.parent         # Repeat algorithm on grandparent to remove conflicts.
      else:
        if k == k.parent.right:
          k = k.parent
          tree.leftRotate(k)
        k.parent.color = Black
        k.parent.parent.color = Red
        tree.rightRotate(k.parent.parent)
    if k == tree.root:
      break
  tree.root.color = Black


func fixDelete (tree: var RBTree; x: Node) =
  ## Fix issues after deletion.

  var x = x
  while x != tree.root and x.color == Black:
    if x == x.parent.left:
      var s = x.parent.right
      if s.color == Red :
        s.color = Black
        x.parent.color = Red
        tree.leftRotate(x.parent)
        s = x.parent.right
      if s.left.color == Black and s.right.color == Black :
        s.color = Red
        x = x.parent
      else :
        if s.right.color == Black :
          s.left.color = Black
          s.color = Red
          tree.rightRotate(s)
          s = x.parent.right

        s.color = x.parent.color
        x.parent.color = Black
        s.right.color = Black
        tree.leftRotate(x.parent)
        x = tree.root
    else :
      var s = x.parent.left
      if s.color == Red:
        s.color = Black
        x.parent.color = Red
        tree.rightRotate(x.parent)
        s = x.parent.left

      if s.right.color == Black and s.right.color == Black:
        s.color = Red
        x = x.parent
      else :
        if s.left.color == Black:
          s.right.color = Black
          s.color = Red
          tree.leftRotate(s)
          s = x.parent.left

        s.color = x.parent.color
        x.parent.color = Black
        s.left.color = Black
        tree.rightRotate(x.parent)
        x = tree.root
  x.color = Black


func insert(tree: var RBTree; key: Positive) =
  ## Insert a new node.

  let node = Node(val: key, left: tree.null, right: tree.null, color: Red)

  # Find position for new node.
  var y: Node
  var x = tree.root
  while x != tree.null:
    y = x
    x = if node.val < x.val: x.left
        else: x.right

  node.parent = y
  if y.isNil:
    # If parent is nil then it is the root node.
    tree.root = node
  elif node.val < y.val:
    y.left = node
  else:
    y.right = node

  if node.parent.isNil:
    node.color = Black    # Root node is always black.
    return

  if node.parent.parent.isNil:
    # If parent node is the root node.
    return

  tree.fixInsert(node)


func min(tree: RBTree; node: Node): Node =
  result = node
  while result.left != tree.null:
    result = result.left


func rbTransplant(tree: var RBTree; u, v: Node) =
  ## Transplant nodes.
  if u.parent.isNil:
    tree.root = v
  elif u == u.parent.left:
    u.parent.left = v
  else:
    u.parent.right = v
  v.parent = u.parent


proc deleteHelper(tree: var RBTree; node: Node; key: Positive) =
  ## Function to handle deletion.

  var node = node
  var z = tree.null
  while node != tree.null:  # Search for the node having that value/key and store it in 'z'.
    if node.val == key:
      z = node
    node = if node.val <= key: node.right
           else: node.left

  if z == tree.null:        # If key is not present then deletion is not possible so return.
    echo "Value not present in tree!"
    return

  var x: Node
  var y = z
  var yOriginalColor = y.color
  if z.left == tree.null:
    x = z.right
    tree.rbTransplant(z, x)             # Transplant node to be deleted with x.
  elif (z.right == tree.null):
    x = z.left
    tree.rbTransplant(z, x)             # Transplant node to be deleted with x.
  else :
    y = tree.min(z.right)
    yOriginalColor = y.color
    x = y.right
    if y.parent == z:
      x.parent = y
    else:
      tree.rbTransplant(y, y.right)
      y.right = z.right
      y.right.parent = y

    tree.rbTransplant(z, y)
    y.left = z.left
    y.left.parent = y
    y.color = z.color
  if yOriginalColor == Black:           # If color is black then fixing is needed
    tree.fixDelete(x)


proc delete(tree: var RBTree; val: Positive)  =
  # Delete a node.
  tree.deleteHelper(tree.root, val)


proc print(tree: RBTree; node: Node; indent: string; last: bool) =
  ## Print part of a tree.

  var indent = indent
  if node != tree.null:
    stdout.write indent, ' '
    if last:
      stdout.write "R----", ' '
      indent.add "     "
    else :
      stdout.write "L----", ' '
      indent.add "|    "

    echo &"{node.val}({node.color})"
    tree.print(node.left, indent, false)
    tree.print(node.right, indent, true)


proc print(tree: RBTree) =
  ## Print a tree.
  tree.print(tree.root, "", true)


when isMainModule:

  var bst = initRBTree()

  echo "State of the tree after inserting the 30 keys:"
  for x in 1..30:
    bst.insert(x)
  bst.print()

  echo "\nState of the tree after deleting the 15 keys:"
  for x in 1..15:
    bst.delete(x)
  bst.print()
Output:

Note that the Python program inserts only 29 nodes and deletes only 14 nodes which explains why we get a different result.

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(RED)
           L---- 12(BLACK)
          |     L---- 10(BLACK)
          |    |     L---- 9(BLACK)
          |    |     R---- 11(BLACK)
          |     R---- 14(BLACK)
          |          L---- 13(BLACK)
          |          R---- 15(BLACK)
           R---- 20(BLACK)
                L---- 18(BLACK)
               |     L---- 17(BLACK)
               |     R---- 19(BLACK)
                R---- 24(RED)
                     L---- 22(BLACK)
                    |     L---- 21(BLACK)
                    |     R---- 23(BLACK)
                     R---- 26(BLACK)
                          L---- 25(BLACK)
                          R---- 28(RED)
                               L---- 27(BLACK)
                               R---- 29(BLACK)
                                    R---- 30(RED)

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

Phix

See Red_black_tree_sort/Phix.

Python

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

#!/usr/bin/python

# Define Node
class 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 Tree
class 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)

Wren

See Red_black_tree_sort/Wren.

Cookies help us deliver our services. By using our services, you agree to our use of cookies.