问题标签 [avl-tree]

每次我使用这个我的 avlRotate 函数时，它都会从树中删除一些元素。z 是检测到不平衡的节点，y 是其高度较大的子树节点，x 是新插入的节点。此函数在单次插入后立即调用。

该函数通过以下方式调用：

在插入函数中。

输出：

这个功能明显不正确吗？

注意：每个节点都存储一个范围，例如。3 to 5.

我正在考虑尝试使用树结构进行索引，因为我想测试它是否比我当前的索引实现更快，这本质上是基于哈希的查找。

我已经阅读了有关 B-Trees、AVL-Trees 和 Red-Black Trees 性能的各种问题和文章，并且在性能方面看不出它们之间有多大区别。

人们会推荐什么树结构，为什么？理想情况下，它应该有一个现有的 .Net 实现可用，但我不反对在必要时实现我自己的

我已经创建了一个 AVL 树实现，但是由于 AVL 树是一个相当复杂的结构，我需要对其进行测试。所以问题是 - 我该如何测试它？

到目前为止，我有以下测试：

1. 基本健全性检查 - 检查每个节点高度是否等于最大值。子节点的高度+1，平衡在[-1, 1]，左孩子的key <这个节点的key <右孩子的key，并且没有循环引用（就像一个节点的左孩子就是一个节点自己）；

2. 检查 AVL 树（以及整个二叉搜索树）上的中序遍历是否会按顺序返回底层集合中的值；

3. 检查 AVL 树的高度是否严格小于 1.44*log2(N+2)-1（有 N 是元素数） - 由 AVL 树创建者证明；

4. 视觉检查 - 效果不太好，我尝试画一棵树（第一行是根节点，下一行是他的直接子节点，第三行是根节点的直接子节点的子节点，依此类推），但这仅适用于小树，大树变得一团糟；

5. 俄罗斯维基百科说，实验证明，两次插入需要一次重新平衡，五次移除也需要一次重新平衡，但真的如此吗？英文维基百科对此一无所知，对于我的 AVL 来说，两次插入或四次移除需要一次重新平衡，这并不完全相同。

也许这些测试已经足够了，但如果还有更多的测试，不难实现，为什么不做呢？

我很难弄清楚如何为我的班级平衡 AVL 树。我已经用这个插入了它：

我的计划是调用 balance() 检查树是否需要平衡，然后根据需要进行平衡。问题是，我什至不知道如何遍历树来找到正确的不平衡节点。我知道如何递归地遍历树，但我似乎无法将该算法转换为找到最低的不平衡节点。我在编写迭代算法时也遇到了麻烦。任何帮助，将不胜感激。:)

我有 x（百万）个正整数，它们的值可以尽可能大（+2,147,483,647）。假设它们是独一无二的，那么为查找密集型程序存储它们的最佳方式是什么。

到目前为止，我想到了使用二叉 AVL 树或哈希表，其中整数是映射数据的键（名称）。但是我不确定我是否可以使用哈希表实现如此大的键和如此大的数量（除了容易发生冲突之外，这不会产生> 0.8的负载因子吗？）

我可以就哪种数据结构可能适合我的情况获得一些建议吗

我有一些关于 AVL 的问题，假设我创建了一些整数的 avl-tree，我需要如何管理插入到我的树中才能取出最长的数字序列，（插入必须具有复杂度 O(logn ））， 例如：

在这种情况下，最长的序列将是 6,7,8 所以在我的函数中void sequence(int* low, int* high)我会做 * low = 6, *high = 8...

函数（序列）的复杂性必须是 O(1)

提前感谢您的任何想法

假设我有两棵 AVL 树并且我知道它们各自的大小。但是，我不知道是否有重复的节点，或任何其他信息。将它们合并到新的 AVL 树中的最有效方法是什么？原来的树可以被破坏。

我正在尝试基于具有特殊要求的 AVL 树创建一些等级树，假设我有带有节点的 AVL 树，每个节点有 2 个字段：

我的 AVL 树按 id 排序，我还有一个功能：

这降低了小于或等于此函数的所有 id 的优先级currentId必须delta 处理复杂度 O(log n)，所以我的问题是我需要存储哪些附加信息才能使用highest priorityat弹出节点任何阶段with complexity O(1)（也使用 foo 之后！）。

P.S.我试图在右子树中存储有关最大优先级的信息，在左子树中存储有关最大优先级的信息，但是在foo. 它需要的不仅仅是 O(log n)。在此先感谢您提供有关树木的任何好主意或好书。

我有以下 AVL 树：

如果我插入 3 那么我得到：

如果我计算每个节点的平衡因子，似乎每个 BF 都是有效的： (Node:BF) -> 10:1, 5:0, 2:-1, 1:0, 4:-1, 8:0, 7:0, 9:0, 3:0, 12:0, 11:0, 13:0 但显然这棵树需要重新平衡。哪里有无效的BF，然后如何进行必要的旋转。

我目前正在学习 c 和算法。我已经将一个模拟字典实现为一棵树，并且想进一步学习我的课程并使用 avl 树。

我试图在网上寻找一个实现，发现解释相当混乱。有人可以为我指出如何将这个树结构更改为 avl 树结构的正确方向。

谢谢