балансировка дерева 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;
}

Вы должны всегда проверять баланс (и делать повороты, если необходимо) при изменении дерева, не нужно ждатьдо конца, когда дерево беспорядок, чтобы сбалансировать его.Это только усложняет ситуацию ...

---

ОБНОВЛЕНИЕ

В вашей реализации есть ошибка, в приведенном ниже коде вы не проверяете правильно ли деревонесбалансированный.Вы должны проверить, равна ли высота 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 ++
• AVL Tree ~ Апплет

Answer 2

Подожди, подожди, подожди.Вы действительно не собираетесь проверять «высоту» каждой ветви каждый раз, когда вставляете что-то, не так ли?

Измерение высоты означает пересечение всей подветви.Значит - каждая вставка в такое дерево будет стоить O (N).Если так - зачем тебе такое дерево?Вы также можете использовать отсортированный массив: он дает O (N) вставку / удаление и O (log N) поиск.

Правильный алгоритм обработки AVL должен хранить высота влево / вправоРазница в каждом узле.Затем, после каждой операции (вставка / удаление) - вы должны убедиться, что ни один из затронутых узлов не будет слишком сильно разбалансирован.Для этого вы делаете так называемые «повороты».Во время них вы не фактически заново измеряете высоту.Вам просто не нужно: каждый поворот меняет баланс затронутых узлов на некоторое предсказуемое значение.

Answer 3

Закомментирован код правого поворота вверху и левого поворота, ниже мой рабочий правый поворот и мой рабочий левый поворот.Я думаю, что логика в повороте выше инвертирована:

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

Answer 4

Перейти к http://code.google.com/p/self-balancing-avl-tree/, все обычные операции, такие как добавление, удаление, плюс concat и split