【C++】map&set的底层结构 -- AVL树（高度平衡二叉搜索树）（上）

// AVL树节点的定义（KV模型）
template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<T>* _left;   // 该节点的左孩子
    AVLTreeNode<T>* _right;  // 该节点的右孩子
    AVLTreeNode<T>* _parent; // 该节点的双亲指针
 
    pair<K, V> _kv;          // 键值对
    int _bf;                 // 该节点的平衡因子(balance factor) = 右子树高度-左子树高度
 
    // 构造函数
    AVLTreeNode(const pari<K, V>& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};
 
// AVL树的定义（KV模型）
template<class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  // 成员函数
 
private:
  Node* _root;
}

// 插入节点
bool Insert(const pair<K, V>& kv)
{
    // 如果树为空，则直接插入节点
    if (_root == nullptr)
    {
    _root = new Node(kv);
    return true;
  }
 
  // 如果树不为空，找到适合插入节点的空位置
    Node* parent = nullptr; // 记录当前节点的父亲
    Node* cur = _root;      // 记录当前节点
 
    while (cur) // while循环结束，说明找到适合插入节点的空位置了
    {
        if(kv.first > cur->_kv.first) // 插入节点键值k大于当前节点
        {
            parent = cur;
            cur = cur->_right;
        }
        else if(kv.first < cur->_kv.first) // 插入节点键值k小于当前节点
        { 
            parent = cur;
            cur = cur->_left;
        }
        else // 插入节点键值k等于当前节点
        {
            return false;
        }
    }
    
    // 插入新节点
    cur = new Node(kv); // 申请新节点
    // 判断当前节点是父亲的左孩子还是右孩子
    if (cur->_kv.first > parent->_kv.first)
    {
        parent->_right = cur;     
 
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;
 
    // 控制平衡
  // 1、更新平衡因子
    
    // ...
 
    return true;
}

// 插入节点
bool Insert(const pair<K, V>& kv)
{
    // 控制平衡
  // 1、更新平衡因子
    
    while (parent) // 最坏情况：更新到根节点
    {
        // 更新双亲的平衡因子
        if (cur == parent->_left) // 新节点插入在父亲的左边
            parent->_bf--;
        else // 新节点插入在父亲的右边
            parent->_bf++;
 
        // 更新后检测双亲的平衡因子
        if (0 == pParent->_bf)
        {    
            break;
        }
 
        //else if (1 == parent->_bf || -1 == parent->_bf)
        else if (abs(parent->_bf) == 1) // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
        {
            cur = parent;
            parent = cur->_parent;
        }
 
        else if (abs(parent->_bf) == 2) // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以parent为根的树进行旋转处理
        {
            // 1、父节点的右边高，左边低，需要往左旋
            if (parent->_bf == 2 && cur->_bf == 1) 
        {
        RotateL(parent); // 左单旋
      }
 
            // 2、父节点的左边高，右边低，需要往右旋
      else if ((parent->_bf == -2 && cur->_bf == -1))
      {
        RotateR(parent); // 右单旋
      }
            
            // 3、父节点的左边高，且父节点左孩子的右边高
      else if (parent->_bf == -2 && cur->_bf == 1) 
      {
        RotateLR(parent); // 左右双旋
      }
 
            // 4、父节点的右边高，且父节点右孩子的左边高
            else if (parent->_bf == 2 && cur->_bf == -1)
      {
        RotateRL(parent); // 右左双旋
      }
 
      break; // 旋转完成，树已平衡，退出循环
        }
 
        // 除了上述3种情况，平衡因子不可能有其它的值，报错处理
        else
        {
            assert(false);
        }
    }
    return true;
}

// 右单旋
void _RotateR(Node* parent)
{  
    Node* subL = parent->_left; // subL : parent的左孩子
  Node* subLR = subL->_right; // subLR : parent左孩子的右孩子
 
    // 旋转完成之后，让subL的右子树subLR成为parent的左子树
    parent->_left = subLR;
    // 如果subLR存在，更新subLR的双亲指针，指向parent
    if (subLR)
  {
    subLR->_parent = parent;
  }
    
    // 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点
    Node* ppNode = parent->_parent;
    
    // 让parent成为subL的右子树
    subL->_right = parent;
    // 更新parent的双亲指针，指向subL
    parent->_parent = subL;
 
    // 如果parent是根节点，根新指向根节点的指针
    if (_root == parent)
  {
    _root = subL;            // 更新subL为新的根
    subL->_parent = nullptr; // 更新subL的双亲指针，指向空
  }
    // parent不是根节点，就是一个普通子树
    else
    {
        // 判断parent原先是左孩子还是右孩子
        if (ppNode->_left == parent)
    {
      ppNode->_left = subL; // parent原先的双亲节点接管subL，subL为这个子树的根
    }
    else
    {
      ppNode->_right = subL;
    }
        subL->_parent = ppNode; // 更新subL的双亲指针
    }
 
    // 根据调整后的结构更新部分节点的平衡因子
    parent->_bf = pSubL->_bf = 0;
}