标签: binary-tree

有一个名为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 …

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

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

• 插入: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      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 …

试图通过网络进行大量探索,但可以得到任何帮助,Everywhere就像在Binary Search树中添加一个节点一样.

问题:请求用于将节点添加到二叉树的算法和代码片段.(或指向我更正网址)

假设:根据我的理解,二叉树和二叉搜索树是不同的？如果我错了,请纠正我.

(请求:如果您正在编写代码片段,请使用适当的变量名称,这有助于理解)

例如:二叉树

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3       

二进制搜索树5 7 3 2 4 6

                   5
          3               7

   2          4       6       





insert(int key, struct node **root)
{
    if( NULL == *root )`
    {
        *root = (struct node*) malloc( sizeof( struct node ) );`
        (*root)->data = key;
        (*root)->left = NULL;    
        (*root)->right = NULL;  
    }
    else if(key < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key …

我在scala中创建了一个自定义对象树,我的insert方法抛出了一个堆栈溢出,因为它不是尾递归的.但是,我无法弄清楚如何使其尾递归.相关的例子我见过使用"累加器"变量,但是它们或者像Integers这样的东西可以被乘法和覆盖,或者我无法适应树的列表.这就是我所拥有的:

我的树木的基础:

abstract class GeoTree
case object EmptyTree extends GeoTree
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree

用于递归创建树的insert方法(导致堆栈溢出的方法):

  def insert(t:GeoTree, v: GeoNode): GeoTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => {
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
    }
  }

我不认为它的代码GeoNode实际上特别相关,因为它非常简单.这个类有两个Long属性和<,>以及==适当的树中使用重写运营商.有人可以提出如何使用累加器为我的insert功能,或其他一些方法使其尾递归？

首先,我有两个不同的实现,我认为是正确的,并且已经对它们进行了描述并认为它们具有相同的性能:

depth::Tree a -> Int
depth Empty        = 0
depth (Branch b l r) = 1 + max (depth l) (depth r)


depthTailRec::Tree a -> Int
depthTailRec = depthTR 0 where
           depthTR d Empty          = d 
           depthTR d (Branch b l r) = let dl = depthTR (d+1) l; dr = depthTR (d+1) r in max dl dr 

我只是想知道是不是人们都在谈论尾部递归如何有利于性能？很多问题都在我脑海中浮现:

1. 如何让深度功能更快？
2. 我读到了关于Haskell的懒惰如何减少尾递归的需要,是真的吗？
3. 事实是每个递归都可以转换成尾递归吗？
4. 最后,尾递归可以更快,更节省空间,因为它可以转换为循环,从而减少了推送和弹出堆栈的需要,我的理解是正确的吗？