Program 2-3 drevo v Mathematici

Iz MaFiRaWiki

Osnovne operacije 2-3 drevesa:

Clear[pripravi, dTDrevo, ključ1, ključ2, sin1, sin2, sin3, jePrazno]
pripravi[] := dTDrevo[, , , ,]
dTDrevo[k1___, k2___, s1___, s2___, s3___];
ključ1[d_dTDrevo] := d[ [1]]
ključ2[d_dTDrevo] := d[ [2]]
sin1[d_dTDrevo] := d[ [3]]
sin2[d_dTDrevo] := d[ [4]]
sin3[d_dTDrevo] := d[ [5]]
jePrazno[d_dTDrevo] := Length[DeleteCases[d,]] === 0

Iskanje elementa v 2-3 drevesu:

Clear[vsebuje]
vsebuje[d_dTDrevo, e_] /; jePrazno[d] := False;
vsebuje[d_dTDrevo, e_] :=
  If[
    e < ključ1[d],
    If[
      Length[DeleteCases[d,]] === 1,
      False,
      vsebuje[sin1[d], e]
      ],
    If[
      Length[DeleteCases[d,]] === 1,
      e === ključ1[d],
      If[
        ključ2[d] === Null,
        vsebuje[sin2[d], e],
        If[
          e < ključ2[d],
          vsebuje[sin2[d], e],
          vsebuje[sin3[d], e]
          ]
        ]
      ]
    ]

Vstavljanje elementa v 2-3 drevo:

Clear[vstavi, vst1, vst2, vst3, vst4, vst5]
vstavi[d_dTDrevo, e_] /; jePrazno[d] := dTDrevo[e, , , ,]
vstavi[d_dTDrevo, e_] := If[vsebuje[d, e], d, vst1[d, e]]

vst1[d_, e_] := If[
   Length[DeleteCases[d,]] === 1,
   If[
     e < ključ1[d],
     ReplacePart[ReplacePart[d, dTDrevo[e, , , ,], 3], dTDrevo[ključ1[d], 4]],
     ReplacePart[ReplacePart[ReplacePart[d, dTDrevo[ključ1[d], , , ,], 3], e, 1], dTDrevo[e, , , ,], 4]
     ],
   vst2[d, e]
   ]

vst2[d_, e_] := If[
   Length[DeleteCases[d,]] === 3,
   If[
     e < ključ1[d],
     If[
       Length[DeleteCases[sin1[d],]] === 1,
       If[
         e < ključ1[sin1[d]],
         ReplacePart[ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                   d, ključ1[d], 2],
                 sin2[d], 5],
               sin1[d], 4],
             ključ1[sin1[d]], 1],
           dTDrevo[e, , , ,], 3],
         ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                 d, ključ1[d], 2],
               sin2[d], 5],
             e, 1],
           dTDrevo[e, , , ,], 4]
         ],
       If[
         Length[DeleteCases[sin1[d],]] === 3,
         ReplacePart[d, vstavi[sin1[d], e], 3],
         If[
           Length[DeleteCases[sin1[sin1[d]],]] === 1,
           If[
             e < ključ1[sin1[d]],
             ReplacePart[ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                       d, ključ1[sin1[d]], 1],
                     ključ1[d], 2],
                   If[
                     e < ključ1[sin1[sin1[d]]],
                     ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                             sin1[d], ključ1[sin1[sin1[d]]], 1],
                           dTDrevo[e, , , ,], 3],
                         sin1[sin1[d]], 4],
                       Null, {{2}, {5}}],
                     ReplacePart[ReplacePart[ReplacePart[
                           sin1[d], e, 1],
                         dTDrevo[e, , , ,], 4],
                       Null, {{2}, {5}}]
                     ], 3],
                 dTDrevo[ključ2[sin1[d]], , sin2[sin1[d]], sin3[sin1[d]],], 4],
               sin2[d], 5],
             If[
               e < ključ2[sin1[d]],
               ReplacePart[ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                         d, e, 1],
                       ključ1[d], 2],
                     dTDrevo[ključ1[sin1[d]], , sin1[sin1[d]], sin2[sin1[d]],], 3],
                   dTDrevo[ključ2[sin1[d]], , dTDrevo[e, , , ,], sin3[sin1[d]],], 4],
                 sin2[d], 5],
               ReplacePart[ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                         d, ključ2[sin1[d]], 1],
                       ključ1[d], 2],
                     dTDrevo[ključ1[sin1[d]], , sin1[sin1[d]], sin2[sin1[d]],], 3],
                   dTDrevo[e, , sin3[sin1[d]], dTDrevo[e, , , ,],], 4],
                 sin2[d], 5]
               ]
             ],
           vst4[d, e]
           ]
         ]
       ],
     If[
       Length[DeleteCases[sin2[d],]] === 1,
       ReplacePart[ReplacePart[
           d, e, 2],
         dTDrevo[e, , , ,], 5],
       If[
         Length[DeleteCases[sin2[d],]] === 3,
         ReplacePart[d, vstavi[sin2[d], e], 3],
         If[
           Length[DeleteCases[sin1[sin2[d]],]] === 1,
           If[
             e < ključ1[sin2[d]],
             ReplacePart[ReplacePart[ReplacePart[
                   d, ključ1[sin2[d]], 2],
                 dTDrevo[e, , sin1[sin2[d]], dTDrevo[e, , , ,],], 4],
               dTDrevo[ključ2[sin2[d]], , sin2[sin2[d]], sin3[sin2[d]],], 5],
             If[
               e < ključ2[sin2[d]],
               ReplacePart[ReplacePart[ReplacePart[
                     d, e, 2],
                   dTDrevo[ključ1[sin2[d]], , sin1[sin2[d]], sin2[sin2[d]],], 4],
                 dTDrevo[ključ2[sin2[d]], , dTDrevo[e, , , ,], sin3[sin2[d]],], 5],
               ReplacePart[ReplacePart[ReplacePart[
                     d, ključ2[sin2[d]], 2],
                   dTDrevo[ključ1[sin2[d]], , sin1[sin2[d]], sin2[sin2[d]],], 4],
                 dTDrevo[e, , sin3[sin2[d]], dTDrevo[e, , , ,],], 5]
               ]
             ],
           vst4[d, e]
           ]
         ]
       ]
     ],
   vst3[d, e]
   ]

