Arbres binaires de recherche de villes

L’objectif du projet est d’écrire un algorithme permettant de retrouver toutes les villes comprises dans un carreau rectangulaire délimité par les points de latitude et longitude (φ1, λ1),(φ2, λ1),(φ1, λ2),(φ2, λ2). Pour ce faire nous nous proposons d’étudier les trois approches suivantes : Un arbre binaire de recherche La première approche, la plus simple, consiste à stocker les villes en utilisant une des coordonnée comme clé (par exemple la latitude). Il s’agirait donc de : 1. Rechercher Sφ, l’ensemble des villes comprises entre deux latitudes ; 2. Filtrer Sφ pour ne garder que les villes comprises entre deux longitudes S. Deux arbres binaires de recherche La seconde approche, consiste à stocker les villes dans deux arbres binaires de recherche. Le premier admet comme cl ́e les latitudes des villes et le second leur longitude. Il s’agira donc de 1. Rechercher Sφ, toutes les villes comprises entre deux latitudes ; 2. Rechercher Sλ, toutes les villes comprises entre deux longitudes ; 3. Calculer l’intersection de ces deux ensembles : S = Sφ ∩ Sλ. Un arbre binaire de recherche avec Z-score La troisième approche repose sur un seul arbre de recherche qui utilise comme clé une combinaison de la latitude et de la longitude k = Z(φ, λ) qui garantit que Z(φm, λm) ≤ Z(φ, λ) ≤ Z(φM, λM) pour φm ≤ φ ≤ φM ∧ λm ≤ λ ≤ λM. On peut alors retrouver les villes de la mani`ere suivante : 1. On recherche SZ, toutes les villes dont les clés sont comprises entre Z(φm, λm) et Z(φM, λM) oú φm = min{φ1, φ2}, λm = min{λ1, λ2}, φM = max{φ1, φ2} et λM = max{λ1, λ2}. 2. On filtre SZ pour ne garder que l’ensemble S des bonnes villes. On utilisera le code de Morton comme fonction Z. Celui-ci consiste à entrelacer les bits des coordonnées.