Red black tree sort/Phix: Difference between revisions
Content added Content deleted
m (50/25 -> 30/15) |
(oops) |
||
Line 1: | Line 1: | ||
{{incorrect|Phix|Oh dear}} |
|||
Didn't check carefully enough... it seems to actally work ok about 3/4 in the 50:25 case, almost never in the 30:15 case...<br> |
|||
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> |
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 clarity, either copy in the first hundred lines or so from the other task, or use the runnable version in the distro. |
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. |
Revision as of 10:43, 16 June 2022
Didn't check carefully enough... it seems to actally work ok about 3/4 in the 50:25 case, almost never in the 30:15 case...
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