Балансировка дерева AVL (С++)

У меня труднее всего пытаться выяснить, как сбалансировать дерево 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;
}

Мой план состоял в том, чтобы вызвать уравновешивание(), чтобы проверить, нужно ли балансировать дерево, а затем балансировать по мере необходимости. Проблема в том, что я даже не могу понять, как пройти дерево, чтобы найти правильный неуравновешенный node. Я знаю, как рекурсивно пересекать дерево, но я не могу перевести этот алгоритм на поиск самого низкого неуравновешенного node. У меня также возникла проблема с написанием итерационного алгоритма. Любая помощь будет оценена по достоинству.:)

Ответы

Ответ 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) {...

Некоторые ресурсы

Ответ 2

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

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

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

Ответ 4

Прокомментированный код - это правый поворот кода и поворот налево, ниже мой рабочий правый поворот и моя работа слева вращается. Я думаю, что логика во вращающемся выше обратном:

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