Delkapittel 5.2 – Binære søketrær

Oppgave 1

D₃ = 2(1 + 1/3)H₄ - 4 - 2/3 der H₄ = 1 + 1/2 + 1/3 + 1/4 = 25/12.
Dermed blir D₃ = 2 · 4/3 · 25/12 - 14/3 = 50/9 - 14/3 = 50/9 - 42/9 = 8/9.

Oppgave 2

Over hvert av de 24 trærne står den permutasjonen som gir treet og under hvert tre står treets inndre veilengde. Summen av veilengdene er 116. Gjennomsnittlig nodedybde får vi så ved å dele med 4 siden det er 4 noder og så dele med 24 siden det er 24 trær. Dermed blir det 116/4/24 = 29/24.

Formel 5.2.4 a) gir:

D₄ = 2(1 + 1/4)H₅ - 4 - 2/4 der H₅ = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60.
Dermed D₄ = 2·5/4·137/60 - 9/2 = 137/24 - 108/24 = 29/24.

Oppgave 3 a)

  public static <T> int indreVeilengde(SBinTre<T> tre)
  {
    if (tre.tom()) return 0;
    int[] a = {0};
    indreVeilengde(tre.rot,0,a);
    return a[0];
  }

  private static <T> void indreVeilengde(Node<T> p, int dybde, int[] a)
  {
    if (p.venstre != null) indreVeilengde(p.venstre,dybde + 1,a);
    a[0] += dybde;
    if (p.høyre != null) indreVeilengde(p.høyre,dybde + 1,a);
  }

Oppgave 3 b)

  public static <T> int indreVeilengde(SBinTre<T> tre)
  {
    if (tre.tom()) return 0;
    return indreVeilengde(tre.rot)[0];
  }

  private static <T> int[] indreVeilengde(Node<T> p)
  {
    // et tomt tre har 0 som antall og 0
    // som indre veilengde
    if (p == null) return new int[]{0,0};

    int[] v = indreVeilengde(p.venstre);
    int[] h = indreVeilengde(p.høyre);

    return new int[]
      {v[0] + v[1] + h[0] + h[1], v[1] + h[1] + 1};
  }

Oppgave 4

I et tre med n noder der ingen node har to barn, vil rotnoden ha dybde 0, rotnodens barn ha dybde 1, osv. til den nederste noden som har dybde n - 1. Indre veilengde blir dermed 1 + 2 + 3 + . . . + n - 1 = n(n - 1)/2. Med n = 65536 blir den indre veilengden lik 2147450880 og med n = 65537 blir den 2147516416. Største mulige int-tall er 2147483647. Med andre ord er n = 65537 det minste antallet noder for et tre der indre veilengde i verste fall er for stor for datatypen int.

Oppgave 5

  public static <T> double gjNodedybde(SBinTre<T> tre)
  {
    if (tre.tom()) throw new IllegalArgumentException(
      "Ikke definert for et tomt tre!");

    return (double)indreVeilengde(tre)/tre.antall();
  }

Oppgave 6

  public static void main(String[] args)
  {
    int[] a = {100,1000,100000};
    for (int i = 0; i < a.length; i++)
    {
      SBinTre<Integer> tre = SBinTre.naturligOrdenTre(Tabell.randPermInteger(a[i]));
      System.out.println(SBinTre.gjNodedybde(tre));
    }
  }

Oppgave 7

  public static double gjNodedybde(int n)
  {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i + 1;

    boolean flerePermutasjoner = true;
    long sumVeilengde = 0;

    while (flerePermutasjoner)
    {
      SBinTre<Integer> tre = SBinTre.naturligOrdenTre();
      for (int i = 0; i < n; i++) tre.leggInn(a[i]);
      sumVeilengde += SBinTre.indreVeilengde(tre);
      flerePermutasjoner = Tabell.nestePermutasjon(a);
    }

    double gjennomsnitt = (double)sumVeilengde/n;
    gjennomsnitt /= Matte.fakultet(n);

    return gjennomsnitt;
  }

Oppgave 8

  public static double D(int n)
  {
    return 2*(1 + 1.0/n)*Matte.harmonisk(n + 1) - 4 - 2.0/n;
  }

Oppgave 9

  public static void main(String[] args)
  {
    for (int k = 1; k < 11; k++)
    {
      double a = gjNodedybde(k);
      double b = D(k);
      System.out.println(a);
      System.out.println(b);
    }
  }

Oppgave 10

