标签: binary-tree

我需要一个支持这些声明的多线程数据结构:

• 允许多个并发读者和作者
• 排序
• 容易推理

实现多个读者和一个作家要容易得多,但我真的不想允许多个作家.

我一直在研究这个领域,我知道ConcurrentSkipList(由Lea基于Fraser和Harris的工作),因为它是在Java SE 6中实现的.我还实现了我自己的并发Skip List版本在一个可证明正确的缩放并发跳表由赫利希,列弗,Luchangco和沙维特.

这两个实现是由比我更聪明的人开发的,但我仍然(有点惭愧,因为它是惊人的工作)不得不问这些问题是否是并发多读/写器数据结构的两个唯一可行的实现今天有空吗？

我们都知道有很多自平衡二分查找树(BST),最着名的是红黑和AVL.看看AA树和替罪羊树也许有用.

我想删除插入和搜索,就像任何其他BST一样.但是,删除给定范围内的所有值或删除整个子树是很常见的.所以:

1. 我想在O(log n)(平衡树)中插入,搜索,删除值.
2. 我想删除一个子树,保持整个树平衡,在O(log n)(最坏情况或摊销)
3. 在平衡树之前,删除行中的多个值可能很有用
4. 我通常会一次插入2个值,但这不是一个规则(如果有一个树数据结构考虑到这一点,只是一个提示)

是否有AVL或RB的变体可以帮助我吗？替罪羊树看起来更像这样,但也需要一些改变,任何有经验的人都可以分享一些东西？

更准确地说,哪种平衡程序和/或删除程序可以帮助我保持这项行动的时间效率？

我在C中的链表的插入方法遇到了一些麻烦.它似乎只在列表的开头添加.我做的任何其他插入都失败了.而这个CodeBlocks调试器很难理解我仍然没有得到它.它永远不会给我价值,只有内存中的地址.无论如何这是我的功能.你有没有看到它失败的原因？

/* function to add a new node at the end of the list */
int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while(current->next != NULL) …

这是勇敢的脑筋急转弯.我已经好几天了,只是无法提供解决方案.

我想提出这样的事情:

仅使用html,CSS和PHP.

我靠近了,但不是我所期待的.这是PHP中的代码,这是输出.

<table border="0">
<thead>
    <tr>
        <th>Cientoveintiochavos</th>
        <th>Seseintaicuatravos</th>
        <th>Treintaidosavos</th>
        <th>Dieciseisavos</th>
        <th>Octavos</th>
        <th>Cuartos</th>
        <th>Semifinales</th>
        <th>Final</th>
    </tr>
</thead>
<tbody>
<?php for($i=0;$i<256;$i++): ?>
    <tr>
        <?php for($n=0,$c=2;$n<8;$n++,$c*=2): ?>
            <?php 
            /*
            if(false){//$i == 0) {
                $rwspn = $c/2+1; 
                $iter = 0;
            } else {
                $rwspn = $c; 
                $iter = $c;//-$c/2+1;
            } 
            */
            $class = ($i%($c*2))?'par':'impar winner';
            if($i%$c==0):?>
                <td rowspan="<?=$c;?>" class="<?=$class;?>"><span><?php echo genRandomString();?></span></td>
            <?php endif; ?>
        <?php endfor; ?>
    </tr>   
<?php endfor; ?>
</tbody>
</table>

如果有人知道如何表示二叉树或树形图或提出更智能的代码,请告诉我!

最近,对于数据结构类,我被问到一个问题,即如何删除懒惰(即,首先标记需要删除的项目的删除,然后在某个时候删除所有标记的项目)将是有利的/不利于数组,链表或二叉树.以下是我的想法:

• 这将有助于数组,因为每次删除索引时都会节省移动数组所花费的时间,尽管在需要遍历数组的算法中,可能效率低下.
• 这对链接列表没有帮助,因为您需要遍历O(n)以标记要删除的项目.
• 我不完全确定二叉树,但如果它是一个链表实现,我会想象它就像链表？

