42 lines
1.0 KiB
Plaintext
42 lines
1.0 KiB
Plaintext
constant B = "B", R = "R"
|
|
|
|
function balance(sequence t)
|
|
sequence s = match_algebraic({{B,{R,{R,0,0,0},0,0},0,0},
|
|
{B,{R,0,0,{R,0,0,0}},0,0},
|
|
{B,0,0,{R,{R,0,0,0},0,0}},
|
|
{B,0,0,{R,0,0,{R,0,0,0}}}},t)
|
|
if length(s) then
|
|
object {a,x,b,y,c,z,d} = s
|
|
t = {R,{B,a,x,b},y,{B,c,z,d}}
|
|
end if
|
|
return t
|
|
end function
|
|
|
|
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, object leaf)
|
|
tree = ins(tree,leaf)
|
|
tree[1] = B
|
|
return tree
|
|
end function
|
|
|
|
sequence stuff = shuffle(tagset(10))
|
|
object tree = NULL
|
|
for i=1 to length(stuff) do
|
|
tree = tree_insert(tree,stuff[i])
|
|
end for
|
|
visualise_tree(tree)
|