parent de réglage sur l'arbre AVL

Question

Je suis en train de mettre en œuvre un arbre AVL et pas sûr de la meilleure façon de faire insérer et de suivre le parent de chaque nœud. Ceci est donc l'éducation s'il vous plaît ne suggèrent pas « coup de pouce d'utilisation »:)

Ce compiles mais je ne suis pas convaincu de son exactitude ou qu'il est la meilleure façon. Plus précisément, cette

insert(someNumber,root,root);

En outre, je vais refaire la partie de la hauteur quand je rééquilibrer et déplacer l'arbre.

insérer comme ceci

myTree.insert(someNumber);

Voici la méthode. Je ne sais pas ce que mon deuxième devrait être ici param. J'aurais pensé NULL mais le compilateur ne fonctionne pas comme ça (autre définition de la fonction).

void Tree::insert(int someNumber){
    insert(someNumber,root,root);
}

Voici mon insertion

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
    if(subTreeRoot==NULL)
    {
        subTreeRoot = new Node(someNumber,parent);
        if(subTreeRoot->myParent)   
    }
    else if (someNumber<subTreeRoot->myNumber)
    {
        if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->left,subTreeRoot);
    }
    else
    {
        if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->right,subTreeRoot);
    }
}

-

Answer 1

Puisque vous faites cela pour l'éducation, je vous suggère de travailler certains cas à la main, puis les code dans les tests de la forme

 Insert(6);
 Insert(11);
 // ...
 Insert(3);

 Node test = root;
 assert(root->height == 3);
 assert(root->value == 6);
 test = root->right;
 assert( ... );

les chiffres sont complètement composé.

Cette volonté

1. Donnez-vous plus qu'un sentiment de savoir si oui ou non votre code fonctionne. (Astuce: si vous n'êtes pas sûr que votre code fonctionne, il est sans doute pas)
2. Donnez-vous un endroit pour commencer déterminer ce qui va mal.
3. Développer l'habitude des tests. Il est contre-intuitif à certaines personnes que l'écriture deux fois plus beaucoup de code (le code des tests +) est plus rapide que simplement écrire le code en premier lieu, mais l'essayer. De plus écrire plus de code = plus pratique.

Answer 2

Quelle est la différence entre un arbre et un nœud? (Un arbre est titulaire seul endroit pour le nœud racine, rien nœud plus. A dit parfois d'avoir deux sous-arbres. Arbre et le nœud ne sont pas différents. Une classe suffirait.)

Pourquoi ne pas calculer la hauteur à chaque fois que vous en avez besoin? Beaucoup plus facile à programmer et une preuve correcte. Si la performance vous fait du mal, vous pouvez toujours changer la fonction pour renvoyer une valeur en cache.

noeud A ne devrait pas savoir parent de ce (à mon avis). Ainsi, la fonction d'insertion a besoin d'un paramètre parent. Après avoir créé le nouveau noeud comparer les profondeurs parents-enfants pour voir si vous avez besoin de faire des rotations. Programmation des rotations est délicate: essayer, déboguer et de tester

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}