Nada

Föreläsning 12: Mer om binärträd

Ett binärt sökträd är sorterat från vänster till höger i storleksordning (om det innehåller tal) eller i bokstavsordning (om det innehåller ord). Vi såg förut hur man kunde skriva ut trädet från vänster till höger (kallas inordning) med en enkel rekursiv metod. Nu ska vi se hur sökning efter ett visst tal går till.

Sökning i binärträd

All sökning utgår från roten och man kan tänka sej att man först sätter pekfingret på rottalet. Det sökta talet jämförs med pekfingertalet och då är tre fall möjliga: Om man med satsen if(exists(17))... vill kunna kolla om talet 17 finns i trädet kan man programmera exists så här.
  static boolean exists(int talet)                       {
    Node p=root                                          ;
    while(p!=null)                                       {
      if(talet<p.tal) p=p.left                           ;
      else if(talet>p.tal) p=p.right                     ;
      else return true                                   ;}
    return false                                         ;}
Om trädet är balanserat blir det inte så många tal man behöver jämföra med innan man kommit längst ner i trädet. Med N poster i trädet blir det cirka logN jämförelser, så som visades i föreläsning 11.

Att deklarera metoden som static går bra om man vill ha ett enda binärträd som existerar under hela körningen. Ofta låter man bli att skriva static för att med new BinTree() kunna skapa hur många binärträd som helst just när man behöver dom.

Insättning i binärträd

Insättning av ett nytt tal i trädet går egentligen till på samma sätt som sökningen. Man söker efter talet och om man finner det skriver man bara ut att det är en dubblett. Men om man längst ner i trädet utan att ha funnit talet, dvs man står vid en null-pekare, skapar man en ny post med det nya talet i och låter den forna null-pekaren peka på den nya posten i stället.

Ett avsnitt ur koden för insert ska alltså se ut så här:

    if(p==null)                                          {
      p=new Node()                                       ;
      p.tal=talet                                        ;
      return p                                           ;}
Här returnerar metoden en pekare till den nya posten. Om trädet är tomt tidigare ska pekaren root peka på den nya ensamma posten, därför måste tydligen anropet vara

root=insert(talet,root);

och hela koden blir
  Node insert(int talet, Node p)                         {
    if(p==null)                                          {
      p=new Node()                                       ;
      p.tal=talet                                        ;
      return p                                           ;}
    if(talet<p.tal) p.left=insert(talet,p.left)          ;
    else if(talet>p.tal) p.right=insert(talet,p.right)   ;
    else System.out.println("Dubblett: "+talet)          ;
    return p                                             ;}
Det står Node insert(... eftersom metoden returnerar typen Node, nämligen en pekare till ett träd där det nya talet har stoppats in.

Privatsaker och publiktillvända metoder

Vår binärträdsklass blev så bra att vi vill låta alla andra javaklasser använda den. Vår lilla klass TestTree gör till exempel anrop av typen
  BinTree tree = new BinTree();
  tree.insert(17);
  tree.write();
  n=tree.antal();    
  if(tree.exists(4711)) ...
Notera att pekaren root inte förekommer och att man inte från huvudprogrammet kan avläsa att det finns left- och rightpekare osv. Man säger att binärträdet är abstrakt, och det är så man bör programmera. Genom att skriva private framför allt som har med pekare att göra ser man till att ingen utomstående klass kan komma åt dessa privatsaker. För tydlighets skull skriver vi public på resten.

Eftersom nu inte TestTree kan göra anropet write(root) måste vi tillhandahålla en publik metod write() som sedan i sin tur anropar den privata metoden.

class Node                                               {
  int tal                                                ;
  Node left=null,right=null                              ;}
public class BinTree                                     {
  private Node root=null                                 ;
  public boolean exists(int talet)                       {
    Node p=root                                          ;
    while(p!=null)                                       {
      if(talet<p.tal) p=p.left                           ;
      else if(talet>p.tal) p=p.right                     ;
      else return true                                   ;}
    return false                                         ;}
  private void write(Node p)                             {
    if(p==null) return                                   ;
    write(p.left)                                        ;
    System.out.println(p.tal)                            ;
    write(p.right)                                       ;}
  public void write()                                    {
    write(root)                                          ;}
  private Node insert(int talet, Node p)                 {
    if(p==null)                                          {
      p=new Node()                                       ;
      p.tal=talet                                        ;
      return p                                           ;}
    if(talet<p.tal) p.left=insert(talet,p.left)          ;
    else if(talet>p.tal) p.right=insert(talet,p.right)   ;
    else System.out.println("Dubblett: "+talet)          ;
    return p                                             ;}
  public void insert(int talet)                          {
    root = insert(talet,root)                            ;}
  private int antal(Node p)                              {
    if(p==null) return 0                                 ;
    return 1+antal(p.left)+antal(p.right)                ;}
  public int antal()                                     {
    return antal(root)                                   ;}}
class TestTree                                           {
  public static void main(String[] args)                 {
  BinTree tree = new BinTree()                           ;
  while(Mio.NextChar()!='\n') tree.insert(Mio.GetInt())  ;
  tree.write()                                           ;
  System.out.println(tree.antal()+" poster")             ;
  Mio.GetLine()                                          ;
  System.out.println("Sök efter ett tal: ")              ;
  if(tree.exists(Mio.GetInt())) System.out.println("OK") ;
  else System.out.println("Fanns inte")                  ;}}

Att spara binärträd

Om man under körningen bygger upp ett bra binärträd vill man troligen spara trädet på fil till nästa körning. Den metod som ligger närmast till hands är att använda write(root), men med System.out utbytt mot utfil, så som beskrivits i föreläsning 4. Men då kommer trädposterna att ligga i ordning på filen, och det betyder att man får en långtarm ner åt höger när man senare bygger upp ett nytt träd från filen. Det riktiga är att skriva ut trädet i preordning på filen. Då kommer rotposten ut först på filen och blir därmed vid senare inläsning rotpost även i det nybyggda trädet. Några sekunders eftertanke övertygar en om att hela trädet kommer att bli så som det var vid förra körningen.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 3 mars 1999
Tekniskt stöd: <webmaster@nada.kth.se>