Comment fonctionne un tri d'insertion pour un BST de tableau?

Question

J'ai essayé de le faire récursivement .. L'entier parent varaible serait comme je, conforme à la formule, 2*i +1 pour leftChild et 2*i +2 pour la droite.

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; 
     items[Parent].empty = false; 
    } 
    else if (aData < items[Parent].theData) 
    { 
     Parent = 2 * Parent + 1; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
    else 
    { 
     Parent = (2 * rightChild++)+ 2; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
} 

Il fonctionne très bien lors de l'insertion des éléments qui sont moins que le parent d'origine ... Mais quand je trouve quelque chose qui est plus grand, il toutes Fout: x

void BST::reallocate() 
{ 
    item *new_array = new item[maxSize*2]; 

    for (int array_index = 0; array_index < maxSize; array_index++) 
    { 
     if (! items[array_index].empty) 
     { 
      new_array[array_index].theData = items[array_index].theData; 
     } 
    } 
    maxSize *= 2; 
    delete [] items; 

    items = NULL; 
    items = new_array; 
} 

Voici mon cteur si personne ne se confond alors plus je suis:

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array 

la fonction d'insertion ci-dessus est en fait le meilleur que je peux obtenir ..

        R 
           /\ 
          / \ 
          / \ 
          L  X 
          /\ /\ 
          J V K T <--The only out of place node. 
         /\ \ 
         /NULL \ 
         G  /
           P 

Lors de l'insertion: R, L, J, G, X, K, V, P, T dans cet ordre

Answer 1

Je soupçonne que votre problème est sur cette ligne:

Parent = (2 * rightChild++)+ 2; 

Pourquoi utilisez-vous rightChild ici au lieu de (2 * Parent) + 2?

Pour rendre les choses plus claires, vous pouvez ajouter des fonctions en ligne simples à votre classe pour calculer les indices des enfants gauche/droite et le parent, étant donné un indice:

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; } 
inline int getRightChildIndex(int nodeNdx) { ... } 
inline int getParentIndex(int nodeNdx) { ... } 

Vous pouvez également envisager d'utiliser les méthodes search() ou find() (je suppose qu'il en a un) pour déterminer où insérer un nouveau nœud. La fonction de recherche doit renvoyer l'index d'un nœud existant (à vous de décider comment gérer l'insertion de valeurs dupliquées) ou l'index de l'endroit où la nouvelle valeur doit être insérée.