标签: avl-tree

Java中TreeSet方法的计算复杂度是否与AVLTree相同？

具体来说,我想知道以下方法的计算复杂性:1.add 2.remove 3.first 4.last 5. floor 6. higher

用于方法描述的Java Doc:http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

对于AVL树,有所有O(logn)？什么是上述TreeSet方法的复杂性？

是否有这样一个数字序列(1-7,所有使用的数字,每个只有一次),它们会形成相等的AVL和splay树？

这个非常简单的代码块有问题.请给我你的建议. (我的这个问题已经解决了,在解决这个问题时,有id stakx的人确实对我有帮助,唯一的问题是我正在使用stack <treeNode>,当我仔细看到堆栈的推送方法时,有一个复制过程当我写head-> object = number时,最后我做了一堆指针,就像这个堆栈<treeNode*>它真的解决了问题,我现在没有问题,我非常非常感谢stakx.)

在代码之前你需要支持以下树的

替代文本http://img44.imageshack.us/img44/7016/avlimage06.jpg
,你可以在图片中看到root是8,堆栈有两个节点,即6和4.我将此堆栈和根节点传递给以下代码

void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)
{
if(!s.isempty())
{
treeNode *stacknode;
stacknode=s.pop();
cout<<"\ninside the attachwithtree function, stack node is "<<stacknode->data;
stacknode->right=tree;//attaching the passed node to the right of popped node
root=stacknode;//setting the root to stack node which is the private data member of class
updatebalance(root);//this function is ok, it does not create problem
while(!s.isempty())
{
cout<<"\nstack is still not empty";
stacknode=s.pop();
cout<<"\nright side of "<<root->data<<" is "<<(root->right)->data;
//the below three lines causing …

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

我有x(百万)正整数,其值可以与允许的值一样大(+2,147,483,647).假设它们是唯一的,那么将它们存储为查找密集型程序的最佳方法是什么.

到目前为止,我想到了使用二进制AVL树或哈希表,其中整数是映射数据(名称)的关键.但是我不确定我是否可以使用哈希表来实现如此大的密钥(除了容易发生冲突之外,还不会产生> 0.8的加载因子吗？)

我可以得到一些关于哪种数据结构可能适合我的情况的建议

假设我有两个AVL树,并且我知道它们各自的大小.但是,我不知道是否有重复的节点或任何其他信息.在新的AVL树中合并它们的最有效方法是什么？原始树木可以被摧毁.

我在一些论文中看到了这一点,并且有人认为当我们删除AVL树的节点时,最多可以有log(n)次旋转.我相信我们可以通过生成尽可能不平衡的AVL树来实现这一目标.问题是如何做到这一点.这对于研究去除旋转物有很大帮助.非常感谢!

AVL树中的任何两个叶子之间的最大差是多少？如果我举一个例子，如果高度差大于2（对于任何两片叶子），我的树就会变得不平衡，但是答案是该差可以是任何值。我真的不明白，这怎么可能。有人可以举例说明吗？

想象一下,我有一个很大的整数排序列表(> 1000项).我需要能够在此列表上执行两个操作:删除下半部分并通过插入随机整数将列表再次填充到其原始大小.因为我做了大约一百万次这些操作,所以我需要它尽可能高效.

我做的第一件事就是使用List我通过在正确的位置添加新项目进行排序的方法.虽然删除排序列表的下半部分非常容易,但插入需要相当长的时间.

我尝试实现一个跳过列表,但经过一些测试后,列表的大小似乎必须至少为10000才真正重要,否则它的表现甚至比我的正常列表更糟糕.

这就是为什么我决定使用AVL树,所以我可以更快,更快地插入项目.但问题是我不知道删除这种二叉搜索树的下半部分的任何有效方法.

我的问题是:有没有一种有效的方法来做到这一点？还有其他我可以更轻松使用的数据结构吗？

编辑

如上所述,我做了一个小测试,显示了列表,跳过列表和AVL树之间的性能差异.我在msdn:Skip list tutorial上使用本教程制作了跳过列表.AVL树来自这里:AVL树.我在dropbox上传了测试:示例.还有关于pastebin:程序.

在测试中,我在计时时为每个数据结构添加了10万个项目.在我的电脑上,列表大约需要1秒,跳过列表需要0.5秒,AVL树需要0.045秒.如果我按照我的意愿做了一百万次,那么这个列表大约需要11.5天,但AVL树只需要大约半天.这个时间差异清楚地表明了我希望它有效的原因.

AVL树与自平衡二叉搜索树相同.AVL代表什么？这与发明人的名字有关吗？