⍝ Insert value ⍵ in AVL tree ⍺:

    put ← ∪ avl     ⍝ :: tree ← tree ∇ key value
    rem ← ~ avl     ⍝ :: tree ← tree ∇ key
    get ← ⍎ avl     ⍝ :: value ← tree ∇ key
    chk ← ? avl     ⍝ :: ok height maxbal ← ∇ tree
    fmt ← ⍕ avl     ⍝ :: cmat ← ∇ tree
    vec ← ∊ avl     ⍝ :: (key val)[] ← ∇ tree

    tree←0∘(put foldl)          ⍝ tree from vector of keys.

    tree ⍳7
┌─┬─┬─────────────────────────────────────────────────────────┐
│4│0│┌───────────────────────────┬───────────────────────────┐│
│ │ ││┌─┬─┬─────────────────────┐│┌─┬─┬─────────────────────┐││
│ │ │││2│0│┌─────────┬─────────┐│││6│0│┌─────────┬─────────┐│││
│ │ │││ │ ││┌─┬─┬───┐│┌─┬─┬───┐││││ │ ││┌─┬─┬───┐│┌─┬─┬───┐││││
│ │ │││ │ │││1│0│0 0│││3│0│0 0│││││ │ │││5│0│0 0│││7│0│0 0│││││
│ │ │││ │ ││└─┴─┴───┘│└─┴─┴───┘││││ │ ││└─┴─┴───┘│└─┴─┴───┘││││
│ │ │││ │ │└─────────┴─────────┘│││ │ │└─────────┴─────────┘│││
│ │ ││└─┴─┴─────────────────────┘│└─┴─┴─────────────────────┘││
│ │ │└───────────────────────────┴───────────────────────────┘│
└─┴─┴─────────────────────────────────────────────────────────┘

    fmt tree ⍳7
        ┌─1=1
   ┌─2=2┤    
   │    └─3=3
4=4┤         
   │    ┌─5=5
   └─6=6┤    
        └─7=7

    kseq ← 1↓¨,\' ',12↑⎕a           ⍝ key sequence.

    kseq
┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┬─────────┬──────────┬───────────┬────────────┐
││A│AB│ABC│ABCD│ABCDE│ABCDEF│ABCDEFG│ABCDEFGH│ABCDEFGHI│ABCDEFGHIJ│ABCDEFGHIJK│ABCDEFGHIJKL│
└┴─┴──┴───┴────┴─────┴──────┴───────┴────────┴─────────┴──────────┴───────────┴────────────┘

    fmt∘tree¨ kseq                  ⍝ successive inserts A B C ...
