- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
在尝试理解二叉(搜索)树时,我偶然发现了 BST 是否可以有效地存储在平面数组中(即不浪费空间)的问题。在 google 和论坛(包括 SO)中搜索之后,我没有找到令我满意的东西。大多数人想要存储 BT(l=2*i+1
,r=2*i+2
)或接受这样一个事实,即节点的空子节点表示为nil
值(并像那样存储,不必要地占用空间)。
因此我编写了自己的算法,利用 BST 中的子节点具有特定排序属性的事实(小于根:left
,大于根:right
) .
为了存储 BST,我只是将它线性写入数组,深度优先。这发生在 O(n)
中,递归到树的子节点中。该数组正好是 n
个条目,n
是 BST 中的节点数。
为了从数组中重构 BST,我在遇到数组中的新条目时遵循两个规则:
下一个左节点(如果存在)是下一个比当前节点小的节点。
下一个正确的节点(如果存在)是下一个...
left
时不大于最小父键left
分支中则小于父级这也发生在 O(n)
中。
这对于非常非常大的随机结构树(只要它们是 BST)非常有效。实证测试从未显示出任何问题。我用 C++ 创建了一个工作代码示例 here , 两个转换函数为 toArray和 fromArray .
现在回答我的问题:这是否概括?我害怕监督与此有关的关键问题。事实上,我在网上没有找到任何其他内容,这让我想知道是否
a) 我太笨了,找不到它,
b) 这是常识,没有人谈论它或
c) 这是完全错误的。
如果任何精通该主题的人能就此启发我,我将不胜感激。
非常感谢。
编辑:
在谷歌搜索更多并完全忽略数组细节后,我找到了几个有效的解决方案。最突出的一个(如 here 和 here 所解释的)是使用预序遍历存储 BST。
最佳答案
最终,我自己找到了解决方案。用于从 BST 深度优先创建的数组重建 BST 的技术基于预序遍历。
我找到了解决方案 here并在我自己的 BST 类中实现它 here .主要部分如下:
bool BinarySearchTree::fromArrayPreorderTraversal(std::vector<unsigned int> vecArray, unsigned int& unCurrentIndex, unsigned int unMin, unsigned int unMax) {
bool bResult = false;
if(unCurrentIndex < vecArray.size()) {
unsigned int unVal = vecArray[unCurrentIndex];
if(unVal > unMin && unVal < unMax) {
bResult = true;
this->setKey(unVal);
unCurrentIndex++;
if(unCurrentIndex < vecArray.size()) {
if(!this->left(true)->fromArrayPreorderTraversal(vecArray, unCurrentIndex, unMin, unVal)) {
this->setLeft(NULL);
}
if(!this->right(true)->fromArrayPreorderTraversal(vecArray, unCurrentIndex, unVal, unMax)) {
this->setRight(NULL);
}
}
}
}
return bResult;
}
这里,一个 BST 的形式:
10
/ \
5 20
/ \ \
2 7 30
/
1
作为预序遍历数组可用:
10 5 2 1 7 20 30
父节点先出现,然后是左 child ,然后是右 child (递归)。这是 BST 的深度优先表示。
该算法获取键的有效范围以接受left
或right
侧的新节点作为参数(此处为unMin
和unMax
) 并基于此决定是否应创建节点。以这种方式重构了包括其原始结构在内的完整 BST。
这个(根据上面的引用)的时间复杂度是O(n)
。由于没有空间被浪费,空间复杂度也是O(n)
。
这个算法比我在问题中提出的算法要优雅得多。这似乎也是进行这种重建的一般方法。
关于c++ - 在不浪费空间的情况下将二叉搜索树存储在数组中的看似可行的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35106437/
我正在运行一个辅助角色,并检查 Azure 上托管的存储中是否存在数据。当我将连接字符串用于经典类型的存储时,我的代码可以正常工作,但是当我连接到 V2 Azure 存储时,它会抛出此异常。 “远程服
在我的应用程序的主页上,我正在进行 AJAX 调用以获取应用程序各个部分所需的大量数据。该调用如下所示: var url = "/Taxonomy/GetTaxonomyList/" $.getJSO
大家好,我正在尝试将我的商店导入我的 Vuex Route-Gard。 路由器/auth-guard.js import {store} from '../store' export default
我正在使用 C# 控制台应用程序 (.NET Core 3.1) 从 Azure Blob 存储读取大量图像文件并生成这些图像的缩略图。新图像将保存回 Azure,并将 Blob ID 存储在我们的数
我想将 Mlflow 设置为具有以下组件: 后端存储(本地):在本地使用 SQLite 数据库存储 Mlflow 实体(run_id、params、metrics...) 工件存储(远程):使用 Az
我正在使用 C# 控制台应用程序 (.NET Core 3.1) 从 Azure Blob 存储读取大量图像文件并生成这些图像的缩略图。新图像将保存回 Azure,并将 Blob ID 存储在我们的数
我想将 Mlflow 设置为具有以下组件: 后端存储(本地):在本地使用 SQLite 数据库存储 Mlflow 实体(run_id、params、metrics...) 工件存储(远程):使用 Az
我的 Windows 计算机上的本地文件夹中有一些图像。我想将所有图像上传到同一容器中的同一 blob。 我知道如何使用 Azure Storage SDKs 上传单个文件BlockBlobServi
我尝试发出 GET 请求来获取我的 Azure Blob 存储帐户的帐户详细信息,但每次都显示身份验证失败。谁能判断形成的 header 或签名字符串是否正确或是否存在其他问题? 代码如下: cons
这是用于编写 JSON 的 NeutralinoJS 存储 API。是否可以更新 JSON 文件(推送数据),而不仅仅是用新的 JS 对象覆盖数据。怎么做到的??? // Javascript
我有一个并行阶段设置,想知道是否可以在嵌套阶段之前运行脚本,所以像这样: stage('E2E-PR-CYPRESS') { when { allOf {
我想从命令行而不是从GUI列出VirtualBox VM的详细信息。我对存储细节特别感兴趣。 当我在GUI中单击VM时,可以看到包括存储部分在内的详细信息: 但是到目前为止,我还没有找到通过命令行执行
我有大约 3500 个防洪设施,我想将它们表示为一个网络来确定流动路径(本质上是一个有向图)。我目前正在使用 SqlServer 和 CTE 来递归检查所有节点及其上游组件,只要上游路径没有 fork
谁能告诉我 jquery data() 在哪里存储数据以及何时删除以及如何删除? 如果我用它来存储ajax调用结果,会有性能问题吗? 例如: $("body").data("test", { myDa
有人可以建议如何为 Firebase 存储中的文件设置备份。我能够备份数据库,但不确定如何为 firebase 存储中的文件(我有图像)设置定期备份。 最佳答案 如何进行 Firebase 存储的本地
我最近开始使用 firebase 存储和 firebase 功能。现在我一直在开发从功能到存储的文件上传。 我已经让它工作了(上传完成并且文件出现在存储部分),但是,图像永远保持这样(永远在右侧加载)
我想只允许用户将文件上传到他们自己的存储桶中,最大文件大小为 1MB,仍然允许他们删除文件。我添加了以下内容: match /myusers/{userId}/{allPaths=**} { al
使用生命周期管理策略将容器的内容从冷访问层移动到存档。我正在尝试以下策略,希望它能在一天后将该容器中的所有文件移动到存档层,但事实并非如此在职的。我设置了选择标准“一天未使用后”。 这是 json 代
对于连接到 Azure 存储端点,有 http 和 https 两个选项。 第一。 https 会带来开销,可能是 5%-10%,但我不支付同一个数据中心的费用。 第二。 http 更快,但 Auth
有人可以帮我理解这一点吗?我创建了Virtual Machine in Azure running Windows Server 2012 。我注意到 Azure 自动创建了一个存储帐户。当我进入该存
我是一名优秀的程序员,十分优秀!