Structure de données pour contenir et récupérer des points dans un plan
-
01-11-2019 - |
Question
Définition 1: Point $ (x, y) $ contrôle le point $ (x ', y') $ si et seulement si $ x <x '$ et $ y <y' $.
Définition 2: Point $ (x, y) $ est contrôlé par le point $ (x ', y') $ si et seulement si $ x '<x $ et $ y' <y $.
J'essaie de proposer une structure de données pour soutenir les opérations suivantes:
$ mathrm {add} (x, y) $ - ajoute un point $ (x, y) $ au système dans $ mathcal {o} ( log n) $ complexité où $ n $ est le nombre de points dans le système.
$ mathrm {supprimer} (x, y) $ - supprime un point $ (x, y) $ du système dans $ mathcal {o} ( log n) $ complexité où $ n $ est le nombre de points dans le système.
$ mathrm {score} (x, y) $ - Renvoie le nombre de points $ (x, y) $ contrôle - nombre de points que $ (x, y) $ est contrôlé par. Pire complexité de cas $ mathcal {o} ( log n) $.
J'ai essayé de le résoudre en utilisant plusieurs arbres AVL, mais je n'ai pas pu trouver une solution suffisamment élégante.
Cette question est apparue à mes examens il y a quelques jours. La question devrait avoir relativement simple car elle valait 15 $ / 100 $ de points. J'ai essayé de résoudre ce problème par plusieurs arbres AVL mais je n'ai pas pu trouver une solution suffisamment élégante.
Les conseils sont les bienvenus.
Pas de solution correcte