I løsningsforslaget til Oppgave 2 er alle de 24 trærne for tilfellet n = 4 tegnet. En opptelling viser at det tilsammen er 40 bladnoder. Gjennomsnittet blir derfor 40/24 = 5/3. Det svarer til formelen B_n = (n + 1)/3 med n = 4. Vi ser også at det er 40 noder med ett barn og 16 noder med to barn. Gjennomsnittet for disse blir dermed 5/3 og 2/3. Det svarer til E_n = (n + 1)/3 og T_n = (n - 2)/3 for n = 4.

Oppgave 11

I et binærtre med n noder er det totalt 2n + 1 pekere, dvs. én peker til rotnoden og to pekere ut av hver av de n nodene. Hver node blir pekt på nøyaktig én gang, dvs. n pekere som ikke er null og dermed n + 1 nullpekere.

Bladnoder Ethvert ikke-tomt tre må ha minst én bladnode. For hver n er det lett å lage et tre som ikke har flere enn én node. Lag treet ekstremt skjevt, dvs. slik at ingen noder har to barn. Da er det kun den nederste av nodene som blir bladnode. La n være et oddetall, dvs. n = 2k + 1. Da kan vi lage et tre med k + 1 bladnoder. La f.eks. rotnoden ha to barn, rotnodens høyre barn ha to barn, osv. slik at kun høyre barn har to barn inntil det har blitt n = 2k + 1 noder. Eller lag et komplett tre med n = 2k + 1 noder. Det vil også ha k + 1 bladnoder. Anta at det er mulig å lage et tre med n = 2k + 1 noder slik at det er flere enn k + 1 bladnoder. Ut fra hver bladnode går det to nullpekere. Det betyr at i et slikt tre må det være flere enn 2k + 2 nullpekere. Men det er umulig siden et binærtre alltid har n + 1 = 2k + 2 nullpekere. Med andre ord kan et binærtre med n = 2k + 1 noder ha maksimalt k + 1 bladnoder. Med tilsvarende argumentasjon kan vi vise at hvis n er et partall, dvs. n = 2k, så vil det maksimalt kunne være k bladnoder. Det betyr generelt at 1 er det minste antallet bladnoder og ⌊(n + 1)/2⌋ er det største antallet bladnoder.
Ettbarnsnoder Et ekstremt skjevt tre (ingen noder har to barn) med n noder, har n - 1 ettbarnsnoder. Det er det maksimale. Det minimale antallet er 0 hvis n er et oddetall og 1 hvis n er et partall. Det ser en ved f.eks. å lage et komplett tre med n noder.
Tobarnsnoder Et ekstremt skjevt tre (ingen noder har to barn) med n noder, har ingen tobarnsnoder. Det er det minimale. La La n være et oddetall, dvs. n = 2k + 1. I et komplett tre med n = 2k + 1 noder det ingen ettbarnsnoder og k + 1 bladnoder. Dermed er det k tobarnsnoder. Anta at det finnes et tre med n = 2k + 1 noder som har k + 1 eller flre tobarnsnoder. Ut fra hver tobarnsnode går det to pekere som ikke er null. Dermed vil det i et slikt tre være 2k + 2 eller flere pekere som ikke er null. Det er umulig siden et binærtre med n noder har nøyaktig n pekere som ikke er null. Med andre ord kan et binærtre med n = 2k + 1 noder ha maksimalt k tobarnsnoder. Med tilsvarende argumentasjon kan vi vise at hvis n er et partall, dvs. n = 2k, så vil det maksimalt kunne være k - 1 tobarnsnoder. Det betyr generelt at 0 er det minste antallet og ⌊(n - 1)/2⌋ er det største antallet tobarnsnoder.

Oppgave 12

Flg. rekursive metode traverserer treet og for hver node avgjør om det er bladnode, ettbarnsnode eller tobarnsnode. Tabellen a er slik at bladnodene registreres i a[0], ettbarnsnodene i a[1] og tobarnsnodene i a[2]. Den offentlige metoden returnerer tabellen.

  public int[] antallNodetyper()
  {
    int[] a = {0,0,0};
    if (rot != null) antallNodetyper(rot, a);
    return a;
  }

  private static <T> void antallNodetyper(Node<T> p, int[] a)
  {
    if (p.venstre == null
            && p.høyre == null) a[0]++;  // bladnode
    else if (p.venstre != null
            && p.høyre != null) a[2]++;  // to barn
    else a[1]++;  // ett barn

    if (p.venstre != null) antallNodetyper(p.venstre, a);
    if (p.høyre != null) antallNodetyper(p.høyre, a);
  }

Oppgave 13

Se 5212-2.pdf.