cân bằng cây AVL (C++)

Question

Tôi đang có thời gian khó khăn nhất để tìm ra cách cân bằng cây AVL cho lớp học của mình. Tôi đã có nó chèn với điều này:

Node* Tree::insert(int d) 
{ 
    cout << "base insert\t" << d << endl; 
    if (head == NULL) 
     return (head = new Node(d)); 
    else 
     return insert(head, d); 
} 

Node* Tree::insert(Node*& current, int d) 
{ 
    cout << "insert\t" << d << endl; 
    if (current == NULL) 
     current = new Node(d); 
    else if (d < current->data) { 
     insert(current->lchild, d); 
     if (height(current->lchild) - height(current->rchild)) { 
      if (d < current->lchild->getData()) 
       rotateLeftOnce(current); 
      else 
       rotateLeftTwice(current); 
     } 
    } 
    else if (d > current->getData()) { 
     insert(current->rchild, d); 
     if (height(current->rchild) - height(current->lchild)) { 
      if (d > current->rchild->getData()) 
       rotateRightOnce(current); 
      else 
       rotateRightTwice(current); 
     } 
    } 

    return current; 
} 

Kế hoạch của tôi là có các cuộc gọi để cân bằng() kiểm tra xem cây có cần cân bằng và sau đó cân bằng khi cần thiết. Vấn đề là, tôi thậm chí không thể tìm ra cách đi qua cây để tìm nút không cân bằng chính xác. Tôi biết làm thế nào để đi qua cây một cách đệ quy, nhưng tôi dường như không thể dịch thuật toán đó thành việc tìm kiếm nút không cân bằng thấp nhất. Tôi cũng gặp khó khăn khi viết một thuật toán lặp. Bất kỳ trợ giúp sẽ được đánh giá cao. :)

Answer 1

Bạn có thể đo height của một chi nhánh tại một điểm nhất định để tính toán mất cân bằng

(nhớ một sự khác biệt về chiều cao (cấp)> = 2 có nghĩa là cây của bạn không cân bằng)

int Tree::Height(TreeNode *node){ 
    int left, right; 

    if(node==NULL) 
     return 0; 
    left = Height(node->left); 
    right = Height(node->right); 
    if(left > right) 
      return left+1; 
     else 
      return right+1; 
} 

Tùy thuộc vào không đồng đều thì bạn có thể xoay khi cần thiết

void Tree::rotateLeftOnce(TreeNode*& node){ 
    TreeNode *otherNode; 

    otherNode = node->left; 
    node->left = otherNode->right; 
    otherNode->right = node; 
    node = otherNode; 
} 


void Tree::rotateLeftTwice(TreeNode*& node){ 
    rotateRightOnce(node->left); 
    rotateLeftOnce(node); 
} 


void Tree::rotateRightOnce(TreeNode*& node){ 
    TreeNode *otherNode; 

    otherNode = node->right; 
    node->right = otherNode->left; 
    otherNode->left = node; 
    node = otherNode; 
} 


void Tree::rotateRightTwice(TreeNode*& node){ 
    rotateLeftOnce(node->right); 
    rotateRightOnce(node); 
} 

Bây giờ chúng ta biết làm thế nào để xoay, cho phép nói rằng bạn muốn chèn một giá trị trong cây ... Đầu tiên chúng ta kiểm tra xem cây trống hay không

TreeNode* Tree::insert(int d){ 
    if(isEmpty()){ 
     return (root = new TreeNode(d)); //Is empty when root = null 
    } 
    else 
     return insert(root, d);   //step-into the tree and place "d" 
} 

Khi cây không phải là trống chúng tôi sử dụng đệ quy để đi qua cây và nhận được đến nơi cần

TreeNode* Tree::insert(TreeNode*& node, int d_IN){ 
    if(node == NULL) // (1) If we are at the end of the tree place the value 
     node = new TreeNode(d_IN); 
    else if(d_IN < node->d_stored){ //(2) otherwise go left if smaller 
     insert(node->left, d_IN);  
     if(Height(node->left) - Height(node->right) == 2){ 
      if(d_IN < node->left->d_stored) 
       rotateLeftOnce(node); 
      else 
       rotateLeftTwice(node); 
     } 
    } 
    else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger 
     insert(node->right, d_IN); 
     if(Height(node->right) - Height(node->left) == 2){ 
      if(d_IN > node->right->d_stored) 
       rotateRightOnce(node); 
      else 
       rotateRightTwice(node); 
     } 
    } 
    return node; 
} 

Bạn luôn nên kiểm tra cân bằng (và làm phép quay nếu cần thiết) khi sửa đổi cây, không có điểm chờ đợi cho đến khi kết thúc khi cây là một mớ hỗn độn để cân bằng nó. Đó chỉ là những điều phức tạp ...

---

CẬP NHẬT

Có một sai lầm trong việc thực hiện của bạn, trong đoạn code dưới đây, bạn không kiểm tra một cách chính xác cho dù cây là không cân bằng. Bạn cần phải kiểm tra xem chiều cao bằng 2 (do đó không cân bằng). Kết quả là các mã dưới đây ...

if (height(current->lchild) - height(current->rchild)) { ... 

if (height(current->rchild) - height(current->lchild)) {... 

nên trở thành ...

if (height(current->lchild) - height(current->rchild) == 2) { ... 

if (height(current->rchild) - height(current->lchild) == 2) {... 

---

Một số Tài

• AVL Tree ~ Imprementation in C++
• AVL Tree ~ Applet

Answer 2

Đợi đã, đợi đã. Bạn không thực sự sẽ kiểm tra "chiều cao" của mỗi nhánh mỗi lần bạn chèn cái gì đó, phải không?

Đo chiều cao có nghĩa là vượt qua tất cả các nhánh phụ. Có nghĩa là - mỗi chèn vào một cây như vậy sẽ có giá O (N). Nếu vậy - bạn cần cái cây như thế nào? Bạn cũng có thể sử dụng một mảng được sắp xếp: nó cho phép tìm kiếm/xóa O (N) và tìm kiếm O (log N).

Thuật toán xử lý AVL chính xác phải lưu trữ chênh lệch độ cao trái/phải ở mỗi nút. Sau đó, sau mỗi thao tác (chèn/xóa) - bạn phải chắc chắn rằng không có nút bị ảnh hưởng nào sẽ bị mất cân bằng quá nhiều. Để làm điều này bạn làm cái gọi là "quay". Trong thời gian đó, bạn không thực sự đo lại chiều cao. Bạn chỉ cần không phải: mỗi vòng quay thay đổi sự cân bằng của các nút bị ảnh hưởng bởi một số giá trị dự đoán được.

Answer 3

goto http://code.google.com/p/self-balancing-avl-tree/, tất cả hoạt động bình thường như thêm, xóa được thực hiện, cộng với concat và chia

Answer 4

nhận xét ra là mã đúng xoay trên và xoay trái, dưới đây là của tôi làm việc đúng xoay và xoay tôi làm việc còn lại. Tôi nghĩ rằng logic trong xoay vòng ở trên là nghịch đảo:

void rotateRight(Node *& n){ 
    //Node* temp = n->right; 
    //n->right = temp->left; 
    //temp->left = n; 
    //n = temp; 
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl; 
    Node *temp = n->left; 
    n->left = temp->right; 
    temp->right = n; 
    n = temp; 
} 

void rotateLeft(Node *& n){ 
    //Node *temp = n->left; 
    //n->left = temp->right; 
    //temp->right = n; 
    //n = temp; 
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl; 
    Node* temp = n->right; 
    n->right = temp->left; 
    temp->left = n; 
    n = temp; 
}