标签: binary-tree

我有一系列我将要处理的项目(大理性).在每种情况下,处理将包括删除集合中的最小项目,做一些工作,然后添加0-2个新项目(总是大于删除的项目).该集合将使用一个项目进行初始化,并且工作将继续进行,直到它为空.我不确定该系列可能达到的尺寸,但我希望在1M-100M范围内.我不需要找到除最小项目之外的任何项目.

我目前正计划使用一棵红黑树,可能会调整以保持指向最小项目的指针.但是我之前从未使用过,我不确定我的使用模式是否符合其特性.

1)是否存在从左+随机插入删除模式会影响性能的危险,例如通过要求比随机删除显着更高的旋转次数？或者删除和插入操作仍然是这个使用模式的O(log n)？

2)其他一些数据结构是否会给我带来更好的性能,要么是因为删除模式还是利用了我只需要找到最小项目的事实？

更新:很高兴我问,二进制堆对于这种情况显然是一个更好的解决方案,并且承诺结果很容易实现.

雨果

有一个名为treap的数据结构:这是一个随机二进制搜索树,它也是随机生成的所谓"优先级"的堆.

这种结构存在一种变体,其中键是隐式的,它们不存储在树中,但我们将树中节点的有序索引视为此节点的键.我们需要在每个节点中存储子树的大小而不是密钥.这种技术使我们能够像某种数组一样思考treap,它在O(log N)时间内支持大量操作:子数组的插入,删除,恢复,间隔的变化等等.

我对这种结构有点了解,但没有那么多.我试图谷歌它,但我发现很多关于treap本身的文章,但没有关于这个"隐含的treap"/"索引列表".我甚至不知道它的名字,因为我的母语不是英语,我听过的讲座使用的是结构的本土术语,而不是英文原始术语.这个原生术语可以直接用英语翻译为"隐式键上的Treap"或"隐式键上的笛卡尔树".

任何人都能指出我关于这个结构的文章或告诉我它的原始名称吗？谢谢.

PS对不起,如果我的英语不够容易理解.

UPD:关于我正在寻找的结构的一些额外解释.

考虑使用随机选择的优先级和密钥的常用treap,它们是存储在树中的实际用户数据.然后让我们假设我们在每个节点中都存储了一些其他用户信息,而键只是搜索键.下一步是计算和维护每个节点中的子树大小:我们必须在每次合并/拆分/添加/删除后更新此参数,但它允许我们在O(log N)中查找树的第K个元素时间.

当我们在每个节点中有子树大小时,我们可以抛弃键并想象treap表示inorder遍历中的用户数据数组.可以从子树大小容易地计算每个元素的数组索引.现在我们可以添加/删除数组中间的元素或拆分此数组 - 所有这些都在O(log N)时间内完成.

我们也可以进行"多重"操作 - 例如,为我们的"数组"的所有元素添加一个常量值.为了实现这一点,我们必须延迟此操作,在每个节点中添加一个参数,该参数表示延迟常量,必须"稍后"添加到此节点的子阵列的所有元素,并将更改"推"到必要.向子阵列添加常量或绘制(标记)子阵列可以通过这种方式延迟,因为反转子阵列(此处节点中的延迟信息位"子阵列必须反转"),依此类推.

UPD2:这是代码片段 - 我发现的一小部分信息.不要注意西里尔语:)单词"снеявнымключом"的意思是直接翻译"with implicit key".

我想将一个给定的数学表达式标记为一个解析树,如下所示:

((3 + 4 - 1) * 5 + 6 * -7) / 2

                          '/'
                        /     \
                       +        2
                    /     \
                  *         *
                /   \     /   \
               -     5   6     -7
             /   \
            +     1
          /   \
         3     4

有没有纯Python方法来做到这一点？就像将字符串作为字符串传递给Python然后像上面提到的那样返回树.

谢谢.

我正在尝试在二叉树中搜索一个节点,如果它在那里则返回,否则返回null.顺便说一句,节点类有一个方法名称()返回一个带有它的名字的字符串...到目前为止我所拥有的是:

private Node search(String name, Node node){

     if(node != null){
         if(node.name().equals(name)){
            return node;
         }

      else{
         search(name, node.left);
         search(name, node.right);
      }
    }
    return null;
}

它是否正确？？

我正在学习算法和数据结构,并训练我正在尝试使用objective-c设计和实现二叉树.

到目前为止,我有以下类:

• main - 用于检测
• Node - 树的节点
• BinaryTree - 适用于与树相关的所有方法

BinaryTree我实施的第一类方法之一是insertNode:forRoot:.

