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

StackOverflow https://stackoverflow.com/questions/575772

题

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

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

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

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

然后它继续说 “如果平衡因子变为 2 或 -2，则以此节点为根的树不平衡，需要进行树旋转。最多需要一次或两次旋转来平衡树。” ——我毫不费力地理解这一点。

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

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

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

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

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

有帮助吗？

解决方案

第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，并告诉你如何选择是否做单个旋转或双旋转。在（蟒等）的伪代码：

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

我希望这是有意义

其他提示

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

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

您不需要在运行计算树的深度。

您执行操作您可以维护他们。

此外，你实际上并没有在实际上要保持跟踪深度;你可以简单地保持左右的树深度之间的差异轨道。

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

只是跟踪的平衡因子（左和右子树之间的差）是的，我发现从编程POV容易，除了整理出平衡因子后的旋转是PITA ...

下面的发现高度的替代方式。额外的属性添加到您的节点称为高度：

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
}

干杯，

那么，你可以计算树的高度与下面的递归函数：

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树形状将是正确的，但它并没有达到预期业绩对数的。

  

在此处，它得到混乱，文本指出“如果R的平衡因子为1，则意味着发生在该节点的（外部）右侧的插入，并且需要一个左旋转”。但是，从米理解文中表示（如我的引用），如果平衡的因素是在[-1,1]然后，没有必要为平衡？

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

如果balance(N) = +2，那么你就需要某种形式的旋转。但是，要使用的旋转？嗯，这取决于balance(R)：如果balance(R) = +1那么你需要在N左旋转;但如果balance(R) = -1那么你将需要某种形式的双旋转。

  

在此处，它得到混乱，文本指出“如果R的平衡因子为1时，它   指发生在该节点和左的（外部）右侧的插入   旋转需要。”但是从m个理解文中说（如我引用），如果   平衡因子为[-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
  \
   O
    \
     RC
    /
   LC

  P
   \
    RC
   /
  O
   \
    LC

 10
   \
    15
      \
       20
      /
    18

 10
   \
    20
   /
 15
   \
    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
  \
   O
    \
     LC
      \
       RC

现在，如果我们旋转o左键，我们得到的是这样... 

 P
  \
   LC
  /  \
 O    RC

魔术！我们已经成功地摆脱了树的层次 - 我们已经把树平衡的

更完全平衡树手段去除多余的深度，和包装上水平 - 这正是我们刚刚做了

。

这是有关单/双旋转整个东西很简单，你必须有你的树看起来像这样; 

 P
  \
   O
    \
     LC
      \
       RC

在旋转前 - 你可能需要做一个正确的旋转，以进入该状态。但是，如果你在该州是已经，你只需要做向左旋转。

提供BinaryTree<T, Comparator>::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也被更新。 插入节点（所有测试的），当这些功能被称为e.g。

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;
}

如果删除节点，通过用removeLeft替换removeRight使用不同版本subtreeSize++;和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

此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
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top