.. py:module:: arbres_intervals 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 :code:`[(0, 2), (4, 7), (5, 6), (8, 9)]` és .. code-block:: python (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ó :func:`intervals.punt_central` al fitxer :download:`intervals.py` per calcular-lo: .. function:: intervals.punt_central(intervals) Retorna el punt central de la llista d'intervals. Al mòdul :mod:`arbres_intervals` (fitxer :file:`arbres_intervals.py`), dissenyeu les funcions següents: .. function:: 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: .. literalinclude:: test-classifica_interval.txt :language: python :start-after: --inici-- :end-before: --fi-- Disposeu de més jocs de proves al fitxer :download:`test-classifica_interval.txt`. .. Separació .. function:: 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: .. literalinclude:: test-classifica.txt :language: python :start-after: --inici-- :end-before: --fi-- Disposeu de més jocs de proves al fitxer :download:`test-classifica.txt`. .. note:: La funció :func:`classifica` ha de ser recursiva i ha de cridar la funció :func:`classifica_interval`. No es poden fer servir sentències :code:`for` ni :code:`while`. .. Separació .. function:: crea_arbre_intervals(intervals) Retorna un arbre d'intervals calculat a partir de la llista d'intervals donada. Per exemple: .. literalinclude:: test-crea_arbre_intervals.txt :language: python :start-after: --inici-- :end-before: --fi-- Disposeu de més jocs de proves al fitxer :download:`test-crea_arbre_intervals.txt`. .. note:: La funció :func:`crea_arbre_intervals` ha de ser recursiva i ha de cridar la funció :func:`classifica`. No es poden fer servir sentències :code:`for` ni :code:`while`. Disposeu d'una solució al fitxer :download:`arbres_intervals.py` i de jocs de proves addicionals a :download:`tests-LR4.txt `.