我可以将红黑树表示为数组吗？

Question

是否值得将红黑树表示为数组以消除内存开销。或者数组会占用更多内存，因为数组会有空槽吗？

Answer 1

它既有积极的一面，也有消极的一面。这个答案适用于 C [因为你提到这是你将使用的]

积极的一面

1. 假设您已经创建了一个数组作为您将用于红黑树的对象池。找到位置后删除元素或初始化新元素会快一点，因为您可能会使用自己创建的内存池。

消极的一面

1. 是的，数组很可能最终会占用更多内存，因为数组有时会有空槽。
2. 在这种情况下，您必须确定红黑树的最大大小。所以有大小限制。
3. 您没有利用顺序内存空间的优势，因此这可能是一种资源浪费。