vst3[d_, e_] := If[
   Length[DeleteCases[sin1[d],]] === 1,
   If[
     e < ključ1[d],
     If[
       e < ključ1[sin1[d]],
       dTDrevo[ključ1[d], , dTDrevo[ključ1[sin1[d]], , dTDrevo[e, , , ,], sin1[d],], dTDrevo[ključ2[d], , sin2[d], sin3[d],],],
       dTDrevo[ključ1[d], , dTDrevo[e, , sin1[d], dTDrevo[e, , , ,],], dTDrevo[ključ2[d], , sin2[d], sin3[d],]]
       ],
     If[
       e < ključ2[d],
       dTDrevo[e, , dTDrevo[ključ1[d], , sin1[d], sin2[d],], dTDrevo[ključ2[d], , dTDrevo[e, , , ,], sin3[d],],],
       dTDrevo[ključ2[d], , dTDrevo[ključ1[d], , sin1[d], sin2[d],], dTDrevo[e, , sin3[d], dTDrevo[e, , , ,],],]
       ]
     ],
   If[
     Length[DeleteCases[sin1[sin1[d]],]] === 1,
     If[
       e < ključ1[d],
       If[
         Length[DeleteCases[sin1[d],]] === 3,
         ReplacePart[d, vstavi[sin1[d], e], 3],
         dTDrevo[ključ1[d], , vstavi[sin1[d], e], dTDrevo[ključ2[d], , sin2[d], sin3[d],],]
         ],
       If[
         e < ključ2[d],
         If[
           Length[DeleteCases[sin2[d],]] === 3,
           ReplacePart[d, vstavi[sin2[d], e], 4],
           If[
             e < ključ1[sin2[d]],
             dTDrevo[ključ1[sin2[d]], , dTDrevo[ključ1[d], , sin1[d], dTDrevo[e, , sin1[sin2[d]], dTDrevo[e, , , ,],],], 
               dTDrevo[ključ2[d], , dTDrevo[ključ2[sin2[d]], , sin2[sin2[d]], sin3[sin2[d]],], sin3[sin2[d]],],],
             If[
               e < ključ2[sin2[d]],
               dTDrevo[e, , dTDrevo[ključ1[d], , sin1[d], 
                 dTDrevo[ključ1[sin2[d]], , sin1[sin2[d]], sin2[sin2[d]],],], 
                   dTDrevo[ključ2[d], , dTDrevo[ključ2[sin2[d]], , dTDrevo[e, , , ,], sin3[sin2[d]],], sin3[d],],],                
               dTDrevo[ključ2[sin2[d]], , dTDrevo[ključ1[d], , sin1[d], 
                 dTDrevo[ključ1[sin2[d]], , sin1[sin2[d]], sin2[sin2[d]],],], 
                   dTDrevo[ključ2[d], , dTDrevo[e, , sin3[sin2[d]], dTDrevo[e, , , ,],], sin3[d],],]
               ]
             ]
           ],
         If[
           Length[DeleteCases[sin3[d],]] === 3,
           ReplacePart[d, vstavi[sin3[d], e], 5],
           dTD[ključ2[d], , dTDrevo[ključ1[d], , sin1[d], 
           sin2[d],], vstavi[sin3[d], e],]
           ]
         ]
       ],
     vst5[d, e]
     ]
   ]

