Skip to content

Instantly share code, notes, and snippets.

@Ovid
Created February 17, 2013 13:59
Show Gist options
  • Select an option

  • Save Ovid/4971599 to your computer and use it in GitHub Desktop.

Select an option

Save Ovid/4971599 to your computer and use it in GitHub Desktop.
Reformatted for for red-black tree in Perl 6
enum RedBlack <R B>;
sub MAIN {
my $tree = Any;
for (1..10).pick(*) -> $node {
$tree = insert($node, $tree);
printf "%2d: %s\n", $node, $tree.perl;
}
}
multi insert( $node, $tree ) {
[B, ins( $node, $tree )[1..3]];
}
multi ins( $node, Any:U ) { [R, Any, $node, Any] }
multi ins( $node, @tree [RedBlack $color, $left, $pivot, $right] ) {
when $node before $pivot { balance $color, ins($node, $left), $pivot, $right }
when $node after $pivot { balance $color, $left, $pivot, ins($node, $right) }
default { @tree }
}
multi balance(RedBlack $color, $a, $x, $b) { [$color, $a, $x, $b] }
multi balance(B, [R, [R,$a,$x,$b], $y, $c ], $pivot, $right ) {
[ R, [B,$a,$x,$b], $y, [B,$c,$pivot,$right]]
}
multi balance(B, [R, $a, $x, [R,$b,$y,$c] ], $pivot, $right ) {
[ R, [B,$a,$x,$b], $y, [B,$c,$pivot,$right]]
}
multi balance(B, $left, $pivot, [R, [R,$b,$y,$c], $z, $d] ) {
[ R, [B,$left,$pivot,$b], $y, [B,$c,$z,$d]]
}
multi balance(B, $left, $pivot, [R, $b, $y, [R,$c,$z,$d] ]) {
[ R, [B,$left,$pivot,$b], $y, [B,$c,$z,$d]]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment