Arbres d’intervals

Un arbre d’intervals és una estructura de dades que permet emmagatzemar un conjunt d’intervals de la recta real. Concretament, permet trobar de manera eficient tots els intervals que contenen un punt o que intersequem amb un interval donat.

Vegeu com es construeix un arbre d’intervals a partir d’un conjunt d’intervals.

Representarem un interval tancat com una parelles de nombres (tupla de dos elements): l’extrem inferior i l’extrem superior.

Representarem un arbre d’intervals com una tupla de 5 elements: el punt central, l’arbre dels intervals a l’esquerra del punt central, l’arbre d’intervals de la dreta del punt central, la llista d’intervals que contenen el punt central ordenada per l’extrem inferior dels intervals i la llista d’intervals que contenen el punt central ordenada per l’extrem superior dels intervals. L’arbre d’intervals buit es representa amb el valor None.

Per exemple, l’arbre d’intervals corresponent a la llista d’intervals [(0, 2), (4, 7), (5, 6), (8, 9)] és

(4.5,                                     # punt central
 (1.0, None, None, [(0, 2)], [(0, 2)]),   # arbre esquerra
 (7.0,                                    # arbre dreta
  (5.5, None, None, [(5, 6)], [(5, 6)]),
  (8.5, None, None, [(8, 9)], [(8, 9)]),
  [],
  []),
 [(4, 7)],                                # intervals ordenats per l'extrem inferior
 [(4, 7)])                                # intervals ordenats per l'extrem superior

El punt central d’una llista d’intervals és la mitjana entre l’extrem inferior més petit de la llista i l’extrem superior més gran. Disposeu de la funció intervals.punt_central() al fitxer intervals.py per calcular-lo:

intervals.punt_central(intervals)

Retorna el punt central de la llista d’intervals.

Al mòdul arbres_intervals (fitxer arbres_intervals.py), dissenyeu les funcions següents:

arbres_intervals.classifica_interval(interval, punt)

Retorna

• -1 si l’interval està a l’esquerra del punt,

• 0 si l’interval conté el punt i

• 1 si l’interval està a la dreta del punt.

Per exemple:

>>> i = -2, 2
>>> classifica_interval(i, -3)
1
>>> classifica_interval(i, -2)
0
>>> classifica_interval(i, 0)
0
>>> classifica_interval(i, 2)
0
>>> classifica_interval(i, 5)
-1

Disposeu de més jocs de proves al fitxer test-classifica_interval.txt.

arbres_intervals.classifica(intervals, punt)

Donada una llista d’intervals i un punt, retorna tres llistes:

• la dels intervals que estan a l’esquerra del punt,

• la dels intervals que contenen el punt i

• la dels intervals que estan a la dreta del punt.

Per exemple:

>>> li = [(-3, 0), (-1, 2), (3, 7), (5, 6), (8, 9)]
>>> classifica(li, -5)
([], [], [(-3, 0), (-1, 2), (3, 7), (5, 6), (8, 9)])
>>> classifica(li, 0)
([], [(-3, 0), (-1, 2)], [(3, 7), (5, 6), (8, 9)])
>>> classifica(li, 2.5)
([(-3, 0), (-1, 2)], [], [(3, 7), (5, 6), (8, 9)])
>>> classifica(li, 7)
([(-3, 0), (-1, 2), (5, 6)], [(3, 7)], [(8, 9)])
>>> classifica(li, 10)
([(-3, 0), (-1, 2), (3, 7), (5, 6), (8, 9)], [], [])

Disposeu de més jocs de proves al fitxer test-classifica.txt.

Nota

La funció classifica() ha de ser recursiva i ha de cridar la funció classifica_interval(). No es poden fer servir sentències for ni while.

arbres_intervals.crea_arbre_intervals(intervals)

Retorna un arbre d’intervals calculat a partir de la llista d’intervals donada.

Per exemple:

>>> from pprint import pprint

>>> li = [(0, 2), (4, 7), (5, 6), (8, 9)]
>>> a = crea_arbre_intervals(li)
>>> pprint(a)
(4.5,
 (1.0, None, None, [(0, 2)], [(0, 2)]),
 (7.0,
  (5.5, None, None, [(5, 6)], [(5, 6)]),
  (8.5, None, None, [(8, 9)], [(8, 9)]),
  [],
  []),
 [(4, 7)],
 [(4, 7)])

Disposeu de més jocs de proves al fitxer test-crea_arbre_intervals.txt.

Nota

La funció crea_arbre_intervals() ha de ser recursiva i ha de cridar la funció classifica(). No es poden fer servir sentències for ni while.

Disposeu d’una solució al fitxer arbres_intervals.py i de jocs de proves addicionals a tests-LR4.txt.