Brisanje elementa iz 2-3 drevesa:

Clear[briši, br1, br2, br3, br4]
briši[d_dTDrevo, e_] := If[vsebuje[d, e], br1[d, e], d]
br1[d_, e_] := If[
   Length[DeleteCases[d,]] === 1,
   dTDrevo[, , , ,],
   If[
     Length[DeleteCases[sin1[d],]] === 1,
     If[
       Length[DeleteCases[d,]] === 3,
       If[
         e === ključ1[sin1[d]],
         sin2[d],
         sin1[d]
         ],
       If[
         e === ključ1[sin1[d]],
         dTDrevo[ključ2[d], , sin2[d], sin3[d],],
         If[
           e === ključ1[sin2[d]],
           dTDrevo[ključ2[d], , sin1[d], sin3[d],],
           ReplacePart[d, Null, {{2}, {5}}]
           ]
         ]
       ],
     br2[d, e]
     ]
   ]

br2[d_, e_] := If[
   Length[DeleteCases[sin1[sin1[d]],]] === 1,
   If[
     Length[DeleteCases[d,]] === 3,
     If[
       e < ključ1[d],
       If[
         Length[DeleteCases[sin1[d],]] === 3,
         If[
           Length[DeleteCases[sin2[d],]] === 3,
           If[
             e === ključ1[sin1[sin1[d]]],
             dTDrevo[ključ1[d], ključ1[sin2[d]], sin2[sin1[d]], sin1[sin2[d]], sin2[sin2[d]]],
             dTDrevo[ključ1[d], ključ1[sin2[d]], sin1[sin1[d]], sin1[sin2[d]], sin2[sin2[d]]]
             ],
           If[
             e === ključ1[sin1[sin1[d]]],
             dTDrevo[ključ1[sin2[d]], , dTDrevo[ključ1[d], , sin2[sin1[d]], sin1[sin2[d]],],
               dTDrevo[ključ2[sin2[d]], , sin2[sin2[d]], sin3[sin2[d]],],],
             dTDrevo[ključ1[sin2[d]], , dTDrevo[ključ1[d], , sin1[sin1[d]], sin1[sin2[d]],], 
               dTDrevo[ključ2[sin2[d]], , sin2[sin2[d]], sin3[sin2[d]],],]
             ]
           ],
         ReplacePart[d, briši[sin1[d], e], 3]
         ],
       If[
         Length[DeleteCases[sin2[d],]] === 3,
         If[
           Length[DeleteCases[sin1[d],]] === 3,
           If[
             e === ključ1[sin1[sin2[d]]],
             dTDrevo[ključ1[sin1[d]], ključ1[sin2[d]], sin1[sin1[d]]sin2[sin1[d]], sin2[sin2[d]]],
             dTDrevo[ključ1[sin1[d]], ključ1[d], sin1[sin1[d]], sin2[sin1[d]], sin1[sin2[d]]]
             ],
           If[
             e === ključ1[sin1[sin2[d]]],
             dTDrevo[ključ2[sin1[d]], , ReplacePart[sin1[d], Null, {{2}, {5}}], 
               dTDrevo[ključ1[sin2[d]], , sin3[sin1[d]], sin2[sin2[d]],],],
             dTDrevo[ključ2[sin1[d]], , ReplacePart[sin1[d], Null, {{2}, {5}}], 
               dTDrevo[ključ1[d], , sin3[sin1[d]], sin1[sin2[d]],],]
             ]
           ],
         If[
           e === ključ1[sin1[sin2[d]]],
           ReplacePart[ReplacePart[d, ključ1[sin2[d]], 1], briši[sin2[d], e], 4],
           ReplacePart[d, briši[sin2[d], e], 4]
           ]
         ]
       ],
     br3[d, e]
     ],
   br4[d, e]
   ]

