試圖插入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

ÿ我們的平衡功能是錯誤的。既然你已經插入你的新節點到樹上，你不需要在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 - 但你似乎有這個想法差不多了。您需要在概念上改變的唯一一件事是您基於剛剛插入的密鑰進行平衡的想法。你不是 - 你基於樹的形狀進行平衡，你可以從每個子樹的平衡因子中獲得。