标签: binary-tree

引用维基百科:

使用传统的二叉树数据结构来实现二进制堆是完全可以接受的.在添加可以通过算法解析 的元素时,在二进制堆的最后一级找到相邻元素存在问题 ...

关于这种算法如何工作的任何想法？

我无法找到有关此问题的任何信息,因为大多数二进制堆都是使用数组实现的.

任何帮助赞赏.

最近,我注册了一个OpenID帐户,无法编辑我的初始帖子或评论答案.这就是我通过这个答案回应的原因.非常遗憾.

引用米奇小麦:

@Yse:你的问题是"如何找到二进制堆的最后一个元素"？

是的.或者更确切地说,我的问题是:"我如何找到非基于数组的二进制堆的最后一个元素？".

引用Suppressingfire:

你有没有提出这个问题的背景？(也就是说,你试图解决一些具体问题吗？)

如上所述,我想知道"找到非基于数组的二进制堆的最后一个元素"的好方法,这是插入和删除节点所必需的.

引用罗伊:

对我来说,使用普通的二叉树结构(使用定义为[data,pLeftChild,pRightChild]的pRoot和Node)并添加两个额外的指针(pInsertionNode和pLastNode)似乎是最容易理解的.pInsertionNode和pLastNode都将在插入和删除子例程期间更新,以便在结构中的数据发生更改时保持当前状态.这使O(1)访问结构的插入点和最后一个节点.

是的,这应该有效.如果我没有弄错,找到插入节点和最后一个节点,当它们的位置由于删除/插入而变为另一个子树时,可能会有点棘手.但我会试一试.

引用Zach Scrivena:

如何进行深度优先搜索......

是的,这将是一个很好的方法.我也会尝试一下.

我还在想,如果有办法"计算"最后一个节点和插入点的位置.具有N个节点的二进制堆的高度可以通过获取大于N的最小二次幂的log(基数2)来计算.也许可以计算最深级别上的节点数.然后可能确定如何遍历堆以到达插入点或节点以进行删除.

有谁知道如何计算二叉搜索树的搜索时间(即最坏情况,最佳情况和平均情况)？

我们都知道,如果很好地选择了哈希函数,哈希表对插入和查找都有O(1)时间.那么,我们想要使用二进制搜索树的原因是什么？仅仅因为完美的哈希函数难以设计？

我在这里如何提出这个问题？我注意到,标准 C++ STL具有set和map其与二叉搜索树实现,但没有哈希(不是说非参考标准hash_set,hash_map).虽然,Ruby只有Hash.我想了解这种差异背后的理性.

我正在研究实现一个简单的开源对象时态数据库的最佳数据结构,目前我非常喜欢使用持久性红黑树来实现它.

我使用持久数据结构的主要原因首先是最小化锁的使用,因此数据库可以尽可能并行.此外,实现ACID事务更容易,甚至能够抽象数据库以在某种集群上并行工作.这种方法的好处在于它几乎可以免费实现时态数据库.这是非常好的,特别适用于网络和数据分析(例如趋势).

所有这些都非常酷,但我对在磁盘上使用持久数据结构的整体性能有点怀疑.即使今天有一些非常快的磁盘可用,并且所有写入都可以异步完成,所以响应总是立竿见影,我不想在错误的前提下构建所有应用程序,只是意识到它并不是真的好这样做的方式.

这是我的思路: - 由于所有写入都是异步完成的,并且使用持久数据结构将不会使先前(当前有效)结构无效,因此写入时间实际上不是瓶颈.- 有一些关于此类结构的文献正是针对磁盘使用的.但在我看来,这些技术将增加更多的读取开销,以实现更快的写入.但我认为恰恰相反是可取的.这些技术中的许多确实最终会使用多版本树,但它们并不是严格不可变的,这对于证明持久开销非常重要. - 我知道在向数据库附加值时仍然需要进行某种锁定,而且如果不是要维护所有版本,我也知道应该有一个好的垃圾收集逻辑(否则文件大小肯定会大幅上升) .还可以考虑增量压缩系统. - 在所有搜索树结构中,我真的认为红黑是最接近我需要的,因为它们提供最少的旋转次数.

