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

您要么必须将 parent 作为节点数据结构的一部分（我个人的偏好，因为它允许轻松确定下一个和之前的 in-order 节点）并且您可以检索 parent 的 parent 或者你必须在树下寻找插入位置时跟踪每个 parent 和 grandparent。

如果你没有 parent 而使用后一种方法，那么你知道当前节点是树根，如果你有 parent 但没有 grandparent 你知道 parent 是树根。

Answer 2

现在有多种方法可以实现它；通过传递父节点，或者在分别采用 left/right 路径时通过引用传递父节点的 left/right 指针，或者通过将当前子树的根（如果需要，在平衡之后）返回给父节点当你在树上移动时。

我会 post 第三种方法，因为它减少了代码大小。

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)

AVL 树中的旋转

Rotation in an AVL Tree

c++

binary-search-tree

avl-tree