问题标签 [avl-tree]

我在avl树搜索速度更快但无法理解的几个地方阅读过它。据我了解：红黑树的最大高度 = 2*log(N+1) AVL 树的高度 = 1.44*logo(N+1)

是因为AVL更短吗？

在向树中添加新项目后，我试图平衡我的 AVL 树，但我不断收到 NPE。我相信我已经把它缩小到与我的 balance() 方法有关的事情，或者更具体地说，我的 rotateLeft() 和 rotateRight() 方法。这是我的 AVLTree 类：

我是在错误地使用我提到的方法，还是在进行平衡之前错误地添加到树中？

我创建了一个 AVL 树，其中包含有效的 Add 和 Remove 方法。但是，我需要以可视格式打印出树。例如，如果平衡树当前包含 1、2、3，它看起来像这样：

有没有相对简单的方法来做到这一点？（您可以假设在添加或删除值后，我的树将始终保持适当的平衡。）

假设我有一个无序集 s{3,6,5,1,2,4}，我需要构建一个 AVL 树，
这很好......我了解基本旋转，我在这里达到这一点：

但是当我尝试插入 4 并且我得到最终答案时，一切都崩溃了（左侧）

当我分解它时，我会卡在做同样的旋转
，所以我问我如何与对这个 AVL 有效的父级进行旋转？

我的解决方案有效吗？

给定下面的 AVL 树：

可以在 40 度时进行单次旋转吗？使它像这样：

与左子树相比，它仍然符合具有 -+1 高度的 AVL 属性。

在答案中，它进行了两次旋转，因此上面 35 处的子树在之后看起来像这样：

如果它们都没有违反 height 属性，我不明白何时进行双重旋转以及何时进行单次旋转。

到目前为止，我一直在制定一个攻击计划，看看我如何才能做到这一点，这就是我所拥有的：

bool isEmpty() const- 如果为空，则返回 true，否则返回 false

int getSize()- 返回字典中存储了多少单词

void insert (String word)- 如果不存在，则将单词插入字典，否则更新。

boolfind(String word, WordNode & x)- 如果单词存在，则返回 true，并将数据放入 x。

void printSorted()- 按字典顺序（指定）打印树中的单词

void remove (String word)-实现节点的延迟删除

我有我想做什么的概念，并且我了解 AVL 树的工作原理。但是在实际编写代码时我完全卡住了，有人可以帮我开始吗？

我正在实现 AVL 搜索树。到目前为止，我已经完成了编码部分，并开始测试它的错误。我发现我的节点旋转方法有问题，看在上帝的份上，我无法理解问题所在。

该算法在纸上工作，但在机器上执行时它很好......泄漏树节点。

这是用于向左旋转节点的方法：http: //pastebin.com/mPHj29Af

在我的插入方法中，我评论了 AVL 平衡部分，而我只是试图将新插入的节点向左旋转。以升序插入整数的结果：我的树只包含初始根（插入的第一个节点），所有其他节点都泄漏了。

由于我开始发疯，因此非常感谢您在识别问题方面的任何帮助。

记录一下：如果我不使用任何旋转，树不会泄漏节点，它可以作为正常的不平衡二叉搜索树（用于插入和查找）。

编辑：由于 AJG85 的评论，我将添加观察结果：

我将 printf 'checks' 添加到 avl_search_tree::avl_tree_node 的析构函数方法中，该方法将在清理之前打印键值（在我的情况下为 32 位整数），并添加到 avl_search_tree 的 insert 方法中，该方法将打印刚刚插入的键。

然后在程序的入口点中，我在堆上分配一个 avl_search_tree 并按升序向它添加键，然后将其删除。

启用 AVL 平衡后，我在终端中得到以下输出：

这意味着所有插入都成功，但只有根已被删除。

注释掉 AVL 平衡后，它的工作原理就像一个普通的二叉搜索树。终端输出为：

这意味着一切都已妥善清理。

现在......我是如何得出轮换方法是问题的结论？在注释的 AVL 平衡子程序下，我添加了一条线，将每个新插入的节点向左旋转。结果？就像启用了 AVL 平衡子例程一样。

而关于 update_height() 方法，它不会以任何方式改变树的结构。

我希望这会澄清它。

编辑2：

为了澄清更多的事情，他是如何实现 avl_tree_node 析构函数的：

_left_child 和 _right_child 是指向在堆上分配的 avl_tree_node 对象的指针。

编辑3：

感谢 AGJ85 的第二条评论，我发现了这个问题。在我的旋转方法中，我忘记了每当根移动时我实际上必须将树的根指针更新为新根。

基本上，树的根始终指向第一个插入的节点，并且在需要时不更新指针，我的旋转方法会泄漏实际配置正确的新树的根。:)

谢谢AGJ85！

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

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

用于检查树是否平衡。

我在尝试实现的 AVL 树中遇到了一些编译错误。有什么东西让整个枚举器失望了。在我尝试实现一个辅助类之前，它编译得很好。我认为这与 BTNode 本身是一个私有嵌套类有关，但尝试将其公开只是为了看看会发生什么，但无济于事。

我对此有点难过，不应该进行任何转换。

任何帮助将不胜感激。

这是源代码，我已经注意到编译错误的位置，并分解了不同的嵌套类以便于阅读。

节点类——

枚举器辅助类——

--

--

安...

看了一些关于AVL的rebalance()功能实现的文章。
每次插入后，我们应该检查插入节点的祖先是否平衡。
所以我想，为了检查祖先的余额，我要知道插入节点的父节点。

但是，我想知道有没有其他方法可以做到这一点而不必使用父指针？
例如，节点结构：