这不是标题党，因为这个帖子本身就是关于平衡树的。同时请大家不要模仿向北方大爷。

昨天我 YY 了一种平衡策略。

大致是，每个节点额外维护一个深度，定义为 $\max(\text{左子树深度},(\text{右子树深度})+1$，叶节点深度为 $1$。对于插入，直接朴素插入，然后由下至上调整，如果左右子树的深度差的绝对值超过 $1$ 就旋转一下。

下面问几个问题：

• 这个平衡策略管用吗？我手玩了几次似乎是对的。

• 这个东西看起来有点像 AVL？已经被 lxl 或者其他人发明过了吗？

因为暂时没有时间，所以还没有写板子。有错误请指出，勿喷，谢谢。