我看到一些关于AVL的rebalance()函数实现的文章.每次插入后,我们应检查插入节点的祖先是否有平衡.所以我认为,为了检查祖先的平衡,我必须知道插入节点的父节点.
但是,我想知道有没有其他方法可以做到这一点,而不必使用父指针？例如,节点结构:
struct Node{
int data;
struct Node *lchit, *rchild; //*parent;
};
有人可以告诉我,如果使用AVL比使用2-3树更受欢迎,反之亦然,为什么会这样？
谢谢
我在AVL Tree Wikipedia页面上注意到以下评论:
"如果每个节点另外记录其子树的大小(包括它自己及其后代),那么也可以通过索引在O(log n)时间内检索节点."
我用google搜索并找到了一些提到索引访问的地方,但似乎无法找到人们会编写的算法的解释.
非常感谢
[更新]谢谢大家.如果发现@templatetypedef与@ user448810之一的链接结合起来特别有帮助.特别是这个剪辑:
"这两个函数的关键是节点的索引是它的左子节点的大小.只要我们通过它的左子节点下降树,我们只需要取节点的索引.但是当我们必须移动时通过正确的孩子在树下,我们必须调整大小,以包括我们排除的树的一半."
因为我的实现是不可变的,所以在重新平衡时我不需要做任何额外的工作,因为每个节点计算它的构造大小(与方案impl链接相同)
我最后的实施结果是:
class Node<K,V> implements AVLTree<K,V> { ...
public V index(int i) {
if (left.size() == i) return value;
if (i < left.size()) return left.index(i);
return right.index(i - left.size() - 1);
}
}
class Empty<K,V> implements AVLTree<K,V> { ...
public V index(int i) { throw new IndexOutOfBoundsException();}
}
这与其他实现略有不同,如果您认为我有错误,请告诉我!
在" 算法导论 - 创造性方法 "一书中,问题4.24:
设T1和T2为两个任意树,每个树有n个节点.证明足以将最多2n次旋转应用于T1,使其等于T2.
对于二叉搜索树,我想出了一个算法:
找到等于T2根的元素,我们称之为target-root.
使用AVL旋转策略,旋转target-root使其成为T1的新根.
在此过程中,可以执行多次旋转.
对于T1和T2的左子树,以递归方式处理它们.
对于T1和T2的右子树,以递归方式处理它们.
在最坏的情况下,该算法在O(N ^ 2)中运行.
我不太明白"任意树"这个短语,我无法弄清楚如何使T1等于T2.
有人可以帮忙解决这个问题吗？
我在Haskell中创建了一个AVL树,但我不确定如何平衡树.我可以添加元素,但它们不平衡.比如使用我在[4,2,1,3,6,8]中添加的addList方法将其添加为:
布局:根4(根2(根1空空)(根2空空))(根6空(根8空空))
应打印为:
4
2 6
1 3 8
我想平衡一棵树,但不知道如何正确实现它,这是我的代码到目前为止,任何有关这方面的帮助将是惊人的.
data AVLTree a = Empty | Root a (AVLTree a) (AVLTree a)
deriving (Eq, Ord, Show)
leaf a = Root a Empty Empty
addNode :: Integral a => a -> AVLTree a -> AVLTree a
addNode a Empty = leaf a
addNode x (Root a left right)
| x > a = Root a left (addNode x right)
| x < a = Root a (addNode x left) right
| …我最好的猜测是,当您从已经平衡的AVL树插入或删除一个元素时,一次旋转总是足以平衡AVL树.
一次轮换总是足够吗？一个例子将有助于需要多次轮换.
PS:我将RL/LR旋转计为仅一次旋转.
我知道在AVL树中找到最小节点数的公式是
S(h) = S(h-1) + S(h-2) + 1
但是,我真的不知道如何使用这个函数,比如我们的AVL高度为6.答案告诉我,Minimum = 7 + 4 + 1 = 12.但你怎么得到这个数字？我的意思是当你插入6不是它(6-1)+(6-2)+ 1？
任何人都可以向我解释如何解决这个问题？我的老师还没有谈论这个问题,但我真的想自己弄清楚这一点,以便为下周的测试做好准备.
我想更好地理解差异，但还没有找到可以将其分解到我的水平的来源。
我知道两棵树每次插入最多需要 2 次旋转。那么如何在红黑树中更快地插入呢？
以及插入如何在 avl 树中需要 O(log n) 次旋转而在红黑中需要 O(1) 次？
AVL树中的任何两个叶子之间的最大差是多少？如果我举一个例子，如果高度差大于2（对于任何两片叶子），我的树就会变得不平衡，但是答案是该差可以是任何值。我真的不明白，这怎么可能。有人可以举例说明吗？