如何在Java中以O(1)时间统计WAVL树子树的内部节点数

嘿，我来给你支个招，怎么在WAVLNode里搞定O(1)时间统计子树内部节点数的需求——核心思路就是给每个节点维护一个预计算的字段，在树结构变化时同步更新它，查询时直接拿值就行。具体操作如下：

1. 给WAVLNode新增统计字段 #

首先在你的WAVLNode类里添加一个internalSize成员变量，用来记录以当前节点为根的子树中内部节点的总数。新创建的内部节点（非外部空节点）初始化时，internalSize要设为1，因为它自身就是一个内部节点。

修改后的类代码示例：

package coding_ex1;
public class WAVLNode {
    WAVLNode left;
    WAVLNode right;
    WAVLNode parent;
    int rank;
    int key;
    String value;
    int internalSize; // 新增：记录子树内部节点数量

    public WAVLNode() {
        this.left = null;
        this.right = null;
        this.parent = null;
        this.rank = 0;
        this.key = 0;
        this.value = ""; // 补全value的初始化
        this.internalSize = 1; // 新节点自身是一个内部节点，初始计数为1
    }

    // 新增O(1)查询方法
    public int getInternalNodeCount() {
        return this.internalSize;
    }
}

2. 同步维护internalSize字段的关键操作 #

这个字段的准确性依赖于树结构变化时的及时更新，所以所有修改树结构的操作（插入、删除、旋转、WAVL秩调整）都要同步更新相关节点的internalSize：

• 插入节点时：从新插入的节点开始，向上遍历到根节点，每个经过的父节点的internalSize加1——新节点的加入会让这些父节点的子树节点数增加。
• 删除节点时：从被删除节点的父节点开始，向上遍历到根节点，每个经过的父节点的internalSize减1——子树节点减少，计数同步降低。
• 旋转操作时：旋转会改变节点父子关系，需要先更新旋转后“降级”节点的internalSize，再更新新父节点的internalSize。比如左旋操作的伪代码示例：

  public void leftRotate(WAVLNode x) {
      WAVLNode y = x.right;
      // 常规左旋指针调整逻辑
      x.right = y.left;
      if (y.left != null) {
          y.left.parent = x;
      }
      y.parent = x.parent;
      if (x.parent == null) {
          // 处理x是根节点的情况，更新根为y
      } else if (x == x.parent.left) {
          x.parent.left = y;
      } else {
          x.parent.right = y;
      }
      y.left = x;
      x.parent = y;
  
      // 先更新x的internalSize，它的子树结构已变化
      x.internalSize = 1 + 
          (x.left != null ? x.left.internalSize : 0) + 
          (x.right != null ? x.right.internalSize : 0);
      // 再更新y的internalSize，现在它的左子节点是x
      y.internalSize = 1 + 
          (y.left != null ? y.left.internalSize : 0) + 
          (y.right != null ? y.right.internalSize : 0);
  
      // 省略WAVL树的rank调整逻辑
  }
  

3. 为什么这是O(1)查询？ #

getInternalNodeCount()方法只是直接返回预先维护好的internalSize字段，不需要遍历子树统计，所以时间复杂度是严格的O(1)。而维护这个字段的额外开销是O(log n)——WAVL树的高度是O(log n)，插入、删除、旋转时遍历父节点的次数最多是树的高度，这和WAVL树本身的操作时间复杂度一致，不会增加整体成本。

内容的提问来源于stack exchange，提问作者Yarden Flori