Благодарим вас за помощь, которую вы, ребята, предложили мне на протяжении многих лет. Здесь возникает еще одна проблема, и, как обычно, приветствуются и оцениваются любые объяснения, предложения или исправления!AVL Tree Insertion - Реализация
Я работаю над назначением на 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;
}
И моя вставка и insertionrecursive функции записываются следующим образом
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. Примечание. Повторные значения не допускаются в этом дереве, следовательно, содержит функцию.
Теперь, на мой взгляд, я добавляю к дереву, обновляя высоту, проверяя баланс, а затем вращаюсь, прежде чем продолжить, поэтому, на мой взгляд, я держу свое дерево сбалансированным, когда я иду. Очевидно, что это не выполняется правильно, поэтому мне нужно какое-то направление!
Ожидаемое дерево:
Я возвращаюсь
Я прошу прощения через столько код там, и я уверен, что мало кто действительно хочет прочитать все это, но просто взглянув на него, возможно, вы хотите рвать и можете предложить отличное объяснение.
Спасибо вам большое! -mj