équilibrer un arbre AVL (C++)
j'ai du mal à trouver comment équilibrer un arbre AVL pour ma classe. Je l'ai d'insertion avec ceci:
Node* Tree::insert(int d)
{
cout << "base insertt" << d << endl;
if (head == NULL)
return (head = new Node(d));
else
return insert(head, d);
}
Node* Tree::insert(Node*& current, int d)
{
cout << "insertt" << d << endl;
if (current == NULL)
current = new Node(d);
else if (d < current->data) {
insert(current->lchild, d);
if (height(current->lchild) - height(current->rchild)) {
if (d < current->lchild->getData())
rotateLeftOnce(current);
else
rotateLeftTwice(current);
}
}
else if (d > current->getData()) {
insert(current->rchild, d);
if (height(current->rchild) - height(current->lchild)) {
if (d > current->rchild->getData())
rotateRightOnce(current);
else
rotateRightTwice(current);
}
}
return current;
}
mon plan était d'avoir les appels à équilibrer () vérifier pour voir si l'arbre a besoin d'équilibrage et puis l'équilibre si nécessaire. Le problème est que je ne peux même pas comprendre comment parcourir l'arborescence pour trouver la bonne déséquilibrée nœud. Je sais comment traverser l'arbre de façon récursive, mais je ne peux pas traduire cet algorithme pour trouver le plus bas déséquilibre. nœud. J'ai aussi du mal à écrire un algorithme itératif. Toute aide serait appréciée. :)
4 réponses
vous pouvez mesurer le height d'une branche à un point donné pour calculer le déséquilibre
(rappelez-vous une différence dans la hauteur (niveaux) >= 2 signifie que votre arbre n'est pas équilibré)
int Tree::Height(TreeNode *node){
int left, right;
if(node==NULL)
return 0;
left = Height(node->left);
right = Height(node->right);
if(left > right)
return left+1;
else
return right+1;
}
selon l'inégalité alors vous pouvez rotation selon les besoins
void Tree::rotateLeftOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->left;
node->left = otherNode->right;
otherNode->right = node;
node = otherNode;
}
void Tree::rotateLeftTwice(TreeNode*& node){
rotateRightOnce(node->left);
rotateLeftOnce(node);
}
void Tree::rotateRightOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->right;
node->right = otherNode->left;
otherNode->left = node;
node = otherNode;
}
void Tree::rotateRightTwice(TreeNode*& node){
rotateLeftOnce(node->right);
rotateRightOnce(node);
}
maintenant que nous savons comment tourner, disons que vous voulez insert une valeur dans l'arbre... Tout d'abord, nous vérifions si l'arbre est vide ou pas
TreeNode* Tree::insert(int d){
if(isEmpty()){
return (root = new TreeNode(d)); //Is empty when root = null
}
else
return insert(root, d); //step-into the tree and place "d"
}
Lorsque l'arbre n'est pas vide, on utilise la récursivité traverser l'arbre et se rendre là où il le faut
TreeNode* Tree::insert(TreeNode*& node, int d_IN){
if(node == NULL) // (1) If we are at the end of the tree place the value
node = new TreeNode(d_IN);
else if(d_IN < node->d_stored){ //(2) otherwise go left if smaller
insert(node->left, d_IN);
if(Height(node->left) - Height(node->right) == 2){
if(d_IN < node->left->d_stored)
rotateLeftOnce(node);
else
rotateLeftTwice(node);
}
}
else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
insert(node->right, d_IN);
if(Height(node->right) - Height(node->left) == 2){
if(d_IN > node->right->d_stored)
rotateRightOnce(node);
else
rotateRightTwice(node);
}
}
return node;
}
vous devriez toujours vérifier le solde (et faire des rotations, si nécessaire) lors de la modification de l'arbre, pas de point d'attente jusqu'à la fin lorsque l'arbre est un gâchis pour l'équilibrer. Que juste complique les choses...
UPDATE
Il y a une erreur dans votre implémentation, dans le code ci-dessous vous ne Vérifiez pas correctement si l'arbre est déséquilibré. Vous devez vérifier si la hauteur est égale à 2 (donc déséquilibre). En conséquence, le code ci-dessous...
if (height(current->lchild) - height(current->rchild)) { ...
if (height(current->rchild) - height(current->lchild)) {...
Devrait devenir...
if (height(current->lchild) - height(current->rchild) == 2) { ...
if (height(current->rchild) - height(current->lchild) == 2) {...
Ressources
attendez, attendez, Attendez. Tu ne vas pas vraiment vérifier la "hauteur" de chaque branche à chaque fois que tu insères quelque chose, n'est-ce pas?
mesurer la hauteur signifie traverser toute la sous-branche. Moyens - chaque insert dans un tel arbre coûtera O (N). Si oui, - de quoi avez-vous besoin d'un tel arbre? Vous pouvez utiliser un tableau trié aussi bien: il donne O(N) insertion/suppression et o (log N) recherche.
un algorithme de manipulation AVL correct doit magasin la hauteur gauche / droite différence à chaque nœud. Puis, après chaque opération (insérer/supprimer) - vous devez vous assurer qu'aucun des nœuds touchés seront trop déséquilibrées. Pour ce faire, vous les soi-disant "rotations". Au cours de leur vous ne pas en fait, re-mesurer les hauteurs. Vous n'avez pas à le faire: chaque rotation change l'équilibre des noeuds affectés par une valeur prévisible.
goto http://code.google.com/p/self-balancing-avl-tree/, Toutes les opérations habituelles comme add, delete sont implémentées, plus concat et split
commenté est le code rotation droite au-dessus et rotation gauche, ci-dessous est ma rotation droite de travail et ma rotation gauche de travail. Je pense que la logique dans la rotation ci-dessus est inversée:
void rotateRight(Node *& n){
//Node* temp = n->right;
//n->right = temp->left;
//temp->left = n;
//n = temp;
cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl;
Node *temp = n->left;
n->left = temp->right;
temp->right = n;
n = temp;
}
void rotateLeft(Node *& n){
//Node *temp = n->left;
//n->left = temp->right;
//temp->right = n;
//n = temp;
cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl;
Node* temp = n->right;
n->right = temp->left;
temp->left = n;
n = temp;
}