Red black tree sort: Difference between revisions
Created Nim solution.
(Created Nim solution.) |
|||
| (8 intermediate revisions by 6 users not shown) | |||
Line 9:
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.
=={{header|F_Sharp|F#}}==
===The Functions===
This task extends [[Algebraic data types#F.23]] adding the following functions:
<syntaxhighlight lang="fsharp">
// 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" |_->()
</syntaxhighlight>
===The Task===
<syntaxhighlight lang="fsharp">
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"
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|FreeBASIC}}==
Code originally by AGS.
https://www.freebasic.net/forum/viewtopic.php?t=16113
<syntaxhighlight lang="freebasic">#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</syntaxhighlight>
{{out}}
[https://www.dropbox.com/s/hbrtaahsd6jmlyl/FreeBASIC_Red-black-tree_sort.bmp?dl=0 FreeBasic Red black tree sort image]
=={{header|Julia}}==
See [[Red_black_tree_sort/Julia]].
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="Nim">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()
</syntaxhighlight>
{{out}}
Note that the Python program inserts only 29 nodes and deletes only 14 nodes which explains why we get a different result.
<pre>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)
</pre>
=={{header|Phix}}==
See [[Red_black_tree_sort/Phix]].
=={{header|Python}}==
This is based on the code of Shivali Bhadaniya [https://favtutor.com/blogs/red-black-tree-python], which I thought was reasonably intelligible.
<syntaxhighlight lang="python">#!/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()
</syntaxhighlight>
{{out}}
<pre>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)</pre>
=={{header|Wren}}==
See [[Red_black_tree_sort/Wren]].
| |||