AVL 트리 재귀없이 삽입 C++

Question

AVL 트리 삽입을 구현하는 데 다음 코드를 사용하고 있지만 적절한 순서로 표시하지 않거나 높이를 업데이트하지 못했습니다. 삽입 기능이 완료되면 해당 기능을 완료 할 수 있기 때문에 일부 기능이 남아 있습니다.

AVLNode.cpp

#include <iostream> 
    #include <string> 
    #include "AVLNode.h" 
    using namespace std; 

    AVLNode::AVLNode(string ss, string na){ 
     ssn = ss; 
     name = na; 
     height = 0; 
     left = NULL; 
     right = NULL; 
     parent = NULL; 
    } 

AVLNode.h

#include <iostream> 
    #include <string> 
    using namespace std; 

    struct AVLNode{ 
     string ssn; 
     string name; 
     AVLNode *left; 
     AVLNode *right; 
     AVLNode *parent; 
     int height; 

     AVLNode(string ss, string na); 
    }; 

AVLTree.cpp

#include <iostream> 
#include <string> 
#include <stdio.h> 
#include "AVLTree.h" 
#include <iomanip> 
#include <queue> 
using namespace std; 

AVLTree::AVLTree(){ 
    root = NULL; 
} 

AVLTree::~AVLTree(){ 


} 

AVLNode* AVLTree::getRoot(){ 
    return root; 
} 


// search value ss in the AVL tree 
bool AVLTree::find(string ss){ 
    if (root == NULL) { 
     return false; 
    } 

    AVLNode* node = root; 

    while (node != NULL) { 
     if (ss.compare(node->ssn) == 0) { 
      return true; 
     } 
     if (ss.compare(node->ssn) < 0) { 
      node = node->left; 
     } 
     else{ 
      node = node->right; 
     } 
    } 
    return false; 
} 

// return the height of the subtree rooted at node 
// if subtree is empty, height is -1 
// if subtree has one node, height is 0 
int AVLTree::height(AVLNode* node){ 

    if(node != NULL){ 
     return node->height; 
    } 
    else{ 
     return -1; 
    } 
} 

// return the balance factor of the node 
int AVLTree::balanceFactor(AVLNode* node){ 
    return height(node->left) - height(node->right); 
} 

// update the height of the node 
// this should be done whenever the tree is modified 
void AVLTree::updateHeight(AVLNode* node){ 
    int hl = height(node->left); 
    int hr = height(node->right); 
    node->height = (hl > hr ? hl : hr) + 1; 
} 


// rotate right the subtree rooted at node 
// return the new root of the subtree 
AVLNode* AVLTree::rotateRight(AVLNode* node){ 
    AVLNode* lp = node->left;  // left child of node 
    if (node->parent != NULL) { // node is not root 
     if (node->parent->left == node) { // node is a left child 
      node->parent->left = lp; 
     }else{ 
      node->parent->right = lp;  // node is a right child 
     } 
    } 

    if (lp->right != NULL) {   // pointer update 
     lp->right->parent = node; 
    } 

    lp->parent = node->parent; 
    node->left = lp->right; 
    lp->right = node; 
    node->parent = lp; 
    updateHeight(node);     // after rotation, update height 
    updateHeight(lp);      // after rotation, update height 
    if (node == root) { 
     root = lp; 
    } 
    return lp; // lp is the new root of the subtree 
} 


// rotate left the subtree rooted at node 
// return the new root of the subtree 
AVLNode* AVLTree::rotateLeft(AVLNode* node){ 
    AVLNode* rp = node->right; 
    if (node->parent!=NULL) { 
     if (node->parent->left == node) { 
      node->parent->left = rp; 
     }else{ 
      node->parent->right = rp; 
     } 
    } 

    if (rp->left != NULL) { 
     rp->left->parent = node; 
    } 

    rp->parent = node->parent; 

    node->right = rp->left; 
    rp->left = node; 
    node->parent = rp; 
    node->parent = rp; 
    updateHeight(node); 
    updateHeight(rp); 
    if (node == root) { 
     root = rp; 
    } 
    return rp; 
} 


