Red black tree sort: Difference between revisions

===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 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"

{{out}}

<pre>

Code originally by AGS.

https://www.freebasic.net/forum/viewtopic.php?t=16113

 

Enum nodecolor

Sleep()

Close #1

{{out}}

[https://www.dropbox.com/s/hbrtaahsd6jmlyl/FreeBASIC_Red-black-tree_sort.bmp?dl=0 FreeBasic Red black tree sort image]

=={{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

bst.delete_node(x)

bst.print_tree()

{{out}}

<pre>State of the tree after inserting the 30 keys: