计算二叉搜索树高度的最佳方法？ （平衡 AVL 树）

Question

我正在寻找计算 AVL-tree 中节点平衡的最佳方法。 我以为我已经可以正常工作了，但是经过一些繁重的插入/更新后，我发现它（根本）无法正常工作。

这是一个由两部分组成的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是到叶子的最长向下路径的长度从那个节点开始。” 我理解它，但我未能实现它。 更让我困惑的是，这句话可以在维基百科的树高上找到“传统上，值 -1 对应于没有节点的子树，而 0 对应于具有一个节点的子树。”

第二部分是获取 AVL 树中子树的平衡因子，我对这个概念的理解没有问题，“获取 L 和 R 的高度 子树并从 L 中减去 R"。 它的定义如下： BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读，在描述插入 AVL 树的前几行中提到了这一点： “如果平衡因子变为 -1、0 或 1，则树仍处于 AVL 形式，并且不需要旋转。”

然后继续说道，“如果平衡因子变为 2 或 -2，则以此节点为根的树不平衡，最多需要一次或两次旋转来平衡树。” - 我很容易理解。 。

但是（是的，总有一个但是）。

这就是令人困惑的地方，文本指出“如果 R 的平衡因子为 1，则意味着插入发生在该节点的（外部）右侧，并且需要向左旋转”。 但根据我的理解，文本说（正如我引用的），如果平衡因子在 [-1, 1] 范围内，那么就不需要平衡？

我觉得我已经非常接近掌握这个概念了，我已经降低了树的旋转，实现了一个普通的二叉搜索树，并且即将掌握 AVL 树，但似乎缺少那个基本的顿悟。

编辑：代码示例比学术公式更受青睐，因为我总是更容易掌握代码中的某些内容，但非常感谢任何帮助。

编辑：我希望我可以将所有答案标记为“已接受”，但对我来说，NIck 的答案是第一个让我“啊哈”的答案。

Answer 1

第 1 部分 - 高度

正如 starblue 所说，高度只是递归的。 在伪代码中：

height(node) = max(height(node.L), height(node.R)) + 1

现在可以通过两种方式定义高度。 它可以是从根到该节点的路径中的节点数，也可以是链接数。 根据您引用的页面，最常见的定义是链接数量。 在这种情况下，完整的伪代码将是：

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

如果您想要节点的数量，代码将是：

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

无论哪种方式，我认为重新平衡算法应该工作相同。

