Problème arbres rouges et noirs

Bonjour,
Je développe une simulation de collision (billard) et j'ai besoin d'arbres pour stocker les collisions. J'ai trouvé plusieurs librairies et pour le moment la meilleure est http://en.literateprograms.org/Red-black_tree_(C)

Par contre je ne comprends pas trop à quoi correspondent la clé et la valeur de chaque nœud. Apparemment la clé est "l'adresse" du noeud et la valeur est la donnée contenue dans ce noeud. L'arbre est trié selon les clés ou les valeurs ?

J'ai besoin d'une fonction qui rajoute des données à un arbre mais le problème c'est que si il faut maintenir une liste des différentes clés disponible cela risque d'être compliqué/lourd/lent. Est-ce qu'il y a un moyen pour attribuer "automatiquement" la clé d'un noeud ?

Que veut dire (void*)x (x entier) ?

Merci.