Спасибо за всю помощь, которую вы, ребята, предлагали мне на протяжении многих лет. Здесь возникает другая проблема, и, как обычно, любые объяснения, предложения или исправления приветствуются и приветствуются!
Я работаю над назначением в C ++ для дерева AVL, в настоящее время я работаю над вставкой, но мне также нужно реализовать удаление, так что, хотя этот пост будет тяжелым для кода вставки, любых указателей относительно того, как реализовать удаление самый простой способ понять с моим кодом было бы здорово!
Итак, у меня есть следующие функции, которые помогут мне в балансе / вставке:
int AVL :: returnBalance(Node* nodeme)
{
return (whatisHeight(nodeme->leftbaby) - whatisHeight(nodeme->rightbaby));
}
int AVL :: whatisHeight(Node* localroot)
{
if(localroot == NULL)
{
return 0;
}else
return localroot->getHeight();
}
void AVL :: adjustHeight(Node* localroot)
{
if(localroot != NULL)
{
localroot->height = 1 + max(whatisHeight(localroot->leftbaby), whatisHeight(localroot->rightbaby));
}
}
bool AVL :: contains(Node* nodeme ,int data)
{
if(!nodeme)
{
return false;
}else
if(data == nodeme->value)
{
return true;
}
if(data < nodeme->value)
{
return contains(nodeme->leftbaby,data);
}else
{
return contains(nodeme->rightbaby,data);
}
}
// Rotation
void AVL :: rotateLeft(Node* localroot)
{
Node * temp = localroot->rightbaby;
localroot->rightbaby = temp->leftbaby;
temp->leftbaby = localroot;
localroot = temp;
adjustHeight(localroot);
adjustHeight(localroot->rightbaby);
adjustHeight(temp);
}
void AVL :: rotateRight(Node* localroot)
{
Node * temp = localroot->leftbaby;
localroot->leftbaby = temp->rightbaby;
temp->rightbaby = localroot;
adjustHeight(localroot);
adjustHeight(localroot->leftbaby);
adjustHeight(temp);
localroot = temp;}
И мои вставки и вставки рекурсивных функций пишутся следующим образом
bool AVL :: add(int data)
{
if(!contains(root, data))
{
insertRecursive(root,data);
return true;
}else
{
return false;
}
}Node * AVL :: insertRecursive(Node * nodeme, int data)
{
// getting a number ready to print
int num1 = data;
string out1;
ostringstream convert1;
convert1 << num1;
out1 = convert1.str();
cout << "running recursive insert -- value: " << out1 << endl;
if(root == NULL)
{
cout << "adding root node" << endl;
Node * temporary = new Node(data);
temporary->height = 0;
root = temporary;
return root;
}else
if(nodeme == NULL)
{
cout << "adding at local" << endl;
nodeme = new Node(data);
nodeme->height = 0;
return nodeme;
}else
if(data < nodeme->value)
{
nodeme->leftbaby = insertRecursive(nodeme->leftbaby,data);
// balancing and stuff
adjustHeight(nodeme);
if ((returnBalance(nodeme) == -2 )&& (returnBalance(nodeme->leftbaby) == -1))
{
cout << "rotating right" << endl;
rotateRight(nodeme);
}else
if((returnBalance(nodeme) == -2) && (returnBalance(nodeme->leftbaby) == 1))
{
cout << "rotating left ---- 1" << endl;
rotateLeft(nodeme->leftbaby);
cout << "rotating right" << endl;
rotateRight(nodeme);
}else
if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == 1))
{
cout << "rotating left" << endl;
rotateLeft(nodeme);
}
else
if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == -1))
{
cout << "rotating right --- 2" << endl;
rotateRight(nodeme->leftbaby);
cout << "rotating left" << endl;
rotateLeft(nodeme);
}
adjustHeight(nodeme);
//
return nodeme;
}
else
{
nodeme->rightbaby = insertRecursive(nodeme->rightbaby,data);// balancing and stuff
adjustHeight(nodeme);
if ((returnBalance(nodeme) == -2 )&& (returnBalance(nodeme->leftbaby) == -1))
{
cout << "rotating right" << endl;
rotateRight(nodeme);
}else
if((returnBalance(nodeme) == -2) && (returnBalance(nodeme->leftbaby) == 1))
{
cout << "rotating left --- 3" << endl;
rotateLeft(nodeme->leftbaby);
cout << "rotating right" << endl;
rotateRight(nodeme);
}else
if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == 1))
{
cout << "rotating left" << endl;
rotateLeft(nodeme);
}
else
if((returnBalance(nodeme) == 2) && (returnBalance(nodeme- >leftbaby) == -1))
{
cout << "rotating right --- 4" << endl;
rotateRight(nodeme->leftbaby);
cout << "rotating left" << endl;
rotateLeft(nodeme);
}
cout << "adjust height" << endl;
adjustHeight(nodeme);
//return nodeme;
}
}
cout s просто для тестирования, мои классы используют данный тестовый драйвер, и, как оказалось, мое дерево не соответствует тому, что должно быть при добавлении 0,1,2,3 к 9. Сбой при добавлении 2. Обратите внимание, что повторные значения не допускаются в этом дереве, следовательно, функция содержит.
Теперь я мысленно добавляю к дереву, обновляю высоту, проверяю баланс, а затем вращаюсь, прежде чем продолжить, поэтому в уме я держу дерево сбалансированным на ходу. Очевидно, что это не правильно, поэтому мне нужно направление!
Ожидаемое дерево:
0 1
0 0
1 2
Я возвращаюсь
0 0
1 1
11 2
Я извиняюсь за то, что прочитал так много кода, и я уверен, что не так много людей действительно хотят прочитать все это, но просто взглянув на это, вы, вероятно, хотите рвать, и можете предложить отличное объяснение.
Спасибо много!
-mj
в ротации:
localroot = temp;
Вы должны передать параметр по ссылке. Если нет, фактический параметр не может быть изменен, и вы получите утечку памяти.
И то же самое делает nodeme в AVL :: insertRecursive.
Других решений пока нет …