br3[d_, e_] := If[
   e < ključ1[d],
   If[
     Length[DeleteCases[sin1[d],]] === 3,
     If[
       Length[DeleteCases[sin2[d],]] === 3,
       If[
         e === ključ1[sin1[sin1[d]]],
         dTDrevo[ključ2[d], , dTDrevo[ključ1[d], ključ1[sin2[d]], sin2[sin1[d]], sin1[sin2[d]], sin2[sin2[d]]], sin3[d],],
         dTDrevo[ključ2[d], , dTDrevo[ključ1[d], ključ1[sin2[d]], sin1[sin1[d]], sin1[sin2[d]], sin2[sin2[d]]], sin3[d],]
         ],
       If[
         e === ključ1[sin1[sin1[d]]],
         ReplacePart[ReplacePart[ReplacePart[
               d, ključ1[sin2[d]], 1],
             dTDrevo[ključ1[d], , sin2[sin1[d]], sin1[sin2[d]],], 3],
           briši[sin2[d], ključ1[sin1[sin2[d]]]], 4],
         ReplacePart[ReplacePart[ReplacePart[
               d, ključ1[sin2[d]], 1],
             dTDrevo[ključ1[d], , sin1[sin1[d]], sin1[sin2[d]],], 3],
           briši[sin2[d], ključ1[sin1[sin2[d]]]], 4]
         ]
       ],
     ReplacePart[d, briši[sin1[d], e], 3]
     ],
   If[
     e < ključ2[d],
     If[
       Length[DeleteCases[sin2[d],]] === 3,
       If[
         Length[DeleteCases[sin1[d],]] === 3,
         If[
           e === ključ1[sin1[sin2[d]]],
           ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                   d, ključ2[d], 1],
                 vstavi[sin1[d], ključ1[sin2[sin2]]], 3],
               sin3[d], 4],
             Null, {{2}, {5}}],
           ReplacePart[ReplacePart[ReplacePart[ReplacePart[
                   d, ključ2[d], 1],
                 vstavi[sin1[d], ključ1[sin1[sin2[d]]]], 3],
               sin3[d], 4],
             Null, {{2}, {5}}]
           ],
         If[
           e === ključ1[sin1[sin2[d]]],
           ReplacePart[ReplacePart[ReplacePart[
                 d, ključ2[sin1[d]], 1],
               ReplacePart[sin1[d], Null, {{2}, {5}}], 3],
             ReplacePart[sin2[d], sin3[sin1[d]], 3], 4],
           ReplacePart[ReplacePart[ReplacePart[
                 d, ključ2[sin1[d]], 1],
               ReplacePart[sin1[d], Null, {{2}, {5}}], 3],
             dTDrevo[ključ1[d], , sin3[sin1[d]], sin1[sin2[d]],], 4]
           ]
         ],
       If[
         e === ključ1[sin1[sin2[d]]],
         ReplacePart[ReplacePart[
             d, ključ1[sin2[d]], 1],
           briši[sin2[d], e], 4],
         ReplacePart[d, briši[sin2[d], e], 4]
         ]
       ],
     If[
       Length[DeleteCases[sin3[d],]] === 3,
       If[
         Length[DeleteCases[sin2[d],]] === 3,
         If[
           e === ključ1[sin1[sin3[d]]],
           ReplacePart[ReplacePart[
               d, ReplacePart[ReplacePart[sin2[d], ključ1[sin3[d]], 2], sin2[sin3[d]], 5], 4],
             Null, {{2}, {5}}],
           ReplacePart[ReplacePart[
               d, ReplacePart[ReplacePart[sin2[d], ključ2[d], 2], sin1[sin3[d]], 5], 4],
             Null, {{2}, {5}}]
           ],
         ReplacePart[ReplacePart[ReplacePart[
               d, ključ2[sin2[d]], 2],
             briši[sin2[d], ključ1[sin3[sin2[d]]]], 4],
           If[
             e === ključ1[sin1[sin3[d]]],
             ReplacePart[sin3[d], sin3[sin2[d]], 3],
             dTDrevo[ključ2[d], , sin3[sin2[d]], sin1[sin3[d]],]
             ], 5]
         ],
       If[
         e === ključ1[sin1[sin3[d]]],
         ReplacePart[ReplacePart[
             d, ključ1[sin3[d]], 2],
           briši[sin3[d], e], 5],
         ReplacePart[d, briši[sin3[d], e], 5]
         ]
       ]
     ]
   ]

Ta program "zna" delati z drevesi, katerih globina je največ 3. Za drevesa večje globine, bi bilo potrebno definirati še funkcije vst4[d,e], vst5[d,e] in br4[d,e], ki so že vstavljene v ta program, a niso definirane.


Glej tudi

Osebna orodja