2017-11-19 18 views
0

삽입을 위해 AVL 트리에서 작업 해 왔습니다. 인서트는 제대로 작동하지만 시도한 모든 회전은 제대로 작동하지 않습니다. 내 밸런싱을위한 다른 위치를 시도해 왔고 각 삽입 후에 회전하여 시도 할 수도 있지만 작동 여부를 확인하기 위해 로테이션을 시도하지는 않습니다. 왜 내 로테이션이 효과가 없는지에 대한 도움은 크게 감사 할 것입니다.AVL 트리 회전 관련 문제

헤더 :

#ifndef LINKEDBINARYTREE_H 
#define LINKEDBINARYTREE_H 
#include <iostream> 
#include <string> 
using namespace std; 

class LinkedBinaryTree { 
private: 
    struct Node { 
     string word; 
     Node* left; 
     Node* right; 
     Node* parent; 
     int wordCount; 
     int height; 
     Node() : word(), left(NULL), right(NULL), parent(NULL), wordCount(1), height(1) {} 
     Node(string s, Node* l, Node* r, Node* p) { 
      word = s; 
      left = NULL; 
      right = NULL; 
      parent = p; 
      wordCount = 1; 
      height = 1; 
     } 
    }; 
    Node* _root; 

public: 
    LinkedBinaryTree(); 
    ~LinkedBinaryTree(); 
    void insertNode(Node* node, string word); 
    void insert(string word); 
    void display(Node* ptr, int level); 
    Node* root(); 
    void inOrder(Node* node); 
    void rightRotate(Node* node); 
    void leftRotate(Node* node); 
    void rightLeftRotate(Node* node); 
    void leftRightRotate(Node* node); 
    int avlNum(Node* node); 
    int height(Node* node); 
    int bfactor(Node* node); 
    void fixHeight(Node* node); 
    void balance(Node* node); 

    int n; 
}; 
#endif 

통화 당 :

#include "LinkedBinaryTree.h" 
#include <algorithm> 

void LinkedBinaryTree::inOrder(Node * node) 
{ 
    if (node == NULL) 
     return; 
    inOrder(node->left); 
    cout << node->word << " " << avlNum(node) << " : " ; 
    inOrder(node->right); 
} 

void LinkedBinaryTree::rightRotate(Node* node) 
{ 
    Node* temp; 
    temp = node->left; 
    node->left = temp->right; 
    temp->right = node; 
    temp->parent = node->parent; 
    node = temp; 
    if (temp->parent = NULL) { 
     _root = temp; 
    } 
    fixHeight(node); 
    fixHeight(node->right); 
    fixHeight(node->left); 
} 

void LinkedBinaryTree::leftRotate(Node * node) 
{ 
    Node* temp; 
    temp = node->right; 
    node->right = temp->left; 
    temp->left = node; 
    temp->parent = node->parent; 
    node = temp; 
    if (temp->parent = NULL) { 
     _root = temp; 
    } 
    fixHeight(node); 
    fixHeight(node->right); 
    fixHeight(node->left); 
} 

void LinkedBinaryTree::rightLeftRotate(Node * node) 
{ 
    rightRotate(node->left); 
    leftRotate(node); 
} 

void LinkedBinaryTree::leftRightRotate(Node * node) 
{ 
    leftRotate(node->right); 
    rightRotate(node); 
} 

int LinkedBinaryTree::height(Node * node) 
{ 
    int h = 0; 

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

int LinkedBinaryTree::bfactor(Node * node) 
{ 
    return height(node->right) - height(node->left); 
} 

void LinkedBinaryTree::fixHeight(Node * node) 
{ 
    int hl = height(node->left); 
    int hr = height(node->right); 
    node->height = (hl > hr ? hl : hr) + 1; 
} 

int LinkedBinaryTree::avlNum(Node * node) 
{ 
    int leftH = height(node->left); 
    int rightH = height(node->right); 
    int avlNum = rightH - leftH; 
    return avlNum; 
} 

LinkedBinaryTree::LinkedBinaryTree() 
{ 
    _root = NULL; 
} 

LinkedBinaryTree::~LinkedBinaryTree() 
{ 
} 

void LinkedBinaryTree::insertNode(Node* node, string word) 
{ 
    if (word < node->word) { 
     if (node->left != NULL) 
      insertNode(node->left, word); 
     else { 
      node->left = new Node(word, NULL, NULL, node); 
     } 
    } 
    else if (word > node->word) 
    { 
     if (node->right != NULL) 
      insertNode(node->right, word); 
     else { 
      node->right = new Node(word, NULL, NULL, node); 
     } 
    } 
    else if (word == node->word) { 
     node->wordCount++; 
    } 
    balance(node); 
} 

void LinkedBinaryTree::insert(string word) { 

    if (_root == NULL) { 
     _root = new Node(word, NULL, NULL, NULL); 
     n++; 
    } 
    else { 
     insertNode(_root, word); 
     n++; 
    } 
} 
void LinkedBinaryTree::display(Node* ptr, int level) 
{ 
    int i; 
    if (ptr != NULL) 
    { 
     display(ptr->right, level + 1); 
     printf("\n"); 
     if (ptr == _root) 
      cout << "Root -> "; 
     for (i = 0; i < level && ptr != _root; i++) 
      cout << "  "; 
     cout << ptr->word; 
     display(ptr->left, level + 1); 
    } 
} 

LinkedBinaryTree::Node * LinkedBinaryTree::root() 
{ 
    return _root; 
} 

void LinkedBinaryTree::balance(Node* node) 
{ 
    fixHeight(node); 
    if (bfactor(node) == 2) { 
     if (bfactor(node->right) < 0) 
      rightRotate(node->right); 
     else 
      leftRotate(node); 
    } 
    if (bfactor(node) == 2) { 
     if (bfactor(node->left) > 0) 
      leftRotate(node->left); 
     else 
      rightRotate(node); 
    } 
} 

주 :

#include "LinkedBinaryTree.h" 
#include <string> 

int main() { 

    LinkedBinaryTree t; 

    t.insert("Yes"); 
    t.insert("No"); 
    t.insert("Maybe"); 
    t.insert("Hopefully"); 
    t.insert("Absolutely"); 

    t.display(t.root(), 1); 

    cout << endl; 
    cout << endl; 

    t.inOrder(t.root()); 

    system("PAUSE"); 
    return EXIT_SUCCESS; 
} 

답변

0

가 코드에서 많은 오류가 있지만 회전을 방해하는 일이있다 초 bfactor 체크인시 balance이 잘못되었습니다. -2과 비교해야합니다. 당신이

if (bfactor(node) == -2) 

또 다른 문제는 Rotate 기능에 if 문장의 조건에서 할당이 (컴파일러 경고 수준이를 알려 것이다 증가)입니다.

+0

아, 고맙습니다. 내 코드에서 이러한 변경 사항을 만들었지 만 여전히 문제를 수정하지는 않습니다. "Yes"는 항상 루트가됩니다. 회전이 시작되면 아무 것도 회전하지 않아도 트리 루트를 변경해야하기 때문에 이해할 수없는 일은 중요하지 않습니다. – NeerP84

+0

@ NeerP84'if (temp-> parent == NULL)'을'if (temp-> parent == NULL)'로 수정 했습니까? – 1201ProgramAlarm

+0

고쳐 주셔서 감사합니다. 나는 네 번째 삽입 후 노드를 잃어 가고있다. – NeerP84