Worst-case AVL trees
--------------------
Function for a depth-⍵ worst-case AVL tree.

    fib←{                           ⍝ Depth-⍵ worst-case fibonacci tree.
        ⊃⍬⍴⎕IO{                     ⍝ first item is tree.
            ⍵=0:0 ⍺                 ⍝ f 0 → []
            ⍵=1:(⍺ 0(0 0))(⍺+1)     ⍝ f 1 → ⍺ [] []
            l m←⍺ ∇ ⍵-2             ⍝ left subtree and next value.
            r n←(m+1)∇ ⍵-1          ⍝ right ..  ..  ..  ..  ..
            (m 1(l r))n             ⍝ f ⍵+1 → ⍺ [f ⍵-2] [f ⍵-1]
        }⍵                          ⍝ :: tree next ← next ∇ depth
    }

    ⍕avl fib 7                      ⍝ Depth-7 worst case.
             ┌1=1
         ┌2=2┤
         │   └>3=3┐
         │        └>4=4
     ┌5=5┤
     │   │    ┌6=6┐
     │   │    │   └>7=7
     │   └>8=8┤
     │        │      ┌9=9
     │        └>10=10┤
     │               └>11=11┐
     │                      └>12=12
13=13┤
     │            ┌14=14┐
     │            │     └>15=15
     │      ┌16=16┤
     │      │     │      ┌17=17
     │      │     └>18=18┤
     │      │            └>19=19┐
     │      │                   └>20=20
     └>21=21┤
            │            ┌22=22
            │      ┌23=23┤
            │      │     └>24=24┐
            │      │            └>25=25
            └>26=26┤
                   │      ┌27=27┐
                   │      │     └>28=28
                   └>29=29┤
                          │      ┌30=30
                          └>31=31┤
                                 └>32=32┐
                                        └>33=33

    ⍕avl (fib 7) ~avl 1             ⍝ removing node 1:
                       ┌2=2
                   ┌3=3┤
                   │   └4=4
               ┌5=5┤
               │   └6=6┐
               │       └>7=7
           ┌8=8┤
           │   │     ┌9=9
           │   └10=10┤
           │         └>11=11┐
           │                └>12=12
     ┌13=13┤
     │     │     ┌14=14┐
     │     │     │     └>15=15
     │     └16=16┤
     │           │      ┌17=17
     │           └>18=18┤
     │                  └>19=19┐
     │                         └>20=20
21=21┤
     │           ┌22=22
     │     ┌23=23┤
     │     │     └>24=24┐
     │     │            └>25=25
     └26=26┤
           │      ┌27=27┐
           │      │     └>28=28
           └>29=29┤
                  │      ┌30=30
                  └>31=31┤
                         └>32=32┐
                                └>33=33
See also: avl

Back to: contents

Back to: Workspaces