Вставка дерева AVL — реализация

Спасибо за всю помощь, которую вы, ребята, предлагали мне на протяжении многих лет. Здесь возникает другая проблема, и, как обычно, любые объяснения, предложения или исправления приветствуются и приветствуются!

Я работаю над назначением в 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

0

Решение

в ротации:

localroot = temp;

Вы должны передать параметр по ссылке. Если нет, фактический параметр не может быть изменен, и вы получите утечку памяти.


И то же самое делает nodeme в AVL :: insertRecursive.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector