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.
Merci!
+1: Pour l'inclusion d'une figure de référence 🙂
OriginalL'auteur tvguide1234 | 2011-02-28
Vous devez vous connecter pour publier un commentaire.
Votre question vraiment se résume à: "comment est le terme de "rang" normalement définie par rapport à un arbre AVL?" (et, éventuellement, comment est 'select' normalement défini ainsi).
Au moins que je l'ai vu le terme utilisé, "rang": la position parmi les nœuds de l'arbre -- c'est à dire, combien de nœuds sont à sa gauche. Vous êtes généralement un pointeur vers un nœud (ou peut-être une valeur de clé) et vous avez besoin de compter le nombre de noeuds à gauche de son nom.
"Select" est le contraire, vous êtes donné un rang particulier, et le besoin de récupérer un pointeur vers le nœud spécifié (ou la touche pour que le nœud).
Deux remarques: tout d'Abord, puisque ni l'un ni l'modifie l'arbre à tout, il ne fait aucune différence réelle de la forme de l'équilibrage est utilisée (par exemple, AVL vs rouge/noir); un arbre avec pas d'équilibre à tous est l'équivalent. Deuxièmement, si vous avez besoin de le faire souvent, vous pouvez améliorer considérablement la vitesse par l'ajout d'un champ supplémentaire à chaque nœud de l'enregistrement de la façon dont le nombre de nœuds est à sa gauche.
Autant que je me souvienne, c'est normalement tous les noeuds à gauche de l'arbre dans son ensemble, donc rang(10) serait de 5 ou 6 (selon si vous démarrez à partir de 0 ou 1). Désinvolte, je ne sais pas du tout de bons liens sur le sujet, mais autant que je me souvienne Introduction aux Algorithmes par Cormen, Leiserson, Rivest et Stein a un article sur elle.
Ah ok. Juste si je suis clair sur ce point; que diriez-vous de grade(13) serait de 7 ou 8 alors?
Je suppose que le principal problème des devoirs à la maison, c'est comment faire de l'équilibrage de l'arbre de manière à être en mesure de maintenir le compte. Locales pour les rotations, c'est toujours possible (donc fonctionne même avec des arbres Rouge-Noir, etc). Je crois que le nom de cette structure est de l'Ordre de la Statistique de l'Arbre. +1, si.
oui, c'est correct.
OriginalL'auteur Jerry Coffin
Le rang est le nombre de nœuds du sous-arbre Gauche, plus un, et est calculée pour chaque nœud. Je crois que le rang n'est pas un concept spécifique à AVL arbres - il peut être calculé pour tout arbre binaire.
Select est juste en face de rang. Un rang est attribué et vous devez retourner un nœud correspondant à ce grade.
Le code suivant va effectuer rang de calcul:
OriginalL'auteur JOBBINE JOSEPH
Voici le code que j'ai écrit et a bien fonctionné pour AVL Arbres pour obtenir le rang d'une valeur particulière. la différence est juste que vous avez utilisé un nœud de paramètre et j'ai utilisé une clé d'un paramètre. vous pouvez modifier ce que votre propre chemin. Exemple de code:
[N. B] Si vous voulez démarrer votre classement de 0, puis initialiser la variable rang=0.
vous avez certainement doit avoir mis en œuvre la méthode countNodes() pour exécuter ce code.
OriginalL'auteur optimus_Prime
Voici ce que j'ai fait. Dans mon programme, le rang de l'élément est défini comme le 1+(pas d'éléments plus grande que celle de l'élément). Vous pouvez noter ici que l'élément ne doit pas présent dans l'arbre.
Algorithme pour trouver le rang:
1.Dans l'arborescence de la structure de garder une trace de l'absence d'éléments dans un sous-arbre dont la racine. Donc la tête de l'arbre contient total des éléments dans l'arbre.
2.Comparer l'élément avec un nœud,si elle est plus petite que le nœud, il y a (1+n.des éléments dans le droit de l'enfant) des éléments supérieurs, l'élément clé.Ajouter le total, et de recherche de manière récursive l'élément dans la partie gauche de l'enfant.
3.Si l'élément est plus grand que le nœud racine, puis il suffit de chercher l'élément de façon récursive dans le droit de l'enfant.(pas besoin d'ajouter quoi que ce soit puisque nous sommes en négligeant l'arbre à gauche, dans laquelle tous les éléments sont de moins en moins que la clé donnée)
4.Mettre fin à l'algo lorsque vous trouvez l'élément est atteint nulle.
Le programme donné ne retourne aucun des éléments plus grande que la clé donnée. 1+ la valeur retournée est le rang.
extrait de code:
Espère que cela aide 🙂
OriginalL'auteur Darshan Bhat