草庐IT

c++ - 使用数组实现四叉树

coder 2024-02-15 原文

我正在尝试使用 Barnes-Hut 树算法编写代码来模拟 n 体问题。我计划将来使用 CUDA，因此希望我的四叉树数据结构不由堆对象组成。

来自 Martin Burtscher 和 Keshav Pingali 的论文“基于树的 Barnes Hut n-Body 算法的高效 CUDA 实现”(抱歉找不到链接)，作者指出:

Dynamic data structures such as trees are typically built from heap objects, where each heap object contains multiple fields, e.g., child-pointer and data fields, and is allocated dynamically. Because dynamic allocation of and accesses to heap objects tend to be slow, we use an array-based data structure. Accesses to arrays cannot be coalesced if the array elements are objects with multiple fields, so we use several aligned scalar arrays, one per field, as outlined in Figure 6.6. As a consequence, our code uses array indexes instead of pointers to tree nodes.

我了解有关对齐标量数组的部分(即并行计算中的 SOA 与 AOS 习语)，但不幸的是，作者没有解释如何使用数组构造四叉树。

我的问题是如何使用数组实现四叉树数据结构(使用插入空间点的方法)？我知道如何使用节点结构和子指针等以传统方式实现四叉树。有人可以提供详细说明如何使用数组执行此操作的引用。甚至有关如何使用数组实现二叉树(或任何真正的树)的信息在这里也可能有用。

最佳答案

用数组实现二叉树很简单，首先我们要从1开始对数组进行索引，即根节点为1，然后

左 child 将是:leftChildIndex = 2 * parentIndex;

右 child 将位于:rightChildIndex = 2 * parentIndex + 1;

现在如果要查找当前节点的父节点:parentIndex = currIndex/2;

我写了一个 c++ 代码来执行树的前序遍历:

#include<iostream>

using namespace std;

int binaryTree[20], lengthOfTree;
int leftChild(int idx){ return 2*idx; }
int rightChild(int idx){ return 2*idx+1; }
int parentIndex(int idx){ return idx/2; }

void traverseTree(int idx){
    if(idx >= lengthOfTree) return;
    cout << binaryTree[idx] << " ";
    traverseTree(leftChild(idx));
    traverseTree(rightChild(idx));
}

int main(){

    lengthOfTree = 15;
    for(int i = 1;i <= lengthOfTree;i++){
        cin >> binaryTree[i];  
    }
    traverseTree(1);
    cout << endl;

return 0;
}

Ideone 解决方案链接:http://ideone.com/ZpTJCa

-------------------------------------------- ------------------------------

索引四叉树可能有点复杂，所以我们可以做的是再次从 1 索引树，对于每个节点，我们可以找到该节点的级别，例如:节点 1 的级别是0，节点4的层级为1，节点11的层级为2。

查找级别的伪代码:O(log n)

int findLevel(int nodeNo){
    int level = 0;
    int currNode = 1;
    while(currNode < nodeNo){
        currNode = currNode + pow(4, level++);
    }
    return level;
}

类似地，可以使用上面的伪代码计算当前级别的最左边节点和当前级别的最右边节点，然后找到当前节点的 4 个子节点，我们可以这样做:

当前节点的第一个子节点:child1 = (rightmostNode - currentNode) + 4 * (currentNode - leftmostNode);

当前节点的第二个 child :child2 = child1 + 1;

当前节点的第 3 个子节点:child3 = child2 + 1;

当前节点的第 4 个子节点:child4 = child3 + 1;

您还可以创建一个映射来查找父对象。

关于c++ - 使用数组实现四叉树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35978151/

amp43codechildsectionc++arraysalgorithmcudaquadtree

有关c++ - 使用数组实现四叉树的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  5. ruby - 在 Ruby 中使用匿名模块 - 2

    假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外，还有什么方法可以访问C和m中的其他内容？我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)？如何在使用完匿名模块后将其删除，使其定义的常量不再存在？ 最佳答案 三个答案:是的，使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于

  6. ruby - 使用 ruby​​ 和 savon 的 SOAP 服务 - 2

    我正在尝试使用ruby​​和Savon来使用网络服务。测试服务为http://www.webservicex.net/WS/WSDetails.aspx?WSID=9&CATID=2require'rubygems'require'savon'client=Savon::Client.new"http://www.webservicex.net/stockquote.asmx?WSDL"client.get_quotedo|soap|soap.body={:symbol=>"AAPL"}end返回SOAP异常。检查soap信封，在我看来soap请求没有正确的命名空间。任何人都可以建议我

  7. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  8. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  9. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  10. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

随机推荐