考虑以下数组,声称代表了二叉树:

[1,2,5,6,-1,8,11]

鉴于值为-1的索引表示根元素,我在下面的问题:

a)这实际上是如何表示的？

我们应该遵循以下公式(来自此链接的来源)来找出树吗？三个简单的公式允许您从父项的索引转到其子项的索引,反之亦然:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

如果我们使用上面的公式,那么index(root)= 3,index(left child)= 7,它不存在.

b)知道它是否是完整的二叉树是否重要？

我正在寻找用PHP构建所有可能的决策树.我正在寻找的就是这个答案,但是,我需要在php中使用它,而我在解释LINQ时遇到了困难.并且stringbuilder可能需要是一个数组.

我正在看一本面试书,问题是:

您有两个非常大的二叉树:T1具有数百万个节点,并且 T2具有数百个节点.创建一个算法来确定是否T2是子树T1.

作者提到这是一个可能的解决方案:

请注意,此处的问题指定T1有数百万个节点 - 这意味着我们应该注意我们使用了多少空间.例如,假设T1有1000万个节点 - 这意味着仅有数据40 mb.我们可以创建一个表示inorder和preorder遍历的字符串.如果T2preorder遍历是's preorder遍历的子字符串T1,并且T2inorder遍历是遍历遍历的子字符串T1,那么它T2是一个子字符串T1.

我不太清楚为什么如果这些是真的背后的逻辑:

• T2-preorder-traversal-string 是一个子串 T1-preorder-traversal-string
• T2-inorder-traversal-string 是一个子串 T1-inorder-traversal-string

那T2必须是子串(虽然我假设作者的意思是子树)T1.我能解释一下这个逻辑吗？

编辑:用户BartoszMarcinkowski提出了一个好点.假设两个树都没有重复的节点.

我刚刚开始研究Okasaki的Purely Functional Data Structures,但是我一直在用Haskell而不是Standard ML做事.但是,我遇到了一个早期练习(2.5),让我对如何在Haskell中做事情感到有点困惑:

将现有元素插入二叉搜索树会复制整个搜索路径,即使复制的节点与原始节点无法区分.使用异常重写插入以避免此复制.每次插入只建立一个处理程序,而不是每次迭代一个处理程序.

现在,我的理解是,作为一种不纯洁的语言,ML通过传统的异常处理方法得到了解,而不是Java,所以你可以完成这样的事情:

type Tree = E | T of Tree * int * Tree

exception ElementPresent

fun insert (x, t) = 
  let fun go E = T (E, x, E)
      fun go T(l, y, r) = 
             if      x < y then T(go (l), x, r)
             else if y < x then T(l, x, go (r))
             else    raise ElementPresent
  in go t
  end 
  handle ElementPresent => t

我没有ML实现,所以这在语法方面可能不太正确.

我的问题是,我不知道这是如何在Haskell做,在做的一切之外IO单子,这似乎是作弊,即使它不是作弊,将严重限制其真正的功能的用处并不做任何突变.我可以使用Maybe …

我有BinaryTreeNode(int值)及其左右子类和BinaryTree(int rootVal),BinaryTreeNode根,其中rootVal为其值.我开发了一个代码来计算树中的节点数(在BinaryTreeNode类中),但是由于NullPointerException它不起作用:

public int size(){
    if(this == null) {    // base case
        return 0;
    } else {
        return 1 + left.size() + right.size();
    }
}

然而,我发现的另一种解决方案,采用类似的策略,有效:

public int size(BinaryTreeNode refNode){
    if(refNode == null) {    // base case
        return 0;       
    } else {
        return 1 + size(refNode.left) + size(refNode.right); 
    }
}

我已经理解为什么我的代码抛出异常(因为左/右指向null).但我想理解为什么第二种解决方案与准原理相同.先感谢您!