Arbre de recherche binaire «continu»

Question

J'essaie de créer une structure de données «continue» en prenant un nombre rationnel non négatif, x, comme une clé. La recherche de x comme la clé renverra l'élément unique qui a x comme une clé, sinon le plus grand de tous les éléments plus petit que x sera retourné.

est ici une image pour montrer, ici où la clé de recherche, x, est de 5,1

Search

Mon algorithme proposé modifie l'arbre binaire normale recherche un peu: Chaque fois qu'un droit chemin est pris (donc la clé est plus grande que le noeud) ce noeud est ajouté à un vecteur. Si aucun nœud n'est trouvé après la recherche d'arbre binaire, le plus grand nœud du vecteur est choisi comme résultat.

est-il: classe

1. un (java) qui fait déjà?
2. un moyen facile de "pirater" une classe existante pour ce faire?
3. une meilleure collection pour ce faire?

Answer 1

Vous pouvez résoudre votre problème grâce à l'utilisation d'un NavigableMap. Vous pouvez utiliser NavigableMap#lowerEntry qui:

Renvoie une cartographie clé-valeur associée à la plus grande clé strictement inférieure à la clé donnée, ou null s'il n'y a pas de clé.

Avec ceci, vous pouvez facilement saisir l'élément évalué le plus haut.