Föreläsning 5: Binära tal, mer om binära sökträd

• Binära tal
• Rekursiva tankar för binärträd
• Binära sökträd

Binära tal (och andra baser)

Decimalt	Binärt	Oktalt	Hexadecimalt
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F
16	10000	20	10
17	10001	21	11
18	10010	22	12
19	10011	23	13
20	10100	24	14

Fråga: Hur skriver man talet n binärt?
Rekursivt svar: Först skriver man n/2 (heltalsdivision) binärt och sen skriver man en nolla eller etta beroende på om n var jämnt eller udda, ...men talen 0 och 1 skrivs likadant binärt.

def writebinary(n):
    if n == 0 or n == 1:
        print n,
    else:
        writebinary(n/2)
        print n%2,

def iso2utf(strang):
    """
    Konverterar från iso8859 till utf-8
    """
    ustrang = strang.decode('iso8859-1')
    return ustrang.encode('utf-8')

Abstrakt ordlista

    def exists(self,value):
        return finns(self.root,value)

Svårast att implementera är insättningen. Man skulle tro att satsen
putta(self.root,newvalue)
skulle kunna skicka vidare jobbet till en rekursiv metod putta, men det går inte. När trädet är tomt är rotpekaren None, men när den första noden sätts in ska rotpekaren peka på den. Men self.root kan bara ändras inifrån objektet, så därför får man skriva så här.

    def put(self,newvalue):
        self.root = putta(self.root,newvalue)

Så här blir principen för putta:

• Om p är None så har vi ett tomt träd. Då skapar vi en ny nod och låter p peka på den. Det här basfallet kommer vi så småningom till varje gång nåt ska puttas in i trädet!
• Om nya värdet är mindre än p:s värde så puttar vi in det (rekursivt) till vänster. Då kan det hända att att p.left ska få ett nytt värde (som det rekursiva anropet returnerar).
• Om nya värdet är större än p:s värde så puttar vi på samma sätt in det till höger
• Annars fanns noden redan i trädet.

def putta(p,newvalue):
    if p == None:                         # Skapa en ny nod med det nya
      - - -                               # värdet och returnera den
    if newvalue < p.value:                
        p.left = putta(p.left,newvalue)   # Rekursiv inputtning
    elif newvalue > p.value:
        p.right = putta(p.right,newvalue)
    else:                                 # Värdet fanns redan i trädet!
      - - -                             
    return p                              # Returnera pekare till det
                                          # modifierade trädet

Dessutom kan ju användaren hela tiden använda exists-funktionen för att kontrollera om det den har för avsikt att lägga till redan finns i trädet...

Sökträd med information

    class Node:
       def __init(self, key, info):
          self.key = key              # Det som man sorterar på
          self.info = info            # Objekt med information om key
          self.left = None
          self.right = None

Obalanserade träd

Det här inträffar i praktiken oftare än man kan tro, till exempel när nyfödda förs in i ett träd sorterat på personnummer och då alltid hamnar längst till höger, eller när vi lägger in tidningsartiklar sorterade efter publiceringsdatum.

Det finns många sätt att göra om ett obalanserat träd till ett balanserat. Till exempel kan man spara hela trädet i en (sorterad) lista och skapa trädet på nytt genom att ta elementen i lämplig ordning. Att göra om hela trädet tar O(n) varje gång.

Bättre är att se till att trädet är balanserat efter varje insättning. Ett sätt att göra det är röd-svarta träd där man ger varje nod en extra egenskap (röd eller svart) och ställer upp regler för hur noderna ska vara ordnade. Om reglerna tillämpas varje gång man lägger till eller plockar bort en nod så hålls trädet balanserat. Mer om detta kan man lära sig i fortsättningskursen DD1352 Algoritmer, datastrukturer och komplexitet.