Вращение в дереве AVL

Question

При выполнении поворота в несбалансированном двоичном дереве поиска нам необходимо повернуть родительский узел [одиночный поворот], если дисбаланс возникает в правом-правом или лево-левом. так что к родительскому узлу можно легко получить доступ, когда он передается в функцию.

 void add_node(T data,Node<T>* &node){
   if(this->root==nullptr){
     Node<T>* new_node= new Node<T>(data);
     this->root=new_node;
     
   }
   else{
     if(data<node->m_data){
       if(node->m_left!=nullptr){
         add_node(data,node->m_left);
     
       }else{
          
          Node<T>* new_node= new Node<T>(data);
          node->m_left=new_node;
          rebalance(node);
       }
     }
     if(data>node->m_data){
       if(node->m_right!=nullptr){
        add_node(data,node->m_right);
        
       }else{
          Node<T>* new_node= new Node<T>(data);
          node->m_right=new_node;
          
          rebalance(node);
       }
       
     }
   }
 }

Но как мы можем получить доступ к родительскому узлу, если нам нужно выполнить поворот LR или RL?

 //BalanceFactor of a node
          int balance_factor(Node<T>* node){
          return height(node->m_left)-height(node->m_right);
      }
    Node<T>* rebalance(Node<T>* &node){
          int bal_fact=balance_factor(node);
           if(bal_fact>1){
               if(balance_factor(node->m_left)>0){
                 node=ll_rotate(node);
               }else{
                 node=lr_rotate(node);
               }
           }
           if(bal_fact<-1){
              if(balance_factor(node->m_right)>0){
                 node=rl_rotate(node);
               }else{
                 node=rr_rotate(node);
               }
           }
           return node;
         }

Answer 1

Теперь есть несколько способов реализовать это; передавая родительский узел, или передавая левый / правый указатель родителя по ссылке, когда вы выбираете левый / правый путь соответственно, или возвращая root текущего поддерева (после балансировки, если это требуется) родителю, как вы двигаемся вверх по дереву.

Я отправлю третий способ, потому что он уменьшает размер кода.

int getHeight(Node *current) { return current == nullptr ? -1 : current->height; }
int getBalanceFactor(Node *current) { return getHeight(current->left) - getHeight(current->right); }

Node* rightRotate(Node *y)
{
    Node *x = y->left;

    y->left = x->right;
    x->right = y;

    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;
}

Node* leftRotate(Node *x)
{
    Node *y = x->right;

    x->right = y->left;
    y->left = x;

    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

Node* insert(Node *current, int key)
{
    if (current == nullptr)
        return new Node(key);

    if (key <= current->key)
        current->left = insert(current->left, key);
    else
        current->right = insert(current->right, key);

    // the code hereonwards is when the control is returning from the stack, i.e., we are "moving" up the tree essentially
    current->height = max(getHeight(current->left), getHeight(current->right)) + 1;

    int bf = getBalanceFactor(current);
    // there's no imbalance, return the rooted subtree at `current` as it is
    if (-1 <= bf && bf <= 1)
        return current;

    if (bf == 2)
    {
        int bf_left = getBalanceFactor(current->left);

        // LL case
        if (bf_left == 1)
            return rightRotate(current);
        // LR case
        else
        {
            current->left = leftRotate(current->left);
            return rightRotate(current);
        }
    }
    else
    {
        int bf_right = getBalanceFactor(current->right);

        // RR case
        if (bf_right == -1)
            return leftRotate(current);
        // RL case
        else
        {
            current->right = rightRotate(current->right);
            return leftRotate(current);
        }
    }
}

И он должен называться как root = insert(root, key)

Answer 2

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

Если вы используете последний метод, если у вас нет родителя, то вы знаете, что текущий узел - это дерево root, если у вас есть родитель, но у вас нет бабушки и дедушки, вы знаете, что родителем является дерево root.