90 lines
1.8 KiB
Text
90 lines
1.8 KiB
Text
insert=: {{
|
|
X=.1 {::2{.x,x NB. middle element of x (don't fail on empty x)
|
|
Y=.1 {::2{.y,y NB. middle element of y (don't fail on empty y)
|
|
select.#y
|
|
case.0 do.x NB. y is an empty node
|
|
case.1 do. NB. y is a leaf node
|
|
select.*Y-X
|
|
case._1 do.a:,y;<x
|
|
case. 0 do.y
|
|
case. 1 do.x;y;a:
|
|
end.
|
|
case.3 do. NB. y is a parent node
|
|
select.*Y-X
|
|
case._1 do.balance (}:y),<x insert 2{::y
|
|
case. 0 do.y
|
|
case. 1 do.balance (x insert 0{::y);}.y
|
|
end.
|
|
end.
|
|
}}
|
|
|
|
delete=: {{
|
|
select.#y
|
|
case.0 do.y
|
|
case.1 do.y-.x
|
|
case.3 do.
|
|
select.*(1{::y)-x
|
|
case._1 do.balance (}:y),<x delete 2{::y
|
|
case. 0 do.balance (0{::y) insert 2{::y
|
|
case. 1 do.balance (x delete 0{::y);}.y
|
|
end.
|
|
end.
|
|
}}
|
|
|
|
lookup=: {{
|
|
select.#y
|
|
case.0 do.y
|
|
case.1 do.if.x=y do.y else.'' end.
|
|
case.3 do.
|
|
select.*(1{::y)-x
|
|
case._1 do.x lookup 2{::y
|
|
case. 0 do.y
|
|
case. 1 do.x lookup 0{::y
|
|
end.
|
|
end.
|
|
}}
|
|
|
|
clean=: {{
|
|
's0 x s2'=. #every y
|
|
if.*/0=s0,s2 do. 1{:: y NB. degenerate to leaf
|
|
else. y end.
|
|
}}
|
|
|
|
balance=: {{
|
|
if. 2>#y do. y return.end. NB. leaf or empty
|
|
's0 x s2'=. ,#every y
|
|
if. */0=s0,s2 do. 1{:: y return.end. NB. degenerate to leaf
|
|
'l0 x l2'=. L.every y
|
|
if. 2>|l2-l0 do. y return.end. NB. adequately balanced
|
|
if. l2>l0 do.
|
|
'l20 x l22'=. L.every 2{::y
|
|
if. l22 >: l20 do. rotLeft y
|
|
else. rotRightLeft y end.
|
|
else.
|
|
'l00 x l02'=. L.every 0{::y
|
|
if. l00 >: l02 do. rotRight y
|
|
else. rotLeftRight y end.
|
|
end.
|
|
}}
|
|
|
|
rotLeft=: {{
|
|
't0 t1 t2'=. y
|
|
't20 t21 t22'=. t2
|
|
(clean t0;t1;<t20);t21;<t22
|
|
}}
|
|
|
|
rotRight=: {{
|
|
't0 t1 t2'=. y
|
|
't00 t01 t02'=. t0
|
|
t00;t01;<clean t02;t1;<t2
|
|
}}
|
|
|
|
rotRightLeft=: {{
|
|
't0 t1 t2'=. y
|
|
rotLeft t0;t1;<rotRight t2
|
|
}}
|
|
|
|
rotLeftRight=: {{
|
|
't0 t1 t2'=. y
|
|
rotRight (rotLeft t0);t1;<t2
|
|
}}
|