问题标签 [avl-tree]

AVL 树与 B 树有何不同？

分页二叉树与 AVL 树和/或 B 树有何不同？

我正在编写一个滑动窗口压缩算法（LZ77），它在“移动”字典中搜索短语。

到目前为止，我已经编写了一个 BST，其中每个节点都存储在一个数组中，它在数组中的索引也是窗口本身的起始位置的值。

我现在正在考虑将 BST 转换为 AVL 树。我对我看到的示例实现有点困惑。有些似乎只存储平衡因子，而另一些则存储每棵树的高度。

存储每个节点的高度和/或平衡因子是否有任何性能优势/劣势？抱歉，如果这是一个非常简单的问题，但我仍然没有想象我想如何重组我的 BST 以实现高度平衡。

谢谢。

我正在尝试实现 AVL 树，但不确定插入和跟踪每个节点的父节点的最佳方法。这是教育性的，所以请不要建议“使用提升”:)

这可以编译，但我不相信它的正确性或者它是最好的方法。具体来说这个

此外，当我重新平衡并向上移动树时，我将重做高度部分。

我这样插入

这是方法。我不确定我的第二个参数应该在这里。我会认为 NULL 但编译器不喜欢这样（不同的函数定义）。

这是我的插入

-

我正在尝试为教育目的实现 AVL 树，但轮换没有像我预期的那样工作。

我有节点，每个节点都有一个指向左、右和父节点的指针。

下面是我的左右旋转代码。首先是输入（我要说清楚，这就是我理解的 RR 案例）

进行旋转的代码是

这实际上有效。如果 a 不是根，它甚至可以工作。

失败的测试用例类似于 dcbae

在这种情况下，我进行旋转，然后过来并插入其他东西。

我正要回去看看

http://www.cse.ohio-state.edu/~sgomori/570/avlrotations.html

但我想首先确保我不只是勉强离场，否则离得太远了。

我在 C# 中实现了一个 AVL 树，其插入矩阵如下

现在我的问题是，它对于 AVL 树来说是一个很好的性能还是我必须重新考虑更改算法或重构代码？

编辑：元素是从0到#of elements开始的整数测试代码如下

编辑：实现代码

二叉搜索树

AVL树

代码在这里： http: //pastebin.com/VAdc67bE

函数 rotacao_esquerda 存在问题。这是 AVL 树的旋转。

如何解决？

为什么获得 AVL 树的平衡过程称为旋转？（当你在它的时候，什么是单双旋转？）

我的每一本教科书都公然使用这个词，没有任何解释。

在执行旋转以平衡 AVL 树后，在插入后立即如何更改所有父节点的平衡因子（适当地，通过 -1 或 1）？

AVL 树的每个节点具有以下结构：

我已根据Wikipedia上给出的定义设置了平衡因子。

我需要在每个节点中都有一个指向父节点的指针吗？

当我递归调用插入函数以将节点添加到 AVL 树时，如何计算特定节点的平衡因子。我还没有开始旋转逻辑。我只是想计算平衡因子。

在我目前的尝试中，我被迫存储左右子树的高度，因为没有它们我找不到平衡因子。