标签: avl-tree

我正在努力想弄清楚如何为我的班级平衡AVL树.我已经插入了这个:

Node* Tree::insert(int d)
{
    cout << "base insert\t" << d << endl;
    if (head == NULL)
        return (head = new Node(d));
    else
        return insert(head, d);
}

Node* Tree::insert(Node*& current, int d)
{
    cout << "insert\t" << d << endl;
    if (current == NULL)
        current = new Node(d);
    else if (d < current->data) {
        insert(current->lchild, d);
        if (height(current->lchild) - height(current->rchild)) {
            if (d < current->lchild->getData())
                rotateLeftOnce(current);
            else
                rotateLeftTwice(current);
        }
    }
    else if (d > current->getData()) {
        insert(current->rchild, d);
        if (height(current->rchild) …

好吧,这是CS领域的另一个理论领域.

在90年代,我在实施BST方面做得相当不错.我唯一无法理解的是算法的复杂性以平衡二叉树(AVL).

你能帮助我吗？

维基百科关于AVL树的文章的第三段说:"由于AVL树更加严格平衡,因此对于查找密集型应用程序来说,它们比红黑树更快."

因此,不应该使用AVL树而不是红黑树来实现TreeMap(因为基于散列的数据结构会有更多的查找密集型应用程序)？

在给定一定数量的节点的情况下,是否有公式来计算AVL树的最大和最小高度？

例如:
教科书问题:
3个节点,5个节点和7个节点的AVL树的最大/最小高度是多少？
教科书答案:
3个节点的AVL树的最大/最小高度为2/2,5个节点的最大/最小高度为3/3,7个节点的最大/最小高度为4/3

我不知道他们是否通过一些神奇的公式计算出来,或者他们是否为每个给定的高度绘制了AVL树并确定了它.

我正在使用由随机样本无法区分的概率加密元素组成的数据集.这样,相同数量的顺序加密导致不同的密文.然而,这些仍然可以通过应用SHA256等算法来比较两个密文的特殊函数进行比较.

我想将一个描述的密文列表添加到MongoDB数据库,并使用基于树的结构(即:AVL)对其进行索引.我不能简单地应用数据库的默认索引,因为如上所述,记录必须使用特殊函数进行比较.

示例:假设我有一个数据库db和一个由以下文档类型组成的集合c:

{
  "_id":ObjectId,
  "r":string
}

另外,让F(int,string,string)成为以下函数:

F(h,l,r) = ( SHA256(l | r) + h ) % 3

操作员在哪里 是标准的连接函数.

我想以有效的方式执行以下查询,例如在具有一些合适索引的集合中:

db.c.find( { F(h,l,r) :{ $eq: 0 } } )

对于h和l任意选择但不是常数.即:假设我想找到满足F(h1,l1,r)的所有记录,对于某些对(h1,l1).后来,在另一个时刻,我想做同样的但是使用(h2,l2)使得h1!= h2和l1!= l2.h和l可以假设整数集合中的任何值.

我怎样才能做到这一点？

上面的图片来自"维基百科在AVL树上的条目",维基百科表示这是不平衡的.这棵树怎么还没有平衡？这是文章的引用:

节点的平衡因子是其右子树的高度减去其左子树的高度,并且具有平衡因子1,0或-1的节点被认为是平衡的.具有任何其他平衡因子的节点被视为不平衡,需要重新平衡树.平衡因子或者直接存储在每个节点上,或者从子树的高度计算出来.

左右子树的高度均为4.左侧树的右子树的高度为3,仍然只有1小于4.有人可以解释我缺少的东西吗？

我已经在几个地方阅读了它,可以更快地搜索树,但无法理解.据我了解:红黑树的最大高度= 2*log(N + 1)AVL树的高度= 1.44*标识(N + 1)

是因为AVL更短吗？

我用过kd-tree algoritham并制作树.

但是我发现树不平衡所以我的问题是如果我们使用kd-tree algoritham那么树总是平衡的,如果没有那么我们怎样才能使它平衡？

我们可以使用另一个algoritham喜欢AVL或Red-Black来平衡kd树吗？

我有一些示例数据,我使用kd-tree algoritham,但树不平衡.

 (14,31), (15,32), (17,42), (16,44), (18,52), (16,62)

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

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

   A
  /  \ 
 A    A

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

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

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

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

我有一个数据结构作业,除了常规的AVL树函数,我还要添加一个函数,它返回AVL树中任意两个数字之间的最小间隙(AVL中的节点实际上代表数字.)

假设我们在AVL树中有数字(作为节点)1 5 12 20 23 21,该函数应该返回任意两个数字之间的最小间隙.在这种情况下它应该返回"1",即| 20-21 | 或| 21-20 |.

它应该在O(1)中完成.

试图思考很多,我知道有一个伎俩但是找不到它,我已经花了好几个小时.

还有另一项任务是找到最大间隙,这很容易,它是最小和最大数之间的差异.