但是，如果您在树中存储和更新高度信息，而不是每次都计算高度信息，那么您的树将会更加高效 (O(ln(n))）。 (O(n))

第 2 部分 - 平衡

当它说“如果 R 的平衡因子为 1”时，它正在谈论右分支的平衡因子，当顶部的平衡因子是2。它告诉你如何选择是单旋转还是双旋转。 在（类似 python 的）伪代码中：

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

我希望这是有道理的

Answer 2

您不需要即时计算树的深度。

您可以在执行操作时维护它们。

此外，您实际上并不需要跟踪深度；您只需跟踪深度即可。 您可以简单地跟踪左右树深度之间的差异。

我发现从编程 POV 中跟踪平衡因子（左子树和右子树之间的差异）更容易，除了在旋转后排序平衡因子是 PITA 之外...

Answer 3

• 高度很容易通过递归实现，取子树高度的最大值加一。

• 我认为，“R 的平衡因子”是指树的右子树不平衡。

Answer 4

这是查找高度的另一种方法。 向节点添加一个名为 height 的附加属性：

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

现在，我们将对树进行简单的广度优先遍历，并不断更新每个节点的高度值：

int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;

q.Enqueue(root);
while(q.Count > 0)
{
   lastnode = q.Dequeue();
   if (lastnode.left != null){
      lastnode.left.height = lastnode.height + 1; 
      q.Enqueue(lastnode.left);
   }

   if (lastnode.right != null){
      lastnode.right.height = lastnode.height + 1;
      q.Enqueue(lastnode.right);
   }
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}

干杯，

Answer 5

这里令人困惑，文本指出“如果 R 的平衡因子为 1，则
意味着插入发生在该节点的（外部）右侧和左侧
需要旋转”。但是从我的理解来看，文本说（正如我引用的），如果
平衡因子在[-1, 1]范围内就不需要平衡了？

好吧，顿悟时间到了。

考虑一下轮换的作用。 让我们考虑一下左旋转。

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P              10
  \               \
   O               15
    \                \
     RC               20
    /                /
   LC               18

          ↓
 P              10
   \               \
     RC              20
   /               /
  O              15
   \               \
   LC              18

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

现在，您必须注意的一件大事 - 这种左旋转并没有改变树的深度。 我们已经不再因为这样做而变得平衡了。

但是 - 这就是 AVL 中的魔力 - 如果我们首先将右孩子旋转到右侧，我们会得到这样的...

 P                  10
  \                   \
   O                  15
    \                   \
     LC                 18
      \                   \
       RC                 20

现在如果我们向左旋转 O，我们得到的就是这个...

 P                     10
   \                     \
     LC                  18
    /  \                /  \
   O   RC              15  20

魔术！ 我们已经成功地去掉了树的一个级别 - 我们已经使树达到了平衡。

平衡树意味着摆脱多余的深度，并更完整地包装上层 - 这正是我们刚刚所做的。

关于单/双旋转的全部内容很简单，你必须让你的子树看起来像这样；

 P
  \
   O
    \
     LC
      \
       RC

在你旋转之前 - 你可能必须进行右旋转才能进入该状态。 但如果您已经处于该状态，则只需向左旋转即可。

Answer 6

那么，您可以使用以下递归函数计算树的高度：

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

使用 max() 和 struct tree 的适当定义。 您应该花时间弄清楚为什么这与您引用的基于路径长度的定义相对应。 该函数使用零作为空树的高度。

然而，对于像 AVL 树这样的东西，我认为你实际上不会在每次需要时计算高度。 相反，每个树节点都会增加一个额外的字段，该字段会记住以该节点为根的子树的高度。 当树通过插入和删除进行修改时，该字段必须保持最新。

我怀疑，如果您每次计算高度而不是像上面建议的那样将其缓存在树中，那么 AVL 树形状将是正确的，但它不会具有预期的对数性能。

Answer 7

这里令人困惑，文本指出“如果 R 的平衡因子为 1，则意味着插入发生在该节点的（外部）右侧，并且需要向左旋转”。 但根据我的理解，文本说（正如我引用的），如果平衡因子在 [-1, 1] 范围内，那么就不需要平衡？

R 是当前节点N 的右侧子节点。

如果 balance(N) = +2，那么您需要某种轮换。 但是使用哪种旋转呢？ 好吧，这取决于 balance(R)：如果 balance(R) = +1 那么你需要在 N 上左旋转； 但如果 balance(R) = -1 那么你将需要某种形式的双旋转。

Answer 8

给 BinaryTree::Node 一个 subtreeHeight 数据成员，在其构造函数中初始化为 0，并每次自动更新：

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
    const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
    left = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (right)
            subtreeHeight = std::max (right->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerLeftSubtreeSize;
        subtreeHeight = right ? right->subtreeHeight + 1 : 0;
    }
}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
    const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
    right = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (left)
            subtreeHeight = std::max (left->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerRightSubtreeSize;
        subtreeHeight = left ? left->subtreeHeight + 1 : 0;
    }
}

注意数据成员 subtreeSize 和 depthFromRoot 也已更新。
这些函数在插入节点时调用（均已测试），例如，

template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;
        return newNode;
    }
    if (getComparator()(t, node->value)) {
        std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
        node->setLeft(newLeft);
    }
    else {
        std::shared_ptr<Node> newRight = insert(tree, t, node->right);
        node->setRight(newRight);
    }
    return node;
}

如果删除节点，请通过替换 subtreeSize++;removeLeft 和 removeRight 来使用不同版本。 code> 和 subtreeSize--;。 rotateLeft 和 rotateRight 的算法也可以毫无问题地进行调整。 以下内容经过测试并通过：

template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
    std::shared_ptr<Node> pivot = node->right;
    pivot->subtreeSize = node->subtreeSize;
    pivot->depthFromRoot--;
    node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
    const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
    node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
    if (pivot->right) {
        node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
        pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
    }
    else
        pivot->subtreeHeight = node->subtreeHeight + 1;
    node->depthFromRoot++;
    decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
    increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
    pivot->parent = node->parent;
    if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
        if (pivot->parent->left == node)
            pivot->parent->left = pivot;
        else
            pivot->parent->right = pivot;
    }
    node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
    pivot->setLeftSimple(node);
    if (node == root) {
        root = pivot;
        root->parent = nullptr; 
    }
}

其中

inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
    if (!node)
        return;
    node->depthFromRoot += adjustment;
    adjustDepthFromRoot (node->left, adjustment);
    adjustDepthFromRoot (node->right, adjustment);
}

以下是完整代码： http://ideone.com/d6arrv

Answer 9

这种类似 BFS 的解决方案非常简单。 简单地一层一层地跳跃。

def getHeight(self,root, method='links'):
    c_node = root
    cur_lvl_nodes = [root]
    nxt_lvl_nodes = []
    height = {'links': -1, 'nodes': 0}[method]

    while(cur_lvl_nodes or nxt_lvl_nodes):
        for c_node in cur_lvl_nodes:
            for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
                nxt_lvl_nodes.append(n_node)

        cur_lvl_nodes = nxt_lvl_nodes
        nxt_lvl_nodes = []
        height += 1

    return height