计算二叉search树中高度的最佳方法是什么？ （平衡AVL树）
我正在寻找计算AVL树中节点平衡的最佳方法。 我以为我有它的工作，但经过一些沉重的插入/更新，我可以看到，它不工作正确（在所有）。
这是一个由两部分组成的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是从该节点到叶的最长下降path的长度“。 我明白了，但是我没能实施。 为了进一步使我迷惑，可以在维基百科树形高度上find这个引用。 “传统上，值-1对应于没有节点的子树，而零对应于具有一个节点的子树。
第二部分是在AVL树中获得子树的平衡因子，对于“得到L和R子树的高度并从L减去R ”这个概念我没有任何问题。 这是这样定义的： BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
在维基百科上阅读时，在描述插入AVL树的前几行中说： “如果平衡因子变成-1,0或1，那么树仍然是AVLforms，不需要旋转。
然后继续说： “如果平衡因子变成2或-2，那么以此节点为根的树就不平衡了，需要进行树的旋转，最多只需要一次或两次旋转来平衡树。 – 我没有任何困难抓住。
但是（是的，总有一个但是）。
这里是令人困惑的地方，文字指出“如果R的平衡因子是1，则意味着插入发生在该节点的（外部）右侧，并且需要左旋转” 。 但从理解的文字（正如我所引述的）所说，如果平衡因素在[-1, 1]之内[-1, 1]那么就不需要平衡了？
我感觉自己如此接近于理解这个概念，我已经把树轮旋转了下来，实现了一个普通的二叉search树，并且在抓AVL树的边缘，但是似乎缺less了那个重要的顿悟。
编辑：代码示例优于学术公式，因为我总是有更容易的时间抓住代码的东西，但任何帮助，非常感谢。
编辑：我希望我能标记所有的答案为“接受”，但对我来说，NIck的答案是第一个让我去“哈哈”。
第1部分 – 高度
正如starblue所说，高度只是recursion的。 在伪代码中：
height(node) = max(height(node.L), height(node.R)) + 1
现在可以用两种方法来定义高度。 它可能是从根节点到该节点的path中的节点数量，也可能是链接数量。 根据你引用的页面 ，最常见的定义是链接的数量。 在这种情况下，完整的伪代码将是：
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
无论哪种方式，我认为重新平衡algorithm应该是一样的。
但是，如果您在树中存储和更新高度信息，而不是每次计算高度信息，那么您的树会更有效率（ O（ln（n）） ）。 （ O（n） ）
第2部分 – 平衡
当它说“如果R的平衡因子是1”，它是在谈论右边的平衡因素，当顶部的平衡因子是2.它告诉你如何select是做一个单一的旋转还是双重旋转。 在（python like）伪码：
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
我希望这是有道理的
-
高度很容易通过recursion实现，取最大值的子树加1。
-
R的“平衡因子”是指我认为是不平衡的树的右边的子树。
您不需要即时计算树的深度。
您可以在执行操作时对其进行维护。
此外，你实际上并不需要跟踪深度; 您可以简单地跟踪左右树深度之间的差异。
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
只要跟踪平衡因子（左右子树之间的差异），我发现编程POV更容易，除了旋转后的平衡因子是PITA …
这是find身高的另一种方法。 为您的节点添加一个名为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 }
干杯，
那么，你可以用下面的recursion函数来计算树的高度：
int height(struct tree *t) { if (t == NULL) return 0; else return max(height(t->left), height(t->right)) + 1; }
用max()和struct tree的适当定义。 您应该花时间弄清楚为什么这符合您引用的基于path长度的定义。 该函数使用零作为空树的高度。
但是，对于像AVL树这样的东西，我不认为每次需要时都要计算高度。 相反，每个树节点都增加了一个额外的字段，用于logging以该节点为根的子树的高度。 该字段必须保持最新，因为树是通过插入和删除来修改的。
我怀疑，如果你每次计算高度而不是像上面提到的那样在树中caching它，AVL树的形状将是正确的，但是它不会有预期的对数性能。
这里是令人困惑的地方，文字指出：“如果R的平衡因子是1，则意味着插入发生在该节点的（外部）右侧，并且需要左旋转”。 但从理解的文字（正如我所引述的）所说，如果平衡因素在[-1,1]之内，那么就不需要平衡了？
R是当前节点N的右侧子节点。
如果balance(N) = +2 ，那么你需要旋转一些。 但是使用哪种旋转？ 那么，这取决于balance(R) ：如果balance(R) = +1则需要在N上左转; 但如果balance(R) = -1那么你将需要某种forms的双重旋转。
这里是令人困惑的地方，文字指出：“如果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
而现在，如果我们旋转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也会更新。 插入节点（全部testing）时调用这些函数，例如
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; }
如果删除节点， removeRight通过replacesubtreeSize++;使用不同版本的removeLeft和removeRight subtreeSize++; 与子subtreeSize--; 。 rotateLeft和rotateRightalgorithm也可以适应，没有太大的问题。 以下是testing并通过：
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的解决scheme非常简单。 简单地跳一级水平。
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
