问题标签 [tree-balancing]

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

这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是从该节点到叶子的最长向下路径的长度。” 我理解它，但我未能实施它。为了让我更加困惑，这句话可以在 wikipedia on tree-heights 上找到“通常，值 -1 对应于没有节点的子树，而 0 对应于具有一个节点的子树。”

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

在维基百科上阅读描述插入 AVL 树的前几行是这样说的：“如果平衡因子变为 -1、0 或 1，那么树仍然是 AVL 形式，不需要旋转。”

然后它继续说“如果平衡因子变为 2 或 -2，则以该节点为根的树是不平衡的，需要进行树旋转。最多需要单轮或双轮旋转来平衡树。” - 我很容易掌握。

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

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

我觉得我已经非常接近掌握这个概念了，我已经降低了树的旋转，实现了一个正常的二叉搜索树，并且在掌握 AVL 树的边缘，但似乎只是缺少了那个重要的顿悟。

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

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

我正在处理一项要求我实现 AVL 树的任务。我很确定我的轮换方法是正确的，但我无法确定何时使用它们。

例如，书中的解释说我应该爬上与插入节点/元素相同的路径。但是，我不能有任何父指针。

最新代码：

我在这里要做的是爬回树上，但它只能在插入节点后检查平衡。因此，这在 else 子句中。

我还尝试将余额代码放在 R Samuel Klatchko 建议的位置，但检查了每个插件的余额。例如：如果连续插入 7、9、5、3 和 1，尝试插入 1 时会出现空指针异常。

编辑：上述的一个原因可能与我做高度的方式有关。如果我每次都用 height() 计算高度，但它会破坏 AVL 树的 O(log(n)) 时间，那么它在一次右旋转时效果很好。

关于如何做到这一点的任何想法？

我会尽量让自己清楚。基于邻接列表模型：http ://articles.sitepoint.com/article/hierarchical-data-database

我需要一种方法来平衡这棵树

类似于：

基于示例代码：

我修改了代码，使它可以输出一个像这样的平面 html 表：

$super_parent = '0000' 左节点条目进入平面列表：

但是我需要一种方法来将所有这些重新组织成一个平衡的树，而无需移动或旋转父级。虽然我可以考虑在数据库中创建一个重复表并进行第二次查询以显示或创建另一个 Binaray 树，但我认为可以将这样的扁平树重新组织为：

从左到右。0 代表 parent 或 super_parent 0000。

我想这样做的原因是我可以从原始树创建一个虚拟树，它将成为我项目中另一个算法的基础。

提前致谢。

鲍勃

我正在 Haskell 中设计一个自平衡树。作为一项练习，因为它很好地放在你的后手上。

以前在 C 和 Python 中，我更喜欢 Treaps 和 Splay Trees，因为它们的平衡规则很简单。我一直不喜欢 R/B 树，因为它们看起来比它们的价值更多。

现在，由于 Haskell 的功能特性，事情似乎发生了变化。我可以用 10 行代码编写一个 R/B 插入函数。另一方面，Treaps 需要包装来存储随机数生成器，而 Splay Trees 自顶向下做起来很痛苦。

所以我问你是否有其他类型的树木的经验？哪些更擅长利用函数式语言的模式匹配和自上而下的特性？

我已经完成了手动请求的树（bst>avl）的平衡，我想知道这真的很容易，所以我不确定我是否正确地完成了它。

初始状态是：“a”是“b”（左）和“e3”（右）的父级，“b”是“e1”（左）和“e2”（右）的父级。

应用右旋转给我们：

'b' 代替 'a'，左边有子 'e1'，右边有 'a' 子，'a' 在左边得到 'b' 的 'e2'。

所以问题：

1. 如果 e1 本身是包含其他元素的子树或节点，我还能做这种旋转吗？
2. 2. 如果没有e2和e3，我还能做这个轮换吗？

例 11；12;16

初始状态：16 是 13 的父级，13 是 10 的父级。我可以这样做：13 是 10（左）和 16（右）的父级

我知道这很简单，但是假设它很清楚，理论通常不会涵盖这些事情，但并不适合所有人。感谢帮助，

我需要修改我创建的二叉搜索树以确保它是平衡的。我只需要根据我的说明修改添加和删除方法。这是我目前拥有的：

我不是在找人来指导我完成这项任务 - 只是寻找一些关于我应该如何去做的建议，这样我就不会在中途破坏代码。我猜我需要做一些事情来检查树的平衡因子，每次添加或删除某些东西，然后在不平衡时重建树或“旋转”。

感谢您提前提供的任何建议。:) 欣赏所有提示。

-克里斯

更新：我无法让“平衡”工作，因为我无法让“doAVLBalance”识别成员函数“isBalanced()”、“isRightHeavy()”、“isLeftHeavy”。而且我不知道为什么！我完全尝试了 Sash 的示例（第 3 个答案），但我得到“减速不兼容”并且我无法解决这个问题......所以我尝试按照我的方式去做......它告诉我那些成员函数不存在，当他们显然做到了。

“错误：类“IntBinaryTree：TreeNode”没有成员“isRightHeavy”。我在尝试过去 4 小时后被卡住了 :(。下面更新了代码，非常感谢帮助！！

我正在创建一个基于字符串的二叉搜索树，并且需要使其成为“平衡”树。我该怎么做呢？*请帮忙！！提前致谢！

BinarySearchTree.cpp：

BinarySearchTree.h：

我在一本名为“Coding Interview Cracked”的书中读到，要检查 BST 是否平衡，只需找出最大和最小高度之间的差异，但我不确定它是否 100% 正确。虽然我找不到反测试用例。

任何人都可以确认这种方法是否正确。

用于检查树是否平衡。

我正在读一本关于数据结构的书，它说左平衡二叉树是一棵树，其中叶子只占据最后一层的最左边的位置。

这对我来说似乎有点模糊。这是否意味着叶子仅在根的左侧并且分布在整个级别，或者叶子仅存在于整个树的左侧。究竟什么构成左平衡？

我不确定我的猜测是否涵盖了任何答案，所以如果有人可以提供帮助，将不胜感激:-)。

我想编写一个程序来告诉我一棵树是否平衡。在这种情况下，平衡意味着相同的高度或 1 的高度差。

这是我到目前为止所写的，但它不适用于 1 的高度差。为什么？