Le calcul de rang d'un nœud dans un arbre de recherche binaire

Si chaque nœud dans un arbre de recherche binaire magasins de son poids (nombre de nœuds de son sous-arbre), ce qui serait une méthode efficace pour calculer le rang d'un nœud donné (son index dans la liste triée) que je recherche dans l'arbre?

OriginalL'auteur dissem | 2014-09-28

  1. 12

    Commencer le rang à partir de zéro. Comme le binaire de recherche se poursuit à partir de la racine, ajouter les tailles de tous les sous-arbres gauche que la recherche ignore, y compris le sous-arbre gauche d'un nœud.

    I. e., lorsque la recherche va de gauche (de la mère à gauche de l'enfant), il découvre aucune nouvelle des valeurs inférieures à l'élément recherché, de sorte que le classement reste le même. Quand il va à droite, le parent, en plus de tous les nœuds du sous-arbre gauche sont moins de l'élément recherché, afin d'ajouter un plus le sous-arbre gauche de la taille. Quand il en trouve l'élément recherché. tous les éléments, à gauche dans le sous-arbre du nœud contenant l'élément sont de moins qu'elle, alors ajoutez à cela le rang.

    Mettre tous ensemble:

    int rank_of(NODE *tree, int val) {
  int rank = 0;
  while (tree) {
    if (val < tree->val) //move to left subtree
      tree = tree->left;
    else if (val > tree->val) {
      rank += 1 + size(tree->left);
      tree = tree->right;
    }
    else 
      return rank + size(tree->left);
  }
  return NOT_FOUND; //not found
}

    Ceci renvoie à la base zéro rang. Si vous avez besoin de base 1 puis initialiser rank à 1 au lieu de 0.

    C'est génial !
    Votre solution est simple et propre. J'ai essayé de résoudre ce problème par le maintien de tous les enfants de compter à chaque nœud. Qui est complexe et sujette à des erreurs au lieu de cela, il est beaucoup plus facile de maintenir la taille du sous-arbre gauche comme vous l'avez fait. Merci!

    OriginalL'auteur Gene

  2. 2

    Depuis chaque nœud dispose d'un champ de stockage de son poids, de la première à mettre en œuvre un appel de la méthode size() qui renvoie le nombre de noeuds dans un nœud substree:

    private int size(Node x)
{
if (x == null) return 0;
else return x.N;
}

    puis calculer le rang d'un nœud donné est facile

    public int rank(Node key)
{ return rank(key,root) }

    private int rank(Node key,Node root)
    {
        if root == null 
             return 0;
        int cmp = key.compareTo(root);
//key are smaller than root, then the rank in the whole tree
//is equal to the rank in the left subtree of the root.
        if (cmp < 0) {
            return rank(key, root.left) 
        } 
//key are bigger than root,the the rank in the whole tree is equal
//to the size of subtree of the root plus 1 (the root) plus the rank 
//in the right sub tree of the root.
        else if(cmp > 0){
            return size(root.left) + 1 + rank(key,root.right); 
        } 
//key equals to the root, the rank is the size of left subtree of the root
        else return size( root.left);  
    }
    La dernière else n'est pas correct. Seule la gauche de la sous-arborescence de la racine contient des éléments moins que la recherche de la valeur.

    OriginalL'auteur Jade Tang

  3. 0

    Dépend de la BST de la mise en œuvre, mais je crois que vous pouvez le résoudre de manière récursive. 

    public int rank(Key key){
    return rank(root, key);
}

private int rank(Node n, Key key){
    int count = 0;
    if (n == null)return 0;
    if (key.compareTo(n.key) > 0) count++;
    return count + rank(n.left, key) + rank(n.right, key);
}

    OriginalL'auteur Joe Drool