Как проверить, остается ли двоичное дерево AVL, и поддерживать его?

У меня возникли некоторые проблемы с созданием древовидной структуры AVL в C ++ для университетского проекта. Пока мне удалось сделать простые функции добавления и удаления, но тут возникает проблема! Я видел здесь несколько кодов, где проверки выполняются непосредственно в функции добавления, но я не хотел копировать код. Есть ли способ создать отдельную функцию, которая делает именно эту работу? То, что я не могу заставить работать, это как заставить программу понять, в каком случае ротации мне нужно идти.

Мой код пока таков:

struct node
{
unsigned int target;
struct node *left;
struct node *right;
};

int ClassInvertedIndex::Height(struct node *toCheck)
{
int left, right;

if(toCheck == NULL)
return 0;
left = Height(toCheck->left);
right = Height(toCheck->right);
if(left > right)
return left+1;
else
return right+1;
}

void ClassInvertedIndex::maintainAVL(struct node *toCheck)
{
if(Height(toCheck->left)-Height(toCheck->right) == 2);  //Left subtree problem.

if(Height(toCheck->right)-Height(toCheck->left) == 2);  //Right subtree problem.
}bool ClassInvertedIndex::addNode(unsigned int x)
{
return insideAdd(data, x);
}bool ClassInvertedIndex::insideAdd(struct node *toAdd, unsigned int x)
{
if(toAdd == NULL)
{
toAdd = new struct node;

if(toAdd == NULL)
{
cout << "Could not allocate memory.";
return false;
}

toAdd->left = NULL;
toAdd->right = NULL;
toAdd->target = x;
return true;
}

else if(x < toAdd->target)
{
bool result;
result = insideAdd(toAdd->left, x);
if(result)
{
//maintainAVL(toAdd);
}
return result;
}

else if(x > toAdd->target)
{
bool result;
result = insideAdd(toAdd->right, x);
if(result)
{
//maintainAVL(toAdd);
}
return result;
}

else       //x already exists.
{
return false;
}
}

Итак, в методе keepAVL, что мне делать, чтобы решить, какое вращение мне нужно?

1

Решение

Задача ещё не решена.

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

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

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