[C++知识库]C++实现AVL树（只有插入操作）

// 树节点
struct AVLNode {
  int depth;
  AVLNode* left;
  AVLNode* right;
  int val;

  AVLNode(int val=0) {
    depth = 0;
    left = right = nullptr;
    this->val = val;
  }
};

class AVLTree {
  typedef AVLNode Node;
  typedef AVLNode *PNode;

  const int DEPTH_DIFFERENCE_LIMIT = 1;

  public:
    /**
     * 递归插入
    */
    bool insert(const int val, PNode &n) {
      if (nullptr == n) {
        n = new Node(val);
        balance(n);
        return true;
      }
      else if (val < n->val) {
        bool isSucc = insert(val, n->left);
        balance(n);
        return isSucc;
      }
      else if (val > n->val) {
        bool isSucc = insert(val, n->right);
        balance(n);
        return isSucc;
      }
      else
        // 说明树中已经有这个节点了
        return false;
    }

    /**
     * 获取深度
     */
    int get_depth(PNode node) {
      if (node == nullptr) {
        return 0;
      }

      return node->depth;
    }

    /***
     * 更新深度
     */
    void update_depth(PNode node) {
      if (node == nullptr) {
        return;
      }

      update_depth(node->left);
      update_depth(node->right);

      int l_depth = get_depth(node->left);
      int r_depth = get_depth(node->right);
      node->depth = max(l_depth, r_depth) + 1;
    }

    /**
    * 获取平衡因子
    */
    int get_balance(PNode n) {
      if (n == nullptr) {
        return 0;
      }

      return get_depth(n->left) - get_depth(n->right);
    }

    /**
     * 左旋
     */ 
    void l_rotate(PNode &n) {
      auto r = n->right;
      n->right = r->left; // 右子树的左子树右挂
      r->left = n;

      // 更新高度
      // update_depth(n);
      // update_depth(r);

      n = r;
    }

    /**
     * 右旋
     */ 
    void r_rotate(PNode &n) {
      auto l = n->left;
      n->left = l->right; // 左子树的右子树左挂
      l->right = n;

      n = l;
    }

    /**
     * 右左双旋
     */ 
    void rl_rotate(PNode &n) {
      r_rotate(n->right);
      l_rotate(n);
    }

    /**
     * 左右双旋
     */ 
    void lr_rotate(PNode &n) {
      l_rotate(n->left);
      r_rotate(n->right);
    }

    /**
     * 通过旋转节点来平衡高度
     */ 
    void balance(PNode &n) {
      if (nullptr == n) {
        return;
      }

      if ((get_depth(n->left) - get_depth(n->right)) > DEPTH_DIFFERENCE_LIMIT) { // 左子树高度失衡
        if (get_depth(n->left->left) >= get_depth(n->left->right)) {
          /**
           *      8           6
           *     /           / \
           *    6    =>     4   8
           *   /
           *  4          (右旋)
           * 
           */
          r_rotate(n);
        } else {
          /**
           *      8            8           7
           *     /            /           / \
           *    6     =>     7    =>     6   8
           *     \  (左旋)  /
           *      7        6      (右旋)
           * 
           */
          lr_rotate(n);
        }
      } else if ((get_depth(n->right) - get_depth(n->left)) > DEPTH_DIFFERENCE_LIMIT) { // 右子树失衡
        if (get_depth(n->right->right) >= get_depth(n->right->left)) {
          /**
           *    4                  6
           *     \                / \
           *      6     =>       4   8
           *       \
           *        8    (左旋)
           * 
           */
          l_rotate(n);
        } else {
          /**
           *    4             4              6
           *     \             \            / \
           *      8     =>      6    =>    4   8
           *     /    (右旋)     \     
           *    6                8     (左旋)
           * 
           */
          rl_rotate(n);
        }
      }

      // 更新高度
      update_depth(n);
    }

    /**
     * 获取根节点
     */
    PNode getRoot() {
      return root;
    }
  private:
    PNode root = nullptr;
};

节点高度更新的代码调用还有点问题