- (void)insertNodeByRef:(Node **)node forRoot:(Node **)root{

    if (head == NULL) {
        head = *node;
    }
    // Case 2 root is null so can assign the value of the node to it
    if (root == NULL) {
        root = node;
    } else {
        if (node.data > root.data) { // to the right
            [self insertNode:node forRoot:root.right];
        } else if (node.data < root.data) { //or to the left
            [self …

删除二叉树中所有节点的标准算法使用沿这些行的节点上的后序遍历:

if (root is not null) {
   recursively delete left subtree
   recursively delete right subtree
   delete root
}

该算法使用O(h)辅助存储空间,其中h是树的高度,因为在递归调用期间存储堆栈帧所需的空间.但是,它在时间O(n)中运行,因为每个节点只访问一次.

是否有算法仅使用O(1)辅助存储空间删除二叉树中的所有节点而不牺牲运行时间？

在创建二进制最大堆时,为什么最好将它实现为基于数组,而不是基于树(基于树,每个节点也有一个指向它的父节点)？在运行时分析,内存使用,性能......

对于二进制最大堆,运行时间为:

• 插入:O(lg n)
• 删除min:O(lg n)
• 合并:O(n)

对于树实现

• 插入:O(lg n)
• 删除min:O(lg n)
• 合并:O(n)

谁能详细解释一下？

介绍

我正在构建一个HTML5 Web应用程序,它从给定的数字列表中创建二叉搜索树的可视化表示.

目前,我有一个算法,根据树的最大深度(这是一个基数为0的值)计算每行节点之间的视觉间距:

offset = 50
offset *= pow(2, maxDepth - currentDepth)

从这里开始,使用该偏移量和其父节点的x位置确定节点的位置.

该算法运行良好,因为它始终能够适应任何深度的最宽树.然而,这也使得树有时不必要地宽.

例子

树枝向左(太宽):

树枝向左分支http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

树枝分叉到两侧(左侧和右侧可以更靠近在一起).

树枝分枝到两侧http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

理想情况下,上面的树应该像金字塔一样,宽度较小,边长,如下图所示:

平衡树(算法最佳的情况):

平衡树http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

履行

属性

我正在使用Backbone.js从Node模型创建节点.每个节点都具有以下属性:

• parent(父节点)
• left(左子节点)
• 对(右子节点)
• x(节点的x位置,以像素为单位)
• y(节点的y位置,以像素为单位)

上面的x和y属性是根据节点分支的方向计算的:

if (parent.get('left') === node) {
    x = parentX - offsetX;
    y = parentY + offsetY;
} else if (parent.get('right') === node) {
    x = parentX + offsetX;
    y = parentY + offsetY;
}

此时,x和y属性是用于定位节点的确切值(每个节点都位于容器元素内的绝对值).

方法 …

这是我最近遇到的面试问题之一.

给定完整或几乎完整的二叉树的根地址,我们必须编写一个函数将树转换为最大堆.

这里没有涉及数组.树已经建成了.

例如,

              1   
         /         \
        2           5
      /   \       /   \ 
     3      4    6     7

可以有任何可能的最大堆作为输出 -

              7   
         /         \
        3           6
      /   \       /   \ 
     2     1     4     5

要么

              7   
         /         \
        4           6
      /   \       /   \ 
     2     3     1     5

等等...

我写了一个解决方案,但使用了前后顺序遍历的组合,但我想在O(n ^ 2)中运行.我的代码提供了以下输出.

              7   
         /         \
        3           6
      /   \       /   \ 
     1     2     4     5

我一直在寻找更好的解决方案.有人可以帮忙吗？

编辑:

我的守则

void preorder(struct node* root)
{    
    if(root==NULL)return;
    max_heapify(root,NULL);
    preorder(root->left); 
    preorder(root->right);
}
void max_heapify(struct node* root,struct …

我在采访中被要求打印二叉树的边界.例如.

      1
   /    \
  2      3
 /  \   /  \
4    5 6    7
    /   \     \
   8     9     10

答案是:1,2,4,8,9,10,7,3

我给出了以下答案.

第一种方法:

我使用Bool变量来解决上述问题.

void printLeftEdges(BinaryTree *p, bool print) {
   if (!p) return;
   if (print || (!p->left && !p->right))
       cout << p->data << " ";
   printLeftEdges(p->left, print);
   printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
   if (!p) return;
   printRightEdges(p->left, false);
   printRightEdges(p->right, print);
   if (print || (!p->left && !p->right))
   cout << p->data << " ";
}

void printOuterEdges(BinaryTree …