但是在此过程中存在一些可能的缺陷: - 异步写入 - 可能会影响需要实时数据的应用程序.但我不认为Web应用程序就是这种情况,大部分时间都是如此.此外,当需要实时数据时,可以设计另一种解决方案,例如需要以更实时的方式工作的特定数据的登记/结账系统. - 它们也可能导致一些提交冲突,但我没有想到它何时会发生的好例子.如果两个线程使用相同的数据,那么正常的RDBMS中也会发生冲突,对吧？ - 拥有像这样的不可变接口的开销将呈指数级增长,一切都注定要很快失败,所以这一切都是个坏主意.

有什么想法吗？

谢谢!

编辑:似乎存在对持久性数据结构的误解:http: //en.wikipedia.org/wiki/Persistent_data_structure

这不是作业.只是一个有趣的任务:)

给出完整的二进制搜索三个由数组表示.使用常量内存在O(n)中对数组进行排序.

例:

树:

              8
           /     \
          4       12
         /\       / \
        2  6     10  14
       /\  /\    /\   /\
      1 3 5  7  9 11 13 15

阵列:8,4,12,2,6,10,14,1,3,5,7,9,11,13,15

输出:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

有人可以使用C指导我使用树数据结构的一些教程.我尝试使用谷歌搜索,但大多数实现都是针对C++或Java.如果有人能指出我在C中的一些在线教程,那将是很棒的.

谢谢..

这是我最近在接受采访时提出的一个问题.给出二叉树,其条件是每个左子项比根小1,右子项大1.这是一个示例树

以O(1)和O(n)时间复杂度对其进行排序.

以下是我建议的方法:

1. 使用计数来维护每个元素的计数,然后在整个遍历完成O(n)时间和O(n)空间复杂度后返回.
2. 使用行程编码.在以数字作为键重复元素并形成值时形成链.仅当没有重复时才需要空间进行计数,因此除了数组之外不需要额外的空间,但是时间复杂度将是O(n log n),因为我们必须遍历数组以查看它是否存在.
3. 最后,我建议广度优先遍历.我们需要队列的O(log n)空间和O(n)时间复杂度(假设插入是O(1)链表).

你有什么办法？

之前在Stack Exchange中已经提出过这个问题,但是没有得到答复.

链接到前面提到的问题: 二进制堆通过二叉树结构实现

如何在二叉树中实现堆.要实现堆,了解最后一个填充节点和第一个未占用节点非常重要.这可以在树的级别排序中完成,但是时间复杂度将是O(n)以便找到第一个未占用的节点.那么,如何在O(logn)中的二叉树中实现堆？

谢谢Shekhar

我正在构建一个二叉树.如果这是一种正确的方法,请告诉我.如果没有请告诉我如何？我找不到构建一般二叉树的正确链接.BST到处都是编码的.

  3
 / \
1   4
   / \
  2   5

这是我想要制作的二叉树.我应该能够完成所有的树遍历.简单的东西.

public class Binarytreenode
{
    public Binarytreenode left;
    public Binarytreenode right;
    public int data;

    public Binarytreenode(int data)
    {
        this.data=data;
    }

    public void printNode()
    {
        System.out.println(data);
    }

    public static void main(String ar[])
    {
        Binarytreenode root = new Binarytreenode(3);
        Binarytreenode n1 = new Binarytreenode(1);
        Binarytreenode n2 = new Binarytreenode(4);
        Binarytreenode n3 = new Binarytreenode(2);
        Binarytreenode n4 = new Binarytreenode(5);

        root.left = n1;
        root.right = n2;
        root.right.left = n3;
        root.right.right = n4;
    } …

最近,我的问题被标记为重复,就像这样,即使它们不是.所以,让我先从下面开始,然后我将解释我的问题.

为什么这个问题不重复？

我不是在询问如何在顺序和前序遍历时创建二叉树.我要求证明,inorder + preorder遍历定义了一个唯一的二叉树.

现在,原来的问题.我去面试,面试官问我这个问题.我被困住了,无法继续.:|

问题: 给定二进制树的inorder和preorder遍历.证明给定数据只有一个二叉树.换句话说,证明两个不同的二叉树不能具有相同的顺序和前序遍历.假设树中的所有元素都是唯一的(感谢@envy_intelligence指出这个假设).

我尝试使用例子说服采访者,但采访者要求数学/直觉证明.任何人都可以帮我证明吗？