标签: tree-balancing

我正在寻找计算AVL树中节点平衡的最佳方法.我以为我有它工作,但经过一些繁重的插入/更新,我可以看到它的工作正常(根本没有).

这是一个由两部分组成的问题,第一部分是如何计算子树的高度,我知道定义"节点的高度是从该节点到叶子的最长向下路径的长度".而我理解它,但我没有实现它.并且为了进一步混淆我这个引用可以在维基百科的树高上找到"传统上,值-1对应于没有节点的子树,而零对应于具有一个节点的子树."

而第二部分是得到一个子树的平衡因素,AVL树,我没有问题理解概念,"让你的高度L和R子树和减去R从L".这被定义为这样的事情:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读在描述插入到AVL树中的前几行中说:"如果平衡因子变为-1,0或1,那么树仍然是AVL形式,并且不需要旋转."

然后继续说,"如果平衡因子变为2或-2,那么植根于此节点的树是不平衡的,并且需要树旋转.最多需要单次或双次旋转来平衡树." - 我没有抓麻烦.

但是(是的,总有一个但是).

这是令人困惑的地方,文本说明"如果R的平衡因子为1,则意味着插入发生在该节点的(外部)右侧,需要左旋转".但是从理解的角度来看,正如我所引用的那样,如果平衡因素在[-1, 1]那之内,那么就没有必要进行平衡了吗？

我觉得我是如此接近抓概念,我已经得到了树旋转下来,实现正常的二叉搜索树,抓AVL树的边缘,但只是似乎缺少必要的顿悟.

编辑:代码示例比学术公式更受欢迎,因为我总是更容易在代码中掌握一些东西,但是非常感谢任何帮助.

编辑:我希望我能将所有答案都标记为"已接受",但对我而言,NIck的答案是第一个让我走"aha"的答案.

我正在Haskell中设计一个自平衡树.作为一项练习,因为你的后背很好.

之前在C和Python中,由于其简单的平衡规则,我更喜欢Treaps和Splay Trees.我总是不喜欢R/B树,因为它们似乎比它们的价值更多的工作.

现在,由于Haskell的功能性,事情似乎发生了变化.我可以用10行代码编写一个R/B插入函数.另一方面,Treaps需要包装以存储随机数生成器,并且Splay Trees是自上而下的痛苦.

所以我问你是否有其他类型树木的经验？哪些更好地利用函数式语言的模式匹配和自上而下的性质？

为了好玩我决定写一个简单的程序,可以解决8个十分之一的猫倒数数字拼图,链接是形式倒计时,但相同的规则.所以我的程序只是通过AxBxCxDxExF的所有可能组合,其中字母是数字,"x"是+, - ,/和*.这是它的代码:

private void combineRecursive( int step, int[] numbers, int[] operations, int combination[]){
    if( step%2==0){//even steps are numbers
        for( int i=0; i<numbers.length; i++){
            combination[ step] = numbers[ i];
            if(step==10){//last step, all 6 numbers and 5 operations are placed
                int index = Solution.isSolutionCorrect( combination, targetSolution);
                if( index>=0){
                    solutionQueue.addLast( new Solution( combination, index));
                }
                return;
            }
            combineRecursive( step+1, removeIndex( i, numbers), operations, combination);
        }
    }else{//odd steps are operations
        for( int i=0; i<operations.length; i++){
            combination[ step] = operations[ i];
            combineRecursive( …

随着算法的进展,我有一棵大树.每个节点都包含set,我认为它是作为平衡二叉搜索树实现的.在创建该节点的子节点之前,每个节点的集合在该节点创建之后应保持固定.

但我担心复制每一套都非常昂贵.相反,我希望每个新创建的节点集合利用父节点集合的所有适当部分.简而言之,我很高兴复制集合的O(log n)而不是O(n).

STL的关联数据结构是否有任何变体可以提供这种部分复制优化？也许在Boost？当然,在Haskell或OCaML中实现这样的数据结构是微不足道的,但是在C++中需要更多的努力.

是O(1)还是O(logN)但系数较小？

如果这是未指定的,我至少想知道基于合理假设的答案,即地图/集是使用红黑或AVL树实现的.我认为,插入元素的一般算法是这样的:

• 找到合适的地方 - O(logN)
• 做实际插入 - ？
• 必要时重新平衡树 - ？

现在,如果我们提供正确的迭代器提示,那么第一步就变成O(1).其他步骤是O(1)还是O(logN)？

我正在阅读一本关于数据结构的书,它说左侧平衡二叉树是一棵树,其中叶子只占据最后一级的最左边位置.

这对我来说似乎有点模糊.这是否意味着叶子只在根的左侧,并且分布在整个水平,或者只留在整个树的左侧.究竟什么构成左平衡？

我不确定我的猜测是否涵盖了任何答案,所以如果有人可以提供帮助,我们将非常感激:-).

因此,在平衡KD树时,您应该找到中位数,然后将所有较少的元素放在左子树上,而将更大的元素放在右侧.但是如果你有多个与中位数具有相同价值的元素,会发生什么？他们是左边的子树,右边还是丢弃它们？

我问,因为我尝试过多次操作,它会影响我最近邻搜索算法的结果,并且在某些情况下,树的给定部分的所有元素都将具有完全相同的值,因此我不这样做知道在这种情况下如何拆分它们.

是否有可能强制Boost.Spirit Qi以这种方式运行,生成的语法可以根据一些运行时可计算的条件/规则/速率进行调整？例如,输入由语言构造组成,这些构造在解析期间导致不同的替代方案,一些更频繁,另一些 - 更少.但是替代方案的顺序会影响效率,即语法的运行时最优性.在某些情况下,不可能事先确定在任意输入(可能强烈聚集)的情况下将更频繁地选择哪种替代方案.

我知道可以qi::symbols在运行时附加符号,但对于其他一些解析器来说,类似的行为是可取的.

这是c中的一个简单的二叉树,但它似乎不平衡,如何使其平衡？

码:

/**
 * binary_tree impl
 */

#include <stdio.h>
#include <stdlib.h>


typedef struct _tnode _tnode;
typedef struct _bin_tree _bin_tree;
struct _tnode {
    int data;
    _tnode *parent;
    _tnode *left;
    _tnode *right;
};

_tnode *new_node(int data) {
    _tnode *node = (_tnode*)malloc(sizeof(_tnode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

_tnode *add(_tnode *top, int new_data, int (*cmpf)(int, int)) {
    if(top == NULL) {
        top = new_node(new_data);
    } else if(cmpf(top->data, new_data)<=0) {
        if(top->left == NULL) 
            top->left = new_node(new_data);
        else
            add(top->left, …

B树与AVL树一样是自平衡树。在这里我们可以看到如何使用左右旋转来保持 AVL 树平衡。

这里是一个解释 B 树插入的链接。如果我没记错的话，这种插入技术不涉及任何旋转来保持树平衡。因此它看起来更简单。

问题：是否有任何类似的（或任何其他不使用旋转的技术）来保持 avl 树平衡？

我不太了解为什么splay树数据结构中的轮换不仅要考虑评级节点的父级，还要考虑祖父母（zig-zag和zig-zig操作）。为什么以下方法不起作用：

例如，当我们在树中插入一个新节点时，我们检查是否插入到左或右子树中。如果插入到左侧，则将结果右旋转，反之亦然。递归就是这样

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

那应该避免整个“花花公子”程序，你不觉得吗？