我正在寻找在AVL-tree中计算节点平衡的最佳方法。我以为我有它工作，但经过一些繁重的插入/更新，我可以看到它的工作正常（根本没有）。
这是一个由两部分组成的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是从该节点到叶子的最长向下路径的长度“。而我理解它，但我没有实现它。并且为了进一步混淆我这个引用可以在维基百科的树高上找到“传统上，值-1对应于没有节点的子树，而零对应于具有一个节点的子树。”
第二部分是获取AVL树中子树的平衡因子，理解这个概念没有问题，“获取L和R子树的高度，并从R中减去L”。这被定义为：BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
在维基百科上阅读在描述插入到AVL树中的前几行中说：“如果平衡因子变为-1,0或1，那么树仍然是AVL形式，并且不需要旋转。”
然后继续说，“如果平衡因子变为2或-2，那么植根于此节点的树是不平衡的，并且需要树旋转。最多需要单次或双次旋转来平衡树。” - 我没有抓麻烦。
但是（是的，总有一个但是）。
这是令人困惑的地方，文本说明“如果R的平衡因子为1，则意味着插入发生在该节点的（外部）右侧，需要左旋转”。但是从理解的角度来看，正如我所引用的那样，如果平衡因子在[-1, 1]之内，那么就没有必要进行平衡了吗？
我觉得我已经非常接近于掌握这个概念，我已经让树旋转下来，实现了一个普通的二叉搜索树，并且在抓住AVL树的边缘，但似乎只是缺少那个必要的顿悟。
编辑：代码示例比学术公式更受欢迎，因为我总是更容易在代码中掌握一些东西，但是非常感谢任何帮助。
编辑：我希望我能将所有答案都标记为“已接受”，但对我而言，NIck的答案是第一个让我走“aha”的答案。
正如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）））。 （上））
当它说“如果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
我希望这是有道理的
您无需动态计算树深度。
您可以在执行操作时对其进行维护。
而且，实际上你实际上并不需要跟踪深度;您可以简单地跟踪左右树深度之间的差异。
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中的魔力 - 如果我们将正确的孩子转到正确的FIRST，那么我们所拥有的就是......
P
\
O
\
LC
\
RC
现在，如果我们左转，我们得到的是......
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也会更新。插入节点（所有测试的）时调用这些函数，例如，
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