平衡AVL树(C++)

Question

我正在努力想弄清楚如何为我的班级平衡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()来检查树是否需要平衡,然后根据需要进行平衡.麻烦的是,我甚至无法弄清楚如何遍历树以找到正确的不平衡节点.我知道如何递归遍历树,但我似乎无法将该算法转换为找到最低的不平衡节点.我在编写迭代算法时遇到了麻烦.任何帮助,将不胜感激.:)

Answer 1

您可以测量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;
}

在修改树时,您应该始终检查平衡(并在必要时进行旋转),没有任何一点等到树结束时为了平衡它.这只会让事情复杂化......

UPDATE

您的实现中存在错误,在下面的代码中,您没有正确检查树是否不平衡.您需要检查高度是否等于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) {...

一些资源

• AVL Tree~C++中的Imprementation
• AVL Tree~Applet

Answer 2

等等,等等.每次插入东西时,你都不会检查每个分支的"高度",是吗？

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

正确的AVL处理算法必须在每个节点处存储左/右高度差.然后,在每次操作(插入/删除)之后 - 您必须确保所有受影响的节点都不会过于不平衡.要做到这一点,你要做所谓的"旋转".在它们期间,您实际上并没有重新测量高度.您不必:每次轮换都会通过某些可预测的值更改受影响节点的平衡.