排序统计（OS）树

Question

在订单统计树中也是AVL，如果左子树的尺寸为2，则右子树的最大维度是多少？ 我认为我们可以在正确的子树中添加6个节点，一个有两个孩子，两个孩子也有两个。这不会影响AVL属性，因此我的答案是正确的子树的维度是7，但我不确定。

Answer 1

确定因素是它是AVL树。它是否也是订单统计树不影响右子树中可能发生的最大节点数量。 我们的左子树有2个节点，因此这意味着根的左子树有一个孩子，是叶子。这意味着左子树的高度为1。由于AVL属性，右子树的高度要么是0、1或2。由于我们想最大化右子树中的节点数量，因此我们会去对于2的高度，将其填充为Perfect

二进制树：

    _o_
   /   \
  o    _o_
 /    /   \
o    o     o
    / \   / \
   o   o o   o

使得右子树最多可以具有7个节点。再添加一个将违反AVL属性。