AVL树与平衡二叉树指定节点下属节点数获取的时间复杂度咨询

问题1：获取给定根节点下属节点总数的时间复杂度 #

AVL树本质是严格自平衡的二叉搜索树，属于平衡二叉树的典型实现，二者在该问题上的特性完全一致，时间复杂度分两种实现场景：

• 无预存子树大小的标准实现：必须遍历该子树的所有节点完成计数，时间复杂度为 O(k)，其中k为该子树的实际节点数；若给定节点是整棵树的根，复杂度退化为O(n)。
• 带子树大小维护的增强实现：每个节点预先存储以自身为根的子树总节点数，直接读取该属性即可，时间复杂度为 O(1)。

问题2：能否在O(logn)时间内获取指定节点的子树节点总数 #

可以实现，且整体时间复杂度稳定为O(logn)，核心是采用上述「节点预存子树大小」的增强逻辑，该增强不会提升AVL树原有的插入、删除、查找操作的渐进时间复杂度。

核心实现逻辑 #

1. 节点结构扩展：在原有AVL树节点的基础属性（键值、左右孩子指针、父节点指针、高度/平衡因子）上，新增size属性存储当前子树的总节点数，叶子节点的size初始值为1。
2. 子树大小的一致性维护：所有会修改树结构的操作（插入、删除、旋转）完成后，必须自底向上更新涉及节点的size值：
   • 旋转是局部结构调整，仅需更新旋转涉及的2个节点的size，单次开销O(1)。
   • 插入/删除操作完成后，从变更位置的父节点开始，沿向上路径更新所有祖先节点的size；AVL树的高度始终被控制在O(logn)级别，因此该过程总开销为O(logn)，和原有操作的复杂度完全一致，不会引入额外的性能损耗。
3. 查询流程：先通过标准AVL树查找逻辑定位目标节点（耗时O(logn)），直接读取该节点的size属性（耗时O(1)），整体复杂度即为O(logn)，符合要求。

伪代码示例 #

首先定义扩展后的节点结构：

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1  # 原有AVL树属性，用于计算平衡因子
        self.size = 1    # 新增属性：当前子树的总节点数

子树大小更新的辅助函数：

# 前置条件：节点的左右孩子的size已经是最新值
def update_size(node):
    if not node:
        return
    left_cnt = node.left.size if node.left else 0
    right_cnt = node.right.size if node.right else 0
    node.size = left_cnt + right_cnt + 1

带size维护的右旋操作示例（左旋逻辑对称）：

def right_rotate(失衡节点x):
    y = x.left
    # 原有旋转的指针调整逻辑
    x.left = y.right
    if y.right:
        y.right.parent = x
    y.right = x
    y.parent = x.parent
    if x.parent:
        if x.parent.left == x:
            x.parent.left = y
        else:
            x.parent.right = y
    x.parent = y

    # 按子树到根的顺序更新size（先更新下层的x，再更新上层的y）
    update_size(x)
    update_size(y)

    # 原有AVL树的高度更新逻辑
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

目标节点查找+子树大小查询逻辑：

# 查找目标key对应的节点，耗时O(logn)
def find_node(root, target_key):
    curr = root
    while curr:
        if curr.key == target_key:
            return curr
        curr = curr.left if target_key < curr.key else curr.right
    return None

# 整体获取指定key对应节点的子树大小，总耗时O(logn)
def get_subtree_size(root, target_key):
    target_node = find_node(root, target_key)
    return target_node.size if target_node else 0

注意：如果不预先维护子树大小属性，获取任意子树节点数只能通过遍历实现，最坏情况时间复杂度为O(n)，无法达到O(logn)的性能要求。

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