// rebalance a tree rooted at node 
// return the new root of the subtree 
AVLNode* AVLTree::balance(AVLNode* node){ 
    updateHeight(node); 
    if (balanceFactor(node) == 2) { 
     if (balanceFactor(node->left) < 0) { 
      node->left = rotateLeft(node->left); // for left right case 
     } 

     AVLNode* temp = rotateRight(node); 
     updateHeight(temp); 
     return temp; 
    } 

    if (balanceFactor(node) == -2) { 
     if (balanceFactor(node->right) > 0) { 
      node->right = rotateRight(node->right); // for right left case 
     } 
     AVLNode* temp2 = rotateLeft(node); 
     updateHeight(temp2); 
     return temp2; 
    } 
    return node; 
} 

// insert a new node with (ss, na) to the AVL tree 
// if there exists ss value, return false 
// otherwise, insert it, balance the tree, return true 
bool AVLTree::insert(string ss, string na){ 
    AVLNode *newNode=new AVLNode(ss,na); 

    AVLNode *Iterator; 
    if(root==NULL){ 
     cout<<"Root Node Inserted"<<endl; 
     root=newNode; 

    } else { 

     Iterator = root; 
     int rootTempValue = atoi((Iterator->ssn).c_str()); 
     int addTempValue = atoi((newNode->ssn).c_str()); 



     if(rootTempValue <= addTempValue ){ 
       // Right Portion of the tree 
       while(Iterator->right != NULL){ 

         cout << "In the Right portion" <<endl; 


         int rootTempValue2 = atoi((Iterator->right->ssn).c_str()); 
         int addTempValue2 = atoi((newNode->ssn).c_str()) ; 

         if(rootTempValue2 <= addTempValue2)    
          Iterator = Iterator->right; 
         else 
          Iterator = Iterator->left;  


        //Iterator = Iterator->right; 


       } 

       Iterator->right = newNode ; 
       newNode->parent = Iterator ; 


     } else { 


       // Left Portion of the tree 
       while(Iterator->left != NULL){ 
        //Iterator = Iterator->left; 



        int rootTempValue2 = atoi((Iterator->left->ssn).c_str()); 
        int addTempValue2 = atoi((newNode->ssn).c_str()) ; 

        if(rootTempValue2 <= addTempValue2)    
          Iterator = Iterator->right; 
        else 
         Iterator = Iterator->left;  



       } 
       newNode->parent = Iterator; 
       newNode->right = NULL ; 
       newNode->left = NULL; 
       Iterator->left = newNode ; 

       cout << "In the left portion : " <<Iterator->left->ssn<<endl; 

     } 

    } 

    balance(newNode); 
    updateHeight(newNode); 


    return true; 
} 


AVLNode* AVLTree::maxOfSubtree(AVLNode* node){ 
    if (node == NULL) { 
     return NULL; 
    } 
    while (node->right != NULL) { 
     node = node->right; 
    } 
    return node; 
} 

// delete the node containing value ss 
// if there is not such node, return false 
// otherwise, delete the node, balance the tree, return true 
bool AVLTree::deleteNode(string ss){ 

    // please implement here 
    return true; 

} 

// internal function 
// do not call it directly 
void AVLTree::print(AVLNode* x, int indent){ 
    if(x == NULL) 
     return; 
    if (x->right != NULL) { 
     print(x->right, indent+4); 
    } 

    if (indent != 0) { 
     cout << std::setw(indent) << ' '; 
    } 

    if(x->right != NULL){ 
     cout << " /\n" << std::setw(indent) << ' '; 
    } 

    cout << x->ssn << endl; 

    if (x->left != NULL) { 
     cout << std::setw(indent) << ' ' <<" \\\n"; 
     print(x->left, indent+4); 
    } 

} 

