Red black tree sort/Phix: Difference between revisions
Content added Content deleted
(Created page with "Since I was invited to and it was about a zillion times easier, I simply added delete routines to the Algebraic data types#Phix task.<br> Unchanged code omitted for clari...") |
m (50/25 -> 30/15) |
||
Line 82: | Line 82: | ||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stuff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;"> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stuff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30</span><span style="color: #0000FF;">))</span> |
||
<span style="color: #004080;">object</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span> |
<span style="color: #004080;">object</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #000000;">stuff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;"> |
<span style="color: #000000;">stuff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">15</span><span style="color: #0000FF;">]</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_delete</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_delete</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
||
Line 97: | Line 97: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
┌B3 |
|||
│└B4 |
|||
┌B7 |
|||
⚫ | |||
⚫ | |||
┌B6 |
|||
⚫ | |||
││┌B9 |
|||
┌B12 |
|||
⚫ | |||
││ ┌B13 |
|||
⚫ | |||
││┌B15 |
|||
─B15 |
|||
│└B19 |
|||
│┌B17 |
|||
⚫ | |||
└B19 |
|||
─B23 |
|||
│ ┌B20 |
|||
│┌B22 |
|||
│ │└R25 |
|||
└R24 |
|||
│┌B31 |
|||
└B27 |
|||
│││┌B32 |
|||
└B30 |
|||
││└R33 |
|||
││ └B34 |
|||
└B35 |
|||
│ ┌R36 |
|||
│ ┌B37 |
|||
│┌B40 |
|||
└B43 |
|||
│┌B45 |
|||
└R48 |
|||
└B49 |
|||
└B50 |
|||
</pre> |
</pre> |
Revision as of 10:08, 16 June 2022
Since I was invited to and it was about a zillion times easier, I simply added delete routines to the Algebraic data types#Phix task.
Unchanged code omitted for clarity, either copy in the first hundred lines or so from the other task, or use the runnable version in the distro.
-- demo\rosetta\Red_Black_Tree.exw with javascript_semantics enum CLR, LEFT, DATA, RIGHT function ins(object tree, object leaf) if tree=NULL then tree = {R,NULL,leaf,NULL} else object {c,l,k,r} = tree if leaf!=k then if leaf<k then l = ins(l,leaf) else r = ins(r,leaf) end if tree = balance({c,l,k,r}) end if end if return tree end function function tree_insert(object tree, leaf) tree = ins(tree,leaf) tree[1] = B return tree end function object lm function leftmost(object tree) -- set lm and return tree with that removed object l = tree[LEFT] if l=NULL then lm = tree[DATA] tree = tree[RIGHT] else tree[LEFT] = NULL -- (kill refcount) l = leftmost(l) tree[LEFT] = l end if if tree!=NULL then tree = balance(tree) end if return tree end function function del(object tree, object leaf) if tree!=NULL then object {c,l,k,r} = tree tree = NULL if leaf=k then if l=NULL then tree = r elsif r=NULL then tree = l else r = leftmost(r) k = lm tree = {c,l,k,r} end if else if leaf<k then l = del(l,leaf) else r = del(r,leaf) end if tree = {c,l,k,r} end if if tree!=NULL then tree = balance(tree) end if end if return tree end function function tree_delete(object tree, leaf) tree = del(tree,leaf) tree[1] = B return tree end function procedure main() sequence stuff = shuffle(tagset(30)) object tree = NULL for i=1 to length(stuff) do tree = tree_insert(tree,stuff[i]) end for stuff = shuffle(stuff)[1..15] for i=1 to length(stuff) do tree = tree_delete(tree,stuff[i]) end for visualise_tree(tree) end procedure main()
- Output:
┌B3 │└B4 │ └R5 ┌B6 ││┌B9 │└R10 │ └B11 ─B15 │┌B17 └B19 │ ┌B20 │┌B22 └R24 └B27 └B30