我可以将红黑树表示为数组吗？
Can I represent a red black tree as an array?
是否值得将红黑树表示为数组以消除内存开销。或者数组会占用更多内存，因为数组会有空槽吗？
它既有正面的，也有负面的。这个答案适用于 C [因为你提到这是你将使用的]
正面
- 假设您已经创建了一个数组作为将用于红黑树的对象池。找到位置后删除一个元素或者初始化一个新元素会快一点，因为你很可能会用到你自己创建的内存池
消极面
- 是的，数组很可能最终会占用更多内存，因为数组有时会有空槽。
- 在这种情况下，您必须确定红黑树的最大大小。所以有大小限制。
- 您没有利用顺序内存的优势 space，因此这可能是一种资源浪费。
是的，您可以将红黑树表示为数组，但不值得。
红黑树的最大高度为2*log2(n+1)，其中n为条目数。每个级别的数组表示中的条目数为 2**n，其中 n 是级别。因此，要存储 1_000 个条目，您必须分配 1_048_576 个条目的数组。要存储 1_000_000 个条目，您必须分配 1_099_511_627_776 个条目的数组。
不值得。
红背树（实际上是大多数数据结构）不关心使用哪种存储设施，这意味着您可以使用数组甚至 HashTable/Map 来存储树节点、数组索引或地图键是您的新“指针”。如果愿意，您甚至可以将树作为文件放在磁盘上，并使用文件偏移量作为节点索引（不过，在这种情况下，您应该改用 B-Tree）。
主要问题是复杂性增加，因为现在您必须手动管理存储（而不是让 OS and/or 语言运行时为您做）。有时你想扩大数组以便存储更多项目，有时你想缩小它（真空）以释放未使用的 space。这些操作本身可能代价高昂。
内存使用明智，存储设施不会改变树上的节点数。如果你的旧学校指针er树上有 2,000 个节点（树高=10），你的花式数组ilized[=18=上仍然有 2,000 个节点] 树（树高还是10）。但是，在 vacuum 操作之间可能存在冗余 space。
是否值得将红黑树表示为数组以消除内存开销。或者数组会占用更多内存，因为数组会有空槽吗？
它既有正面的，也有负面的。这个答案适用于 C [因为你提到这是你将使用的]
正面
- 假设您已经创建了一个数组作为将用于红黑树的对象池。找到位置后删除一个元素或者初始化一个新元素会快一点，因为你很可能会用到你自己创建的内存池
消极面
- 是的，数组很可能最终会占用更多内存，因为数组有时会有空槽。
- 在这种情况下，您必须确定红黑树的最大大小。所以有大小限制。
- 您没有利用顺序内存的优势 space，因此这可能是一种资源浪费。
是的，您可以将红黑树表示为数组，但不值得。
红黑树的最大高度为2*log2(n+1)，其中n为条目数。每个级别的数组表示中的条目数为 2**n，其中 n 是级别。因此，要存储 1_000 个条目，您必须分配 1_048_576 个条目的数组。要存储 1_000_000 个条目，您必须分配 1_099_511_627_776 个条目的数组。
不值得。
红背树（实际上是大多数数据结构）不关心使用哪种存储设施，这意味着您可以使用数组甚至 HashTable/Map 来存储树节点、数组索引或地图键是您的新“指针”。如果愿意，您甚至可以将树作为文件放在磁盘上，并使用文件偏移量作为节点索引（不过，在这种情况下，您应该改用 B-Tree）。
主要问题是复杂性增加，因为现在您必须手动管理存储（而不是让 OS and/or 语言运行时为您做）。有时你想扩大数组以便存储更多项目，有时你想缩小它（真空）以释放未使用的 space。这些操作本身可能代价高昂。
内存使用明智，存储设施不会改变树上的节点数。如果你的旧学校指针er树上有 2,000 个节点（树高=10），你的花式数组ilized[=18=上仍然有 2,000 个节点] 树（树高还是10）。但是，在 vacuum 操作之间可能存在冗余 space。