Comment trouver le rang d'un nœud dans un arbre AVL?

J'ai besoin de mettre en œuvre deux rang des requêtes [rank(k) et select(r)]. Mais avant que je puisse commencer sur ce, j'ai besoin de comprendre comment les deux fonctions de travail.

Autant que je sache, rank(k) renvoie le rang d'une clé donnée k, et select(r) retourne la clé d'un rang r.

Donc mes questions sont:

1.) Comment calculer le rang d'un nœud dans un AVL(auto-équilibrage de la BST)?

2.) Est-il possible pour plus d'une touche à avoir le même rang? Et si oui, quel woulud select(r) retour?

Je vais inclure un échantillon AVL arbres que vous pouvez consulter si elle permet de répondre à la question.

Comment trouver le rang d'un nœud dans un arbre AVL?

Merci!

+1: Pour l'inclusion d'une figure de référence 🙂

OriginalL'auteur tvguide1234 | 2011-02-28