问题标签 [avl-tree]

基本上你有一个充满值的 BST。例如。1-16 a min,max and value (10,15,3) 并且您需要找到 BST 中的值与树的 min 和 max 内的给定值之间的最大异或值。

我想知道是否有一种方法可以在不遍历整个树的情况下做到这一点。如果 min 和 max 不存在，我的方法是。

基本上继续关注产生更高异或值的节点。

我在使用 min 和 max 时遇到的问题是，当我对 node>=min && node<=max 进行检查时，树会很好地遍历，但是当我在范围内时，我可能会采取错误分支到范围之外的数字。

让我解释。采取 BST 1-16 的右侧

给定：

• 最小值 = 10
• 最大值 = 15
• 值 = 3

最大异或值为3^12=15

然而，使用我的算法，当我在 13 节点时，我没有将左树带到 11，而是将右树带到 15（因为它试图达到 16，但那超出了范围）。

有没有人有更好的解决方案？我应该对我的 BST 进行不同的排序吗？我应该使用什么东西而不是 BST 吗？是否可以在不遍历整个值列表的情况下执行此操作？这里的假设是我将有一个值列表（我放入 BST 中的那些），然后是我必须应用于值列表的参数列表（最小值、最大值、值）。

我需要定义一个读取整数并按升序打印回来的主函数。

但是，我需要使用树木来做到这一点。我可以使用两个功能insertavl，并且deleteavl可以随意使用。他们的定义是这样的...... http://ideone.com/8dwlU 基本上当 deleteavl 被调用时，它会删除节点，并相应地重新平衡树......如果有兴趣他们的结构在：http: //ideone.com/ ｛｝｝｝．

到目前为止，我已经得到了这个：

但这不会按升序打印它们。任何的意见都将会有帮助？提前致谢！

我在 AvlTree 类中实现了一个类迭代器。我的 AvlTree 节点如下：

我的迭代器如下：

我的 AvlTree 还有一个作为公共成员的开始和结束迭代器：

我的问题是，当我尝试在 main 中运行以下命令时：

我没有按顺序输出字符串树中的所有单词，而是得到了树中第一个按顺序项的无限循环。我似乎无法弄清楚为什么它不会超过第一项。

所以我基本上有函数avl？运行在 O(n^2) 中，这是因为每次我递归时，我都在调用高度，它是 O(n) 函数（其中 n 是树中的节点数）。

我的问题是我想做avl？在 O(n) 时间内运行。我得到了提示：“无论你应用多大的 BST，你都应该尽量限制在恒定时间内调用你的高度函数。这样，​​你可以获得 O(n) 的运行时间。” ......我不知道如何让我的身高在恒定时间内运行。有什么建议让我做avl吗？在 O(n) 而不是 O(n^2) 中运行？

我正在创建一个自排序二进制搜索树的任务，每次尝试将重复元素插入树时都会重新组织它。我遇到了一些需要帮助解决的错误。

首先，树的根永远不会改变（我假设问题出在 RotateLeft 或 RotateRight 方法中）当第一个副本进入时，根永远不会更改为现在更高优先级的节点。

我得到的第二个错误是 BAD ACCESS ERROR（我已经注意到它在下面的代码中的位置），我猜它也是来自这些 Rotate 方法之一。

这是 BinaryNode 结构的代码：

有没有人看到我可以改变以提供帮助的任何东西？

AVL树旋转的Big O效率具体是多少？

例如插入时： - O(logN) 搜索位置 - O(1) 插入 - ? 用于平衡（如果需要重新平衡）

我以为它会是 O(logN)，但我发现一个声称它是 O(1) 的网站 - 除非我读错了 - http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

（这对于 2-3 树也一样吗？）

我在这里先向您的帮助表示感谢

我有一个使用 AVL 树快速搜索 IP 地址的大型系统：

所以搜索基于'struct nhlfe_key'，即AVL树中的比较器函数如下所示：

现在，我要做的是添加对多个下一跳的支持，即我在 nhlfe_entry 中添加一个链表：

每个'struct list'都是struct listnode，它嵌入'void *data'指针到调用者的私有数据，这就是'struct nhlfe_key'。

所以我的问题是——如何基于列表中的多个元素生成密钥以存储/搜索树中的节点（因为否则现在在引入列表之后，将不可能仅基于一个 下一跳地址）。此外，他们同样的问题适用于搜索。

另外，在列表中添加新节点后，是否需要重新构建树，因为我认为此操作会更改键，因此树可能会变得不平衡？（或者正确实现的AVL树自然不需要重建？）

我正在考虑在每个列表节点上生成 CRC，然后进行总结。这可以保证密钥的唯一性吗？（缺点是每当我添加/删除列表节点时，我必须重新生成密钥，从树中删除节点并使用新密钥重新添加）。

谢谢！

我正在尝试实现 AVL。这是我的插入、balance_tree、check_bf（平衡因子）和单左旋转函数的顺序：

我用一棵需要向左旋转的小树进行了尝试：

单次左旋转函数结束时，t指向2，1为左节点，3为右节点，所以函数起作用。树看起来像这样：

但是，当它退出函数时，t 指向 1，没有左节点或右节点。我不明白 return t 和右括号 } 之间会发生什么，它结束了更改 t 的函数。任何人都可以帮忙吗？

为我的数据结构课程编写一个 AVL 树来保存泛型；在我的 add() 方法中，在实际插入一个元素之后，我会通过它的祖先检查他们的分数。对于最初的几个添加，它可以工作，但是（大概是在确实需要进行平衡的地方），备份路径的循环无法终止。我已经尝试了我能想到的一切来确保树的父节点的根没有被设置为另一个节点或类似的东西。我将平衡分数计算为右减左，所以正数表示树右重，负数表示左重。这是我的添加（）：

这是正确的旋转方法：

我了解 AVL 树如何与整数一起工作。但我很难找到一种将字符串插入其中的方法。如何比较字符串？

我曾想过只使用 ASCII 总值并以这种方式排序。但在这种情况下，插入两个相同的 ASCII 词（例如“tied”和“diet”）似乎会返回错误。

你如何解决这个问题？我是否以错误的方式思考它，并且需要一种不同的方式来对节点进行排序？

不，它们不需要按字母顺序排列或任何东西......只需在 AVL 树中，这样我就可以快速搜索它们。