┌┬───┬────────┬────────┬─────────────┬─────────────┬─────────────┬─────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┐
││A=A│A=A┐    │   ┌─A=A│   ┌<A=A     │   ┌<A=A     │        ┌─A=A│        ┌─A=A│        ┌─A=A     │        ┌─A=A     │        ┌─A=A     │        ┌─A=A     │             ┌─A=A│
││   │   └>B=B│B=B┤    │B=B┤         │B=B┤         │   ┌─B=B┤    │   ┌─B=B┤    │   ┌<B=B┤         │   ┌<B=B┤         │   ┌<B=B┤         │   ┌<B=B┤         │        ┌─B=B┤    │
││   │        │   └─C=C│   └>C=C┐    │   │    ┌─C=C│   │    └─C=C│   │    └─C=C│   │    └─C=C     │   │    └─C=C     │   │    └─C=C     │   │    └─C=C     │        │    └─C=C│
││   │        │        │        └>D=D│   └>D=D┤    │D=D┤         │D=D┤         │D=D┤              │D=D┤              │D=D┤              │D=D┤              │   ┌─D=D┤         │
││   │        │        │             │        └─E=E│   └─E=E┐    │   │    ┌─E=E│   │    ┌<E=E     │   │    ┌<E=E     │   │         ┌─E=E│   │         ┌─E=E│   │    │    ┌─E=E│
││   │        │        │             │             │        └>F=F│   └─F=F┤    │   └>F=F┤         │   └>F=F┤         │   │    ┌─F=F┤    │   │    ┌─F=F┤    │   │    └─F=F┤    │
││   │        │        │             │             │             │        └─G=G│        └>G=G┐    │        │    ┌─G=G│   │    │    └─G=G│   │    │    └─G=G│   │         └─G=G│
││   │        │        │             │             │             │             │             └>H=H│        └>H=H┤    │   └>H=H┤         │   └>H=H┤         │H=H┤              │
││   │        │        │             │             │             │             │                  │             └─I=I│        └─I=I┐    │        │    ┌─I=I│   │    ┌<I=I     │
││   │        │        │             │             │             │             │                  │                  │             └>J=J│        └─J=J┤    │   └─J=J┤         │
││   │        │        │             │             │             │             │                  │                  │                  │             └─K=K│        └>K=K┐    │
││   │        │        │             │             │             │             │                  │                  │                  │                  │             └>L=L│
└┴───┴────────┴────────┴─────────────┴─────────────┴─────────────┴─────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┘

    (tree 12↑⎕a){fmt ⍺⍺ rem foldl ⍵}¨kseq           ⍝ successive removals A B ..
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬─────────────┬─────────────┬─────────────┬────────┬────────┬───┬┐
│             ┌─A=A│        ┌─B=B┐    │        ┌<C=C     │        ┌>D=D┐    │        ┌─E=E     │   ┌<F=F┐         │        ┌─G=G│   ┌─H=H┐    │   ┌<I=I     │   ┌─J=J│K=K┐    │L=L││
│        ┌─B=B┤    │        │    └>C=C│   ┌─D=D┤         │        │    └>E=E│   ┌<F=F┤         │   │    └>G=G     │   ┌─H=H┤    │   │    └>I=I│J=J┤         │K=K┤    │   └>L=L│   ││
│        │    └─C=C│   ┌─D=D┤         │   │    │    ┌─E=E│   ┌─F=F┤         │   │    └─G=G     │H=H┤              │   │    └─I=I│J=J┤         │   └>K=K┐    │   └─L=L│        │   ││
│   ┌─D=D┤         │   │    │    ┌─E=E│   │    └>F=F┤    │   │    └<G=G     │H=H┤              │   │    ┌<I=I     │J=J┤         │   └─K=K┐    │        └>L=L│        │        │   ││
│   │    │    ┌─E=E│   │    └─F=F┤    │   │         └─G=G│H=H┤              │   │    ┌<I=I     │   └>J=J┤         │   └─K=K┐    │        └>L=L│             │        │        │   ││
│   │    └─F=F┤    │   │         └─G=G│H=H┤              │   │    ┌<I=I     │   └>J=J┤         │        └>K=K┐    │        └>L=L│             │             │        │        │   ││
│   │         └─G=G│H=H┤              │   │    ┌<I=I     │   └─J=J┤         │        └>K=K┐    │             └>L=L│             │             │             │        │        │   ││
│H=H┤              │   │    ┌<I=I     │   └─J=J┤         │        └>K=K┐    │             └>L=L│                  │             │             │             │        │        │   ││
│   │    ┌<I=I     │   └─J=J┤         │        └>K=K┐    │             └>L=L│                  │                  │             │             │             │        │        │   ││
│   └─J=J┤         │        └>K=K┐    │             └>L=L│                  │                  │                  │             │             │             │        │        │   ││
│        └>K=K┐    │             └>L=L│                  │                  │                  │                  │             │             │             │        │        │   ││
│             └>L=L│                  │                  │                  │                  │                  │             │             │             │        │        │   ││
└──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴─────────────┴─────────────┴─────────────┴────────┴────────┴───┴┘

⍝ successive removals of root node:

    (tree 12↑⎕a){fmt ⍺⍺ rem foldl ⍵}¨,\' HIJDEFGKBCLA'
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬─────────────┬─────────────┬─────────────┬─────────────┬────────┬────────┬───┬┐
│             ┌─A=A│             ┌─A=A│             ┌─A=A│        ┌─A=A     │        ┌─A=A     │        ┌─A=A│        ┌─A=A│        ┌─A=A│   ┌<A=A     │   ┌─A=A│   ┌>A=A│A=A││
│        ┌─B=B┤    │        ┌─B=B┤    │        ┌─B=B┤    │   ┌<B=B┤         │   ┌<B=B┤         │   ┌─B=B┤    │   ┌─B=B┤    │   ┌>B=B┤    │B=B┤         │C=C┤    │L=L┘    │   ││
│        │    └─C=C│        │    └─C=C│        │    └─C=C│   │    └─C=C     │   │    └─C=C     │   │    └─C=C│   │    └─C=C│   │    └─C=C│   │    ┌>C=C│   └─L=L│        │   ││
│   ┌─D=D┤         │   ┌>D=D┤         │   ┌>D=D┤         │D=D┤              │E=E┤              │F=F┤         │G=G┤         │K=K┤         │   └>L=L┘    │        │        │   ││
│   │    │    ┌─E=E│   │    │    ┌─E=E│   │    │    ┌─E=E│   │         ┌─E=E│   │    ┌>F=F┐    │   │    ┌─G=G│   └─K=K┐    │   └<L=L     │             │        │        │   ││
│   │    └─F=F┤    │   │    └─F=F┤    │   │    └─F=F┤    │   │    ┌>F=F┤    │   │    │    └>G=G│   └─K=K┤    │        └>L=L│             │             │        │        │   ││
│   │         └─G=G│   │         └─G=G│   │         └─G=G│   │    │    └─G=G│   └>K=K┤         │        └─L=L│             │             │             │        │        │   ││
│H=H┤              │I=I┤              │J=J┤              │   └>K=K┤         │        └<L=L     │             │             │             │             │        │        │   ││
│   │    ┌<I=I     │   │    ┌─J=J     │   └<K=K┐         │        └<L=L     │                  │             │             │             │             │        │        │   ││
│   └─J=J┤         │   └<K=K┤         │        └>L=L     │                  │                  │             │             │             │             │        │        │   ││
│        └>K=K┐    │        └─L=L     │                  │                  │                  │             │             │             │             │        │        │   ││
│             └>L=L│                  │                  │                  │                  │             │             │             │             │        │        │   ││
└──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴─────────────┴─────────────┴─────────────┴─────────────┴────────┴────────┴───┴┘

    display fmt tree ⎕a
