B-tree

Hej Mikkel
Jeg går ud fra det er en tegning du ønsker, den må du selv lave.
Start med det første tal i den usorterede tabel (41) det bliver roden du har nu fra roden to muligheder for det næste tal større eller mindre, er det større gå til højre er det mindre gå til venstre.

                41
                /    \
            6      52
            /  \          \
        14  18      92
          /        \        /
      2        25      63
                  /  \
              22  37


Mvh. Lars

Det der ligner et binary tree - ikke et balanced tree.

http://en.wikipedia.org/wiki/B-tree

hvordan vil et balanced tree se ud til de nøgler?

Et balanceret søgetræs udseende vil naturligvis afhænge af den algoritme der genererer træet!
Det balancerede søgetræ ER et binary træ - men det tager højde for søgedybden; dvs. det balancerer det binære træ.

Lars' træ så således ud:

                41
              /    \
            6      52
          /  \      \
          14  18      92
          /      \    /
        2      25  63
                /  \
              22  37


Der er godt nok en fejl i dette da 14 som bekendt er større end 6; dvs det skulle se således ud:

                  41
              /      \
              6        52
            /  \          \
          2  18        92
              /  \      /
              14  25    63
                  /  \
                22  37

Her er søgedybden større på venstre side af træet og det er derfor i ubalanceret :)

Hvis vi i stedet balancerer det kunne det se således ud:

                  25
                /  \
              18    41
              /  \    \
            6  22    63
            /  \  \  /  \
          2  14  37 52  92


Man skal bare skrive en algoritme, der balancerer det ...

Balancerede træer vil når de kalde B træer ikke være binære.