Red black tree sort: Difference between revisions
Content added Content deleted
m (safe some people some headaches) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 15: | Line 15: | ||
===The Functions=== |
===The Functions=== |
||
This task extends [[Algebraic data types#F.23]] adding the following 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 |
// Red black tree sort. Nigel Galloway: June 17th., 2022 |
||
let fromSeq n=n|>Seq.fold(fun n g->insert g n) Empty |
let fromSeq n=n|>Seq.fold(fun n g->insert g n) Empty |
||
Line 21: | Line 21: | ||
let delSeq n g=toSeq g|>Seq.except n|>fromSeq |
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" |_->() |
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> |
|||
</lang> |
|||
===The Task=== |
===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] |
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" |
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 |
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" |
printfn "\nRed Black Tree after deletions"; printN g "" "X" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 83: | Line 83: | ||
Code originally by AGS. |
Code originally by AGS. |
||
https://www.freebasic.net/forum/viewtopic.php?t=16113 |
https://www.freebasic.net/forum/viewtopic.php?t=16113 |
||
< |
<syntaxhighlight lang="freebasic">#define NULL Cast(Any Ptr,0) |
||
Enum nodecolor |
Enum nodecolor |
||
Line 679: | Line 679: | ||
Sleep() |
Sleep() |
||
Close #1 |
Close #1 |
||
Delete tree</ |
Delete tree</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://www.dropbox.com/s/hbrtaahsd6jmlyl/FreeBASIC_Red-black-tree_sort.bmp?dl=0 FreeBasic Red black tree sort image] |
[https://www.dropbox.com/s/hbrtaahsd6jmlyl/FreeBASIC_Red-black-tree_sort.bmp?dl=0 FreeBasic Red black tree sort image] |
||
Line 691: | Line 691: | ||
=={{header|Python}}== |
=={{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. |
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 |
# Define Node |
||
Line 971: | Line 971: | ||
bst.delete_node(x) |
bst.delete_node(x) |
||
bst.print_tree() |
bst.print_tree() |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>State of the tree after inserting the 30 keys: |
<pre>State of the tree after inserting the 30 keys: |