标签: avl-tree

我想avl-tree支持重复键但是复制的默认行为存在问题,binary search tree即旋转可以使具有相同键的节点位于父级的左侧和右侧.

例如,当添加三个节点时,所有带有键A的节点将使树进行旋转,如下所示:

   A
  /  \ 
 A    A

因此,使用该密钥获取所有条目将是一个问题......并且在两个方向上搜索都不是很好.

我想到的解决方案是让每个节点都存储一个重复数组,所以当添加一个已经存在的新项目时,只需要向数组添加一个新项目,删除带有键的项目将删除整个节点,同时查找所有项目使用key将返回该数组.

是否还有其他方法可以处理重复项？

插入项采用一个键和一个值..所以我需要存储值以便通过findAll使用某些键方法返回它们.

什么是Scala 2.10.x中应该使用的标准平衡二叉搜索树实现？我环顾四周,它似乎已AVLTree被删除,并RedBlack已被弃用(Since version 2.10.0) use TreeMap or TreeSet instead.但是,TreeMap并TreeSet没有提供我需要的功能,因为我需要能够遍历树并基于此构建更复杂的数据结构.

是否有任何新类提供了不被弃用的普通平衡二叉树功能？

我有一个理论问题Balanced BST.

我想构建Perfect Balanced Tree具有2^k - 1节点的节点unbalanced BST.我能想到的最简单的解决方案是使用排序Array/Linked list并递归地将数组划分为子数组,并Perfect Balanced BST从中构建.

但是,在树大小非常大的情况下,我需要创建一个Array/List相同大小的内容,因此这种方法会占用大量内存.

另一种选择是使用AVL旋转功能,逐个元素插入并根据树平衡因子平衡树和旋转 - 左侧和右侧子树的三个高度.

我的问题是,我对我的假设是对的吗？还有其他方法可以BST从不平衡中创造完美BST吗？

我已经实现了一个AVL树,但我遇到了问题.

假设我有以下树:

并在添加另一个节点后:

现在我必须将node5旋转到左边:

但轮换后,它仍然是不平衡的.

我哪里弄错了？

所以,我正在尝试实现一个数据结构来处理动态订单统计.数据结构具有以下操作:

• add(x):插入值为x的新元素
• get(k):返回第k个最小元素:k = ceiling(n/a),其中n =数据结构中元素的数量,a =常数因子.
• reset:重置整个数据结构,即数据结构在其后为空

我使用平衡的AVL树实现了我的数据结构.使用此操作具有以下时间复杂度:

• add(x):O(log(n))
• get(k):O(log(n))

这是我使用O(log(n))时间的get(k)的实现:

public static int get(Node current, int k) {
    int l = tree.sizeLeft(current) + 1;
    if(k == l) {
        return current.value;
    } else if(k < l) {
        if(current.left == null) {
            return current.value;
        }
        return get(current.left, k);
    } else {
        if(current.right == null) {
            return current.value;
        }
        return get(current.right, k);
    }
}

这是我对节点类的实现:

class Node {
int height, value, bal, size;   // bal = balanceFactor, size = amount of …

.NET库中是否有内置的AVL树？

我搜索但没有找到任何.

• 如果有,那么在哪里？什么名称空间
• 如果没有,C#中的AVL树有什么好的实现吗？
• 如果还没有!那么有一个简单的方法来完成它吗？我知道它是如何工作的,并且之前用原生C++构建了一个,但现在我没有时间,如果我自己做的话,我害怕性能不好.

用于链接存储器映射的可执行文件的各个部分的vm_area_struct结构存储为红黑树.现在,据我所知和这里的帖子提到太红黑树和AVL树之间的区别 AVL树比RB树执行更快的查找.

此树由进程引用的虚拟地址编制索引,并在进程开始执行时创建.我希望这棵树可以用于查找,有时也可以用于插入和删除.如果是这种情况,那么为什么AVL树不优于RB树作为相同的实现.

此外,如果我的理解不正确并且树涉及大量插入和删除,与查找相比,请提供参考以支持此声明.

我已经看到一些关于tldp的文章提到早期的AVL树也被用于相同的文章.请解释这种变化带来的原因是什么？

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

据我所知,AVL树和二进制搜索树之间的时间复杂度在平均情况下是相同的,在最坏的情况下AVL击败BST.这给了我一个提示,即AVL总是优于BST以各种可能的方式与它们进行交互,在平衡实现方面可能会增加一些复杂性.

是否有任何理由首先应该使用BST而不是AVL？

相信维基百科文章:http://en.wikipedia.org/wiki/AVL_tree

AVL树是高度平衡的,但通常不是重量平衡的,也不是μ平衡的; [4]也就是说,兄弟节点可以有非常不同数量的后代.

但是,作为AVL树是:

自平衡二进制搜索树[...].在AVL树中,任何节点的两个子子树的高度最多相差一个

我不知道AVL是如何重量不平衡的,因为如果我理解AVL树的定义,每个兄弟都会有大约相同数量的孩子,因为他们有相同的身高+/- 1.

那么,你能给我一个不平衡的AVL树的例子吗？我没有成功找到一个.因此,或者我误解了AVL /未加权树的定义,或维基百科文章是假的......

谢谢