Red black tree sort: Difference between revisions
Created Nim solution.
m (safe some people some headaches) |
(Created Nim solution.) |
||
| (One intermediate revision by one other user not shown) | |||
Line 15:
===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
Line 21:
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===
<
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>
Line 83:
Code originally by AGS.
https://www.freebasic.net/forum/viewtopic.php?t=16113
<
Enum nodecolor
Line 679:
Sleep()
Close #1
Delete tree</
{{out}}
[https://www.dropbox.com/s/hbrtaahsd6jmlyl/FreeBASIC_Red-black-tree_sort.bmp?dl=0 FreeBasic Red black tree sort image]
Line 685:
=={{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}}==
Line 691 ⟶ 1,030:
=={{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.
<
# Define Node
Line 971 ⟶ 1,310:
bst.delete_node(x)
bst.print_tree()
</syntaxhighlight>
{{out}}
<pre>State of the tree after inserting the 30 keys:
| |||