如何在内存中表示二叉树 [英] How to represent a binomial tree in memory

问题描述

我有这样一个结构，被描述为二叉树。让我们看一幅图：

哪些是在内存中表示最好的方法？只是为了澄清，不是一个简单的二叉树，因为节点N4都是N1的左子节点和N2的右子节点，N7和N8等同样的共享等等...我需要一个很容易避免的构造算法复制这样的节点，但只是引用它们。

更新
我们中许多人不同意二叉树定义但这个金融风险（特别是衍生产品定价）可以看看这里： http：// http例如.developer.nvidia.com / GPUGems2 / gpugems2_chapter45.html 。所以我使用域名定义。

解决方案

你可以逐级生成结构级别。在每次迭代中，创建一个级别的节点，将它们放在数组中，并将之前的级别连接到它们。这样的东西（C＃）：

  Node GenerateStructure（int levels）
 {
 Node root = null; 
 
 Node [] previous = null; 
 
（int level = 1; level< = levels; level ++）
 {
 int count = level; 
 
 var current = new Node [count]; （int i = 0; i< count; i ++）
 current [i] = new Node（）; 
 
 
 
 if（level == 1）
 root = current [0]; （int i = 0; i< count  -  1; i ++）
 {
上一个[i] .Left = current [i]; 
 
 
上一个[i] .Right = current [i + 1]; 
} 
 
以前=当前; 
} 
 
返回根; 
} 
  

整个结构需要O（N ^ 2）个内存，其中N是级数。这种方法需要两个阵列的O（N）个附加存储器。另一种方法是从左到右生成图形，但这也需要O（N）个附加存储器。

时间复杂度显然是O（N ^ 2 ）。

I've got such a structure, is described as a "binomial tree". Let'see a drawing:

Which is the best way to represent this in memory? Just to clarify, is not a simple binary tree since the node N4 is both the left child of N1 and the right child of N2, the same sharing happens for N7 and N8 and so on... I need a construction algorithm tha easily avoid to duplicates such nodes, but just referencing them.

UPDATE Many of us does not agree with the "binomial tree deefinition" but this cames from finance ( expecially derivative pricing ) have a look here: http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter45.html for example. So I used the "Domain acceted definition".

解决方案

You could generate the structure level by level. In each iteration, create one level of nodes, put them in an array, and connect the previous level to them. Something like this (C#):

Node GenerateStructure(int levels)
{
    Node root = null;

    Node[] previous = null;

    for (int level = 1; level <= levels; level++)
    {
        int count = level;

        var current = new Node[count];

        for (int i = 0; i < count; i++)
            current[i] = new Node();

        if (level == 1)
            root = current[0];

        for (int i = 0; i < count - 1; i++)
        {
            previous[i].Left = current[i];
            previous[i].Right = current[i + 1];
        }

        previous = current;
    }

    return root;
}

The whole structure requires O(N^2) memory, where N is the number of level. This approach requires O(N) additional memory for the two arrays. Another approach would be to generate the graph from left to right, but that would require O(N) additional memory too.

The time complexity is obviously O(N^2).

这篇关于如何在内存中表示二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！