计算二进制搜索树高度的最佳方法是什么?(平衡AVL树)

第1部分-高度

正如Starblue所说,高度只是递归的。在伪代码中:

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

现在高度可以用两种方式定义。它可以是从根节点到该节点的路径中的节点数,也可以是链接数。根据 page you referenced ,最常见的定义是链接数。在这种情况下,完整的伪代码是:

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

我希望这有道理

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

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

您不需要动态计算树的深度。

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

此外,实际上您不必维护深度跟踪;您只需跟踪左树深度和右树深度之间的差异。

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

在编程POV中,只需跟踪平衡因子(左、右子树之间的差异)就比较容易了,除了在旋转后整理平衡因子是一个pita…

这是另一种寻找高度的方法。向节点添加一个名为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
}

干杯,

好吧,可以用下面的递归函数计算树的高度:

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,则 表示插入发生在该节点的(外部)右侧和左侧 需要旋转”。但从我的理解,文本说(如我引用的),如果 平衡系数在[-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

如果我们向左旋转,我们得到的是…

 P
  \
   LC
  /  \
 O    RC

魔术!我们已经设法把树的一层去掉了。- 我们使树保持平衡 .

平衡这棵树意味着去除多余的深度,更完整地包装上层——这正是我们刚刚做的。

关于单/双旋转的全部内容就是你必须让你的子树看起来像这样;

磷
\
o
\
液晶
\
钢筋混凝土

在你旋转之前-你可能要做一个正确的旋转才能进入那个状态。但如果你已经处于这种状态,你只需要做左旋转。

给予 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 也会更新。 在插入节点(所有测试)时调用这些函数,例如

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