AVL tree: Difference between revisions
Content added Content deleted
m (→{{header|J}}) |
m (J: add some rudimentary comments) |
||
| Line 5,073: | Line 5,073: | ||
clean=: {{ |
clean=: {{ |
||
's0 x s2'=. #every y |
's0 x s2'=. #every y |
||
if.*/0=s0,s2 do. |
if.*/0=s0,s2 do. 1{:: y NB. degenerate to leaf |
||
else. y end. |
|||
else. |
|||
y |
|||
end. |
|||
}} |
}} |
||
balance=: {{ |
balance=: {{ |
||
if.2>#y do.y return.end. |
if. 2>#y do. y return.end. NB. leaf or empty |
||
's0 x s2'=. ,#every y |
's0 x s2'=. ,#every y |
||
if.*/0=s0,s2 do. |
if. */0=s0,s2 do. 1{:: y return.end. NB. degenerate to leaf |
||
1{:: y return. |
|||
end. |
|||
'l0 x l2'=. L.every y |
'l0 x l2'=. L.every y |
||
if.2>|l2-l0 do.y return.end. |
if. 2>|l2-l0 do. y return.end. NB. adequately balanced |
||
if.l2>l0 do. |
if. l2>l0 do. |
||
'l20 x l22'=. L.every 2{::y |
'l20 x l22'=. L.every 2{::y |
||
if.l22 >: l20 do. |
if. l22 >: l20 do. rotLeft y |
||
else. rotRightLeft y end. |
|||
else. |
|||
rotRightLeft y |
|||
end. |
|||
else. |
else. |
||
'l00 x l02'=. L.every 0{::y |
'l00 x l02'=. L.every 0{::y |
||
if.l00 >: l02 do. |
if. l00 >: l02 do. rotRight y |
||
else. rotLeftRight y end. |
|||
else. |
|||
rotLeftRight y |
|||
end. |
|||
end. |
end. |
||
}} |
}} |
||
| Line 5,126: | Line 5,115: | ||
rotRight (rotLeft t0);t1;<t2 |
rotRight (rotLeft t0);t1;<t2 |
||
}}</lang> |
}}</lang> |
||
Tree is right argument, leaf value is left argument. An empty tree has no elements, leaves have 1 element, non-empty non-leaf nodes have three elements. |
|||
Some examples: |
Some examples: |
||