1. Arbres

1.1. Arbres de cerca

""" Problema de arbres 26/05/11 Problema: C={3,15,4,16,-2}

a)Implemen trivial en una llista

c=[3,15,4,16,-2] c.find()---> X E(pertany)C cost O(n) b)Com millorar el cost? -representem c en un arbre binari

• 15

• 3 16

• -2 4

Arbre binari de cerca - Es un arbre binari P1 . pertany subarbre de S

• Fe(s) conte valors menors que s Fd(s) conte valors majors que s

per exemple el sub arbre format per 3 -2 i 4 es fe(15) i 16 es fd(15)

Cost de cerca

Si partim un arbre per nivells: En el n=0 un elemen. En el n=1 2 elements en el n=2 4 elements en el n=3 8 elements

nivell n = 2**n arbre d'alçada n= sumatori de 2**n= 2**(n+1)-1

---

Per C(elements): C= 7 ---> alçada 3 C= 15---> alçada 4 C= 10---> alçada 4

Cost O(log(base2)n) si arbre equilibrat

""" #Implementació #Operacions: Insertar, restar, pertany

class Acerca(object):

• def init(self,p=None):#crea un arbre buit un p es el pare

  • self.esq=self.dret=self.v=None self.pare=p
  def buit(self):
  • return self.v==None
  def arrel(self):
  • return not self.pare
  def es_fe(self):#es fill esquerra, self=fill esq
  • return self.pare.esq==self
  def es_fd(self):
  • return self.pare.dre==self
  def pertany(self,k):
  • if self.buit():
    • return False
    elif self.v==k:
    • return True

    elif self.v>k:#self.v valor darrel

    • return self.esq.pertany(k)

    elif self.v< k:

    • return self.dre.pertany(k)
  def insereix (self,k):
  • if self.buit():
    • self.v=k self.dre = Acerca(p=self) #creem un nou constructor self.esq = Acerca(p=self)
    elif self.v==k:
    • raise Exception ('duplicat')

    elif self.v>k:

    • self.esq.insereix(k)

    elif self.v<k:

    • self.dre.insereix(k)

""" Esborrat 1)esborrar fulla

• 5

• 10 20 esborrar 20

2) esborrar fill unic

• 15

• 10 20

• 7

3) Esborrar node 2 fills

• 15

• 10 20

• 7 12

• 5 8 11 14

1)buscar substitut k sera el 8 ja que el 8 es el mes gran dels mes petits de 10 o el 11 k es el mes petit del mes gran que 10 2)substituir 3)Esborrar substitut

"""

• def minim(self):
  • if self.buit():
    • return None
    else:
    • t=self while not.esq.buit():
      • t=t.esq
      return t
  def esborra(self,k):
  • if self.buit():
    • return

    elif self.v>k:

    • self.esq.esborra(k)

    elif self.v<k:

    • self.dre.esborra(k)
    elif self.v==k:
    • if self.esq.buit() and self.dre.buit():
      • if self.es_fe():
        • self.pare.esq=Acerca(p=self.pare)
        else:
        • self.pare.dre= Acerca(p=self.pare)#el node fulla keda omplert amb pare
      elif self.esq.buit():#si resulta k el meu fill esk es buit
      • #aixo significa k nomes en tinc dret
      • if self.es_fe():
        • pare=self.pare #apuntu pk sigui mes comode, no es estr. necesari. if self.es_fe():
          • pare.esq= self.dre self.dre.pare=pare
      elif self.dre.buit():#el mateix codi k per el fill esq
      • pass
      else:#cas de 2 fills(3)
      • m= self.dre.minim() v=m.v m.esborra(v) self.v=v