权重平衡树是什么？它和 AVL 按高度平衡有什么区别？

简化版

权重平衡树用子树大小作为平衡依据，而不是直接用高度。它要求左右子树大小比例不能过分悬殊；一旦某边节点数太多，就通过旋转或重建调整，保证树高维持在 O(log n)。

AVL 看高度差，红黑树看颜色和黑高，权重平衡树看子树大小。典型思想是：对任一节点，左子树和右子树的节点数量要保持在某个比例范围内。

如果右子树大小远大于左子树，就说明大量节点集中在右侧，搜索路径可能变长，需要左旋或双旋；如果左子树过大，则对称处理。

它的优势是能自然支持排名、第 K 小、区间计数等基于子树大小的操作；代价是每个节点要维护 size，插入删除后需要沿路径更新，并按大小比例做平衡修复。

AVL 用高度差控制形状，红黑树用颜色间接控制高度。权重平衡树换了一个观察角度：如果一棵子树的大部分节点都堆在左边或右边，那么高度很可能逐渐变坏；只要左右节点数量比例不过分失衡，高度就能被控制在对数级。

这个思路很自然，因为搜索树真正承载的是节点集合。用节点数衡量「重量」，再让两边重量相近，就能避免一边过重形成长链。

记忆钩子：AVL 看两边有多高，权重平衡树看两边有多重。

不同权重平衡树有不同参数。一个直观表达是要求某个孩子子树大小不能超过总大小的一定比例，比如 α=0.7。若 size(left) > α * size(root) 或 size(right) > α * size(root)，就认为失衡。

size(root)=10
α=0.7
允许单边最多 7 个节点
若 left=8,right=1，则左边过重，需要修复

实际论文或实现会有更严格的旋转条件，避免来回震荡。面试通常不要求背具体参数，重点是理解「用 size 而不是 height 判断」。

AVL 只关心高度差。例如左子树 100 个节点、右子树 60 个节点，只要高度差不超过 1，AVL 就认为平衡。权重平衡树更关注数量比例，这让它天然适合和排名统计结合。

如果系统大量需要 order statistic 操作，维护 size 的树会更方便。

插入和普通 BST 一样先找到位置，然后沿回溯路径更新 size。每回到一个祖先，就检查左右子树大小是否违反比例。如果右边太重，通常做左旋；如果右子树的左侧更重，可能先右旋右孩子再左旋当前节点。左边太重时对称处理。

node.size = 1 + size(node.left) + size(node.right);
if (size(node.right) > ALPHA * node.size) {
    node = rotateLeftOrRightLeft(node);
}

伪代码只表达方向，真实条件要考虑子树内部重量分布。旋转后必须重新计算受影响节点的 size，否则后续排名会错。

有了 size，查询第 K 小可以在每个节点看左子树大小。若 k == leftSize + 1，当前节点就是答案；若 k <= leftSize，去左子树；否则去右子树并令 k -= leftSize + 1。

root=10, leftSize=5
k=6 -> root
k=3 -> left
k=9 -> right 中找第 9-6=3 小

这类操作不需要额外遍历，复杂度就是树高 O(log n)。所以权重平衡思想常和顺序统计需求一起出现。

权重平衡树的难点不在概念，而在细节。每次插入、删除、旋转后，size 都必须正确维护。删除时节点替换、旋转组合、重复值计数都会影响 size。任何一个字段更新漏掉，树可能看起来还能搜索，但排名和后续平衡判断会悄悄出错。

工程实现还要谨慎选择平衡参数。参数太严格，旋转频繁；参数太松，高度变差。它不像 AVL 的高度差 1 那样容易解释给初学者。

权重平衡树的核心是「按节点数量称重」。AVL 控制高度差，权重平衡树控制左右子树 size 比例。它的自然优势是顺序统计：第 K 小、排名、区间计数都能借助 size 完成。记住两个风险：旋转后必须更新 size，平衡参数会影响旋转频率和树高常数。