问题标签 [avl-tree]

我有一个 BST AVL，用 Java 编写，我需要通过打印最后十个节点来证明它是平衡的。我的 hack-y 解决方案是，知道节点的数量，从有序遍历的最后 10 个节点中获取值。它没有按预期工作。记录与姓氏键一起存储（不保留重复记录），每个节点大小的打印输出结果为 0。我的打印输出主要包含“Z”名称……正如预期的那样，然后它还包含打印输出的第一条记录（26000 条）。我猜测（希望）这是我如何设计打印输出的问题，而不是树中的错误？有没有更优雅的方法来打印最后 10 个节点，不会出现我现在遇到的错误，或者我的树旋转可能存在缺陷？

InOrder 遍历和输出：（通过 get 函数访问的输出）

put 方法：（通过传递根节点、键和值的方法调用）

如果这看起来像是一个随机问题，我很抱歉，但我有一个包含超过 100,000 个名称/值对的数据库（如果你愿意，可以称它们为高分），存储在 AVL 风格的平衡二叉搜索树中。大多数时候，为了列出分数，我使用中序遍历或逆序遍历来打印 BST，但今天我遇到了以随机（或伪随机）顺序打印树的需求。是否有一些公认的或最佳的方式来做到这一点：只访问每个节点一次，但以不可预测的方式？

PS——我考虑过广度优先遍历，但由于它总是以同样的方式发生，它并不是真正随机的。必须有一些聪明的方法，或者一些理想的面试答案，因为这似乎是一个普遍的问题；除了将节点标记为已访问或创建外部跟踪数据结构之外，我还没有想出任何真正聪明的方法。

我正在用 C++ 编写一个 AVL 树程序。我基于我之前制作的 BST 优先队列程序。不幸的是，每次添加应该导致旋转的新节点时，都会引发堆栈溢出异常。

到目前为止，这是我的代码：

节点.h

AVL.h

AVL.cpp

我正在研究 AVL 树，但似乎找不到关于删除的参考代码（通过谷歌搜索或从我方便的几本教科书）。
我不确定为什么会这样，但是您知道在 java 中删除 AVL 的任何参考/示例吗？
（我只发现了这个：avl tree removal，它在链接中说明它在测试中失败）

某个节点的左右子节点的高度相差 2 有什么问题？

这是我第一次接触 AVL 树，我似乎无法理解为什么它是必须的？

真的，孩子相差2岁有什么问题？

问候

我正在尝试Insert在将新元素插入 AVL 树时更新操作。对操作的更新insert将向每个节点添加其根树的大小。

现在，由于我自下而上插入我的元素，那么如果我只是+1为巡视时通过的每个节点添加一个，那么在某些情况下这将不起作用，例如当我需要在新树之后平衡树时不平衡，既然我改变了指针，那么计算就不会正确。

任何想法或提示我该如何正确地做到这一点？

我正在尝试实现 AVL 树，但似乎在使用 Node 类时遇到了问题。我收到错误 C4430: missing type specifier with the second getHeight 我以为我将类型指定为子树的节点？

我在下面有一个基本算法，我知道最坏情况的输入 BST 是从插入到仅一侧退化为链表的输入。

我如何计算这个 BST 到 AVL 转换算法的旋转次数的最坏情况复杂度？

我的树的平衡部分遇到了问题。我在递归插入后调用了 checkBal。如果我尝试添加 5、2 和 4，它会检查 2 的平衡并继续回到 5，然后进入右旋转的 rotateLeft 部分，这是正确的。但是第二行的 rotateLeft 函数出错。

这个实现有什么问题？我到处搜索并将我所做的与人们谈论它是如何完成的方式进行比较。我终于让一切正常了。最后我忘记将 N 设置为 K 了。

我在AVL 树维基百科页面上注意到以下评论：

“如果每个节点还记录了其子树的大小（包括它自己及其后代），那么这些节点也可以在 O(log n) 时间内通过索引检索。”

我用谷歌搜索并找到了一些提到按索引访问的地方，但似乎找不到人们会写的算法的解释。

非常感谢

[更新] 谢谢大家。如果找到@templatetypedef 答案与@user448810链接之一相结合，特别有帮助。特别是这个snipit：

“这两个函数的关键是节点的索引是它的左孩子的大小。只要我们通过它的左孩子下降一棵树，我们只需要节点的索引。但是当我们必须移动时通过它的右子树向下，我们必须调整大小以包括我们排除的树的一半。”

因为我的实现是不可变的，所以在重新平衡时我不需要做任何额外的工作，因为每个节点都会计算它的构造大小（与方案 impl 链接相同）

我的最终实现最终是：

这与其他实现略有不同，如果您认为我有错误，请告诉我！