Avl 트리를 삽입하려고 시도했습니다.

Question

Avl 트리에 삽입 방법을 사용하려고했지만 내 노드의 구조와 순서가 잘못되었습니다. 내가 어디로 잘못 가고 있는지 찾는 데 어려움을 겪고 있습니다. 여기

도움의 모든 종류의

템플릿

void AvL<T>::insert(string val, T k) 
{ 
    if (head == NULL) { 
    head = new AvLNode<T>(val, k); 
} else { 
    put(head, val, k); 
} 

}

template <class T> 
void AvL<T>::put(AvLNode<T>* root,string val,T key1) { 
if (root->key > key1) { 
    if (root->left != NULL) { 
     put(root->left, val, key1); 
     Balance(root, key1); 
    } else { 
     root->left = new AvLNode<T>(val, key1); 
     root->bf = nodeHeight(root->left) - nodeHeight(root->right); 
     root->left->parent = root; 
    } 
} else { 
    if (root->right != NULL) { 
     put(root->right, val, key1); 
     Balance(root, key1); 
    } else { 
     root->right = new AvLNode<T>(val, key1); 
     root->bf = nodeHeight(root->left) - nodeHeight(root->right); 
     root->right->parent = root; 
    } 
} 
} 

template<class T> 
void AvL<T>::Balance(AvLNode<T>* root, T key1) 
{ root->bf = nodeHeight(root->left) - nodeHeight(root->right); 
if (root->bf < -1 && key1 > root->right->key) { 
    cout << "here1 "; 
    LeftRotate(root); 
} else if (root->bf > 1 && key1 < root->left->key) { 
    cout << "here2 "; 
    RightRotate(root); 
} else if (root->bf < -1 && key1 < root->right->key) { 
    RightRotate(root->right); 
    cout << "here3 "; 
    LeftRotate(root); 
} else if (root->bf > 1 && key1 > root->left->key) { 
    LeftRotate(root->left); 
    cout << "here4 "; 
    RightRotate(root); 
} 
} 

template<class T> 
void AvL<T>::RightRotate(AvLNode<T>* node) 
{ 
AvLNode<T>* node1 = node->left; 
node->left = node1->right; 
node1->right = node; 
node->bf = nodeHeight(node->left) - nodeHeight(node->right); 
node1->bf = nodeHeight(node1->left) - nodeHeight(node1->right); 
node = node1; 
} 

template<class T> 
void AvL<T>::LeftRotate(AvLNode<T>* node) 
{ 
AvLNode<T>* node1 = node->right; 
node->right = node1->left; 
node1->left = node; 
node->bf = nodeHeight(node->left) - nodeHeight(node->right); 
node1->bf = nodeHeight(node1->left) - nodeHeight(node1->right); 
node = node1; 
} 


template<class T> 
int AvL<T>::nodeHeight(AvLNode<T> *n) 
{ 
int lheight=0; 
int rheight=0; 
int h = 0; 
if (n == NULL) 
{ 
    return -1; 
} else { 
    lheight = nodeHeight(n->left); 
    rheight = nodeHeight(n->right); 
    h = 1+max(lheight,rheight); 
    return h; 
} 
} 

내 .H 파일

template <class T> 
struct AvLNode 
{ 
string value; 
T key; 
AvLNode *parent; // pointer to parent node 
AvLNode *left; // pointer to left child 
AvLNode *right; // pointer to right child 
int bf; // Balance factor of node 


AvLNode(string Val, T k) 
{ 
    this->value = Val; 
    this->key = k; 
    this->parent = NULL; 
    this->left = NULL; 
    this->right = NULL; 
    bf = 0; 
} 
}; 
template <class T> 
class AvL 
{ 
AvLNode<T> *head; 

public: 
// Constructor 
AvL(); 

// Destructor 
~AvL(); 

// Insertion Function 
void insert(string val, T k); // inserts the given key value pair into the tree 
void Balance(AvLNode<T>* node, T key1); 
void delete_node(T k); // deletes the node for the given key 
void RightRotate(AvLNode<T>* node); 
void LeftRotate(AvLNode<T>* node); 
void put(AvLNode<T>* root,string val,T key1); 
int nodeHeight(AvLNode<T> *n); // returns height of the subtree from given node 
}; 

Answer 1

Y 감사하겠습니다 내 방법 있습니다 우리의 균형 기능이 잘못되었습니다. 이미 트리에 새 노드를 삽입 한 때문에, 당신은 Balance()에서 더 이상 키에 대해 걱정할 필요가 없습니다 - 그래서 프로토 타입은 다음과 같아야합니다

template<class T> void AvL<T>::Balance(AvLNode<T>* root);

당신이하고있는 방법 이제 삽입하는 키를 기반으로 균형을 잡으려고 시도하는 것 같습니다. 필요하지 않습니다! 노드의 균형 요소를 기반으로 트리 균형을 조정할 수 있습니다 - 여기 방법이 있습니다.

template<class T> 
void AvL<T>::Balance(AvLNode<T>* root) { 
    if (root->bf > 1) { 
     if (root->left->bf == -1) LeftRotate(root->left); 
     RightRotate(root); 
    } else if (root->bf < -1) { 
     if (root->right->bf == 1) RightRotate(root->right); 
     LeftRotate(root); 
    } 
} 

당신은 그것을 here에 대한 자세한 내용을보실 수 있습니다 -하지만 당신은 거의 아래로 생각을 갖고있는 것 같다. 개념적으로 변경해야 할 것은 방금 삽입 한 키를 기반으로 균형을 잡는 것입니다. 당신은 아닙니다 - 당신은 각 하위 트리의 균형 요소들로부터 얻을 수있는 나무의 모양에 기초하여 균형을 맞추고 있습니다.