// print out the structure of the binary tree 
// use it for debugging, I love this function 
void AVLTree::print(){ 
    int count = 0; 
    print(root, count); 
} 


// it does not level order traversal 
// it prints out the number of node 
// use it mainly for debugging 
void AVLTree::levelOrder(){ 

// please implement it 
} 

MAIN.CPP는

#include <iostream> 
#include "AVLTree.h" 


int main(int argc, char** argv) { 
    AVLTree temp; 
    temp.insert("05", "a"); 
    temp.insert("04", "b"); 
    temp.insert("09", "c"); 
    //temp.insert("03", "d"); 
    //temp.insert("06", "d"); 
// temp.insert("07", "d"); 
    //temp.insert("02", "d"); 

    temp.print(); 
    cout<<endl; 
    cout<<"The Height Of The Tree is :" << temp.height(temp.getRoot())<<endl; 

    cin.get(); 
    return 0; 
} 

Answer 1

귀하의 AVLTree 불변 복잡한 클래스를 가지고 있으며, 그것을 표현하는 것은 일반적으로 효율적으로 디버깅을위한 좋은 생각이다. 당신이

bool 
AVLTree::invariant() const { 
    if (root == NULL) 
    return true; 

    std::stack<AVLNode*> stack; 
    stack.push_back(root); 
    while (!stack.empty()) { 
    AVLNode* currentNode = stack.back(); 
    int leftHeight = -1, rightHeight = -1; 
    if (currentNode->left) { 
     leftHeight = currentNode->left->height; 
     if (currentNode->left->parent != currentNode) 
     return false; 
     if (currentNode->left.height+1 != currentNode->height) 
     return false; 
    } 
    if (currentNode->right) { 
     rightHeight = currentNode->right->height; 
     if (currentNode->left->parent != currentNode) 
     return false; 
     if (currentNode->left.height+1 != currentNode->height) 
     return false; 
    } 
    if (leftHeigth > rightHeigth+1 || rightHeight > leftHeight+1) 
     return false; 
    if (currentNode->left) 
     stack.push_back(currentNode->left); 
    else { 
     do { 
     stack.pop_back(); 
     AVLNode* parentNode = !stack.empty() ? stack.back() : NULL; 
     if (currentNode && parentNode->right != currentNode && parentNode->right) { 
      stack.push_back(parentNode->right); 
      break; 
     }; 
     currentNode = parentNode; 
     } while (currentNode); 
    }; 
    }; 
    return true; 
} 

같은 방법을 쓰는 경우

당신은 당신은, 당신이 실패 삽입을 확인했다 자마자 그것으로 다음 코드

assert(temp.invariant()); 
temp.insert("05", "a"); 
assert(temp.invariant()); 
temp.insert("04", "b"); 
assert(temp.invariant()); 
temp.insert("09", "c"); 
assert(temp.invariant()); 

를 추가하여 main 기능을 디버깅 할 수 있습니다 실행되는 invariant 메서드에서 return false;을 중단해야합니다. 이 시점에서 버그의 출처를 이해할 수 있어야합니다.

Answer 2

std::stack을 사용하지 않는 이유는 무엇입니까? 재귀는 기본적으로 호출 스택을 그대로 반복합니다.

if (!root) 
    root = new AVLNode(ss, na); 
else 
{ 
    AVLNode *current = root; 
    AVLNode *previous = NULL; 
    std::stack<AVLNode*> rstack; 

    while (current != NULL) 
    { 
     previous = current; 
     //Use String Compare instead of cast 
     if (ss.compare(current->ssn) < 0) //If ss less than current 
      ... 

     rstack.push(previous); 
    } 
    ... 
    ... 

    while (!rstack.empty()) 
    { 
     rstack.top() = balance(rstack.top()); 
     rstack.pop(); 
    } 
}