时间戳

首页 > 解决方案 > AVL 树中的旋转

c++ - AVL 树中的旋转

问题描述

在不平衡的二叉搜索树中执行旋转时，如果不平衡是由左右或左右引起的，我们需要旋转父节点[单次旋转]。因此在将父节点传递给函数时可以轻松访问它。

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

标签： c++binary-search-treeavl-tree

解决方案

您要么必须将父节点作为节点数据结构的一部分（我个人的偏好，因为它可以轻松确定下一个和之前的有序节点），并且您可以检索父节点的父节点，或者您必须跟踪每个父节点和祖父节点当您沿着树向下寻找插入位置时。

如果在没有父节点的情况下使用后一种方法，那么您知道当前节点是树根，如果您有父节点但没有祖父节点，那么您知道父节点是树根。

推荐阅读