20

我很难弄清楚如何为我的班级平衡 AVL 树。我已经用这个插入了它：

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;
}

我的计划是调用 balance() 检查树是否需要平衡，然后根据需要进行平衡。问题是，我什至不知道如何遍历树来找到正确的不平衡节点。我知道如何递归地遍历树，但我似乎无法将该算法转换为找到最低的不平衡节点。我在编写迭代算法时也遇到了麻烦。任何帮助，将不胜感激。:)

4

4 回答 4

28

您可以测量height给定点的分支以计算不平衡

（记住高度（级别）>= 2 的差异意味着你的树不平衡） 

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;
}

根据不平整度，您可以根据需要旋转

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);
}

现在我们知道如何旋转了，假设你想在树中插入一个值...首先我们检查树是否为空

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"
}

当树不为空时，我们使用递归遍历树并到达需要的地方

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;
}

在修改树时，您应该始终检查平衡（并在必要时进行旋转），没有必要等到树一团糟时才平衡它。那只会让事情复杂化...

更新

您的实现中有一个错误，在下面的代码中，您没有正确检查树是否不平衡。您需要检查高度是否等于 2（因此不平衡）。结果下面的代码...

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

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

应该变成...

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

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

一些资源

于 2010-11-18T21:50:09.510 回答
11

等等，等等，等等。每次插入某些东西时，您不会真的要检查每个分支的“高度”，是吗？

测量高度意味着横穿所有的支路。意味着 - 每次插入这样的树都将花费 O(N)。如果是这样 - 你需要这样一棵树吗？您也可以使用排序数组：它提供 O(N) 插入/删除和 O(log N) 搜索。

正确的 AVL 处理算法必须存储每个节点的左/右高度差。然后，在每次操作（插入/删除）之后 - 您必须确保所有受影响的节点都不会太不平衡。为此，您需要进行所谓的“旋转”。在它们期间，您实际上并没有重新测量高度。您只是不必：每次旋转都会将受影响节点的平衡改变一些可预测的值。

于 2010-11-18T22:08:54.910 回答
1

转到http://code.google.com/p/self-balancing-avl-tree/，所有常用操作如添加、删除都已实现，以及 concat 和 split

于 2012-07-12T22:48:25.057 回答
1

注释掉的是代码右旋转和左旋转，下面是我的工作右旋转和我的工作左旋转。我认为上面轮换的逻辑是相反的：

 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;
}
于 2012-07-24T02:24:10.287 回答