┌→──────────────────────┐
↓                  ┌─A=A│
│             ┌─B=B┤    │
│             │    └─C=C│
│        ┌─D=D┤         │
│        │    │    ┌─E=E│
│        │    └─F=F┤    │
│        │         └─G=G│
│   ┌─H=H┤              │
│   │    │         ┌─I=I│
│   │    │    ┌─J=J┤    │
│   │    │    │    └─K=K│
│   │    └─L=L┤         │
│   │         │    ┌─M=M│
│   │         └─N=N┤    │
│   │              └─O=O│
│P=P┤                   │
│   │         ┌─Q=Q     │
│   │    ┌<R=R┤         │
│   │    │    └─S=S     │
│   └─T=T┤              │
│        │         ┌─U=U│
│        │    ┌─V=V┤    │
│        │    │    └─W=W│
│        └>X=X┤         │
│             └─Y=Y┐    │
│                  └>Z=Z│
└───────────────────────┘

    fmt¨ ∪ tree¨↓pmat 5                         ⍝ test double rotation.
┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│   ┌<1=1     │   ┌─1=1┐    │   ┌─1=1┐    │        ┌─1=1│        ┌>1=1│        ┌>1=1│
│2=2┤         │   │    └>2=2│   │    └>2=2│   ┌>2=2┤    │   ┌─2=2┘    │   ┌─2=2┘    │
│   │    ┌─3=3│3=3┤         │3=3┤         │   │    └─3=3│3=3┤         │3=3┤         │
│   └>4=4┤    │   └─4=4┐    │   │    ┌>4=4│4=4┤         │   └─4=4┐    │   │    ┌>4=4│
│        └─5=5│        └>5=5│   └─5=5┘    │   └<5=5     │        └>5=5│   └─5=5┘    │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘

    tt←tree ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)

    display fmt tt
┌→─────────────────────────────┐
↓             ┌>five=5         │
│     ┌<four=4┘                │
│one=1┤                        │
│     │               ┌>seven=7│
│     │        ┌>six=6┘        │
│     └>three=3┤               │
│              └<two=2         │
└──────────────────────────────┘

    vec tt                                  ⍝ enlist of tree.
┌────────┬────────┬───────┬─────────┬───────┬─────────┬───────┐
│┌────┬─┐│┌────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│
││five│5│││four│4│││one│1│││seven│7│││six│6│││three│3│││two│2││
│└────┴─┘│└────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│
└────────┴────────┴───────┴─────────┴───────┴─────────┴───────┘

    tt ← tt put foldl ('one' 11)('two' 22)('three'33)

    display fmt tt
┌→───────────────────────────────┐
↓              ┌>five=5          │
│      ┌<four=4┘                 │
│one=11┤                         │
│      │                ┌>seven=7│
│      │         ┌>six=6┘        │
│      └>three=33┤               │
│                └<two=22        │
└────────────────────────────────┘

    0 ≡ tt rem foldl 'seven' 'six' 'five' 'four' 'one' 'two' 'three'
1
    0 ≡ tt rem foldl 'six' 'four' 'seven' 'three' 'five' 'one' 'two'
1

    tt∘get¨ 'two' 'four' 'six'              ⍝ search tree for keys.
22 4 6

    ⊢tt get 'eight'                         ⍝ key not in tree.
6::VALUE ERROR

    chk tt                                  ⍝ ok size mean_depth height.
1 7 2 4

    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
    }

    display fmt 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│
└───────────────────────────────────────────────┘

    display fmt (fib 7)rem 1        ⍝ removing worst-case node.
┌→───────────────────────────────────────┐
↓                           ┌─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│
└────────────────────────────────────────┘

    ⊢Alpha test '_BST'                       ⍝ common BST tests.
1

Back to: code

Back to: Workspaces