Блог

Я пытаюсь сбалансировать дерево AVL с 10 узлами. Когда я запускаю код в Xcode, он работает нормально и проходит все три теста, но при попытке отправить этот проект я получаю ошибку тайм-аута. Существует класс AVLTree, в котором также используются вспомогательные функции. Я действительно заблудился, я верю, что есть петля, которая не заканчивается, но я застрял там, где это происходит внутри AVLTree.cpp

 //AVLTree.h

#include <iostream>

class AVLTree {
public:
int data;
uint32_t height;
AVLTree* parent;
AVLTree* left;
AVLTree* right;

//base functions defined for you
AVLTree(int data, AVLTree* parent=nullptr, AVLTree* left=nullptr, AVLTree* right=nullptr);
bool isLeaf();
uint32_t getHeight();

//*******************
//functions you need to define

//insert a node and rebalance tree to maintain AVL balanced tree
//return new root of tree
AVLTree* insert(int data);

//computes a node's balance factor by subtracting the right subtree height from the left subtree height.
int getBalance();

//checks for imbalance and rebalances if neccessary
//return new root of tree
AVLTree* rebalance();


//implement a right rotate
//return new root of tree
AVLTree* rotateRight();

//implement a left rotate
//return new root of tree
AVLTree* rotateLeft();

//Do not edit these three functions
bool isBalanced();
uint32_t countNodes();
void updateHeight();
};

//AVLTree.cpp

#include "AVLTree.h"

#include <iostream>

using namespace std;
//************** already implemented helper functions
AVLTree::AVLTree(int t_data, AVLTree* t_parent, AVLTree* t_left, AVLTree* t_right) {
data = t_data;
height = 0;
parent = t_parent;
left = t_left;
right = t_right;
}

bool AVLTree::isLeaf() {
return ((left == nullptr) and (right == nullptr));
}

uint32_t AVLTree::getHeight() {
if (left == nullptr amp;amp; right == nullptr) {
return 0;
}
int i = max (left == nullptr ? 0 : left -> getHeight(), right == nullptr ? 0 : right -> getHeight())   1;
return i;
}

//******************************************************

int AVLTree::getBalance() {
int i = (left == nullptr ? 0 : left->height) - (right == nullptr ? 0 : right->height);
int j = abs(i);
return j;
}

AVLTree* AVLTree::rotateRight() {
AVLTree* u = left;
left = u->right;
u->right = this;
return u;
}

AVLTree* AVLTree::rotateLeft() {
AVLTree* u = right;
right = u->left;
u->left = this;
return u;

}

AVLTree* AVLTree::rebalance() {
if (isLeaf()) {
return this;
}
if (left != nullptr) {
left = left -> rebalance();
}
if (right != nullptr) {
right = right -> rebalance();
}

int isBal = isBalanced();
if (!isBal) {
// Rebalance this (me)

if ((left == nullptr ? 0 : left -> getHeight()) < (right == nullptr ? 0 : right -> getHeight())) {
if (right -> left != nullptr) {
right = right -> rotateRight();
AVLTree *t = rotateLeft();

return t;
}
else if(right -> right != nullptr) {
AVLTree *t = rotateLeft();

return t;
}
}
else if ((left == nullptr ? 0 : left -> getHeight()) > (right == nullptr ? 0 : right -> getHeight())) {
if (left -> right != nullptr) {
left = left -> rotateLeft();
AVLTree *t = rotateRight();

return t;
}
else if(left -> left != nullptr) {
AVLTree *t = rotateRight();

return t;
}
}
}
return this;
}

AVLTree* AVLTree::insert(int new_data) {
AVLTree *root = this;
if (new_data < data) {
if (this -> left != nullptr)
{
left = left -> insert(new_data);
}
else {
this -> left = new AVLTree(new_data, this);
}
}
else if (new_data > data) {
if (this -> right != nullptr)
{
right = right -> insert(new_data);
}
else {
this -> right = new AVLTree(new_data, this);
}
}

// always return the root!
root -> updateHeight();

bool isBal = isBalanced();
if (isBal == false) {
AVLTree *rtn = rebalance();

rtn -> updateHeight();
return rtn;
}

return root;
}




//***************************
//Do not edit code below here
uint32_t AVLTree::countNodes() {
if (isLeaf()) {
return 1;
}
if (left != nullptr) {
if (right != nullptr) {
return 1   left->countNodes()   right->countNodes();
}
return 1  left->countNodes();
}
return 1   right->countNodes();
}

void AVLTree::updateHeight() {
if (isLeaf()) {
height = 0;
return;
}
if (left != nullptr) {
left->updateHeight();
if (right != nullptr) {
right->updateHeight();
height = (1   max(left->getHeight(), right->getHeight()));
return;
}
height = 1   left->getHeight();
return;
}
right->updateHeight();
height = 1   right->getHeight();
return;
}

bool AVLTree::isBalanced() {
if ( isLeaf() ) {
return true;
}
if (left == nullptr) {
return ( right->getHeight() < 1 );
}
if (right == nullptr) {
return ( left->getHeight() < 1 );
}
return ( left->isBalanced() and right->isBalanced() and abs(getBalance() < 2) );
}

//Main.cpp

#include <fstream>
#include <iostream>
#include <cmath>
#include <time.h>
#include <stack>
#include <queue>

#include "AVLTree.h"

using namespace std;


int main() {

AVLTree* tree1Root = new AVLTree(50, nullptr);
srand(time(NULL));
uint32_t numNodes = 10;
for (uint32_t i=1; i < numNodes; i   ) {
tree1Root = tree1Root->insert(( rand() % 10000));


std::cout<<"Balanced? "<< tree1Root -> isBalanced() <<std::endl;
}

// //Uncomment to help debug lost nodes
//// if (tree1Root->countNodes() != i 2) {
//// std::cout<<"Lost node "<<std::endl;
//// return 1;
//// }
//
// //uncomment to help debug unbalanced trees
//// tree1Root->updateHeight();
//// if ( ! tree1Root->isBalanced() ) {
//// std::cout<<"Tree1Root balanced: FAILED at node insertion "<<i<<std::endl;
//// return 1;
//// }
//
// }

if (tree1Root->countNodes() == numNodes) {
std::cout<<"tree1Root lost Nodes: PASSED"<<std::endl;
}
else {
std::cout<<"tree1Root lost Nodes: FAILED expected: 10 actual: "<<tree1Root->countNodes()<<std::endl;
}

tree1Root->updateHeight();
float expectedHeight = log2(numNodes) * 1.5;
if (tree1Root->getHeight() < expectedHeight) {
std::cout<<"tree1Root height: PASSED"<<std::endl;
}
else {
std::cout<<"tree1Root height: FAILED expected: <" <<expectedHeight<<" actual: "<<tree1Root->getHeight()<<std::endl;
}

if ( tree1Root->isBalanced()) {
std::cout<<"Tree1Root is balanced: PASSED"<<std::endl;
}
else {
std::cout<<"Tree1Root is balanced: FAILED"<<std::endl;
}
}