在红黑树中存储颜色信息时如何保存内存？

Question

在红黑树中存储颜色信息时如何保存内存？

Vla*_*kov 7 algorithm binary-tree red-black-tree binary-search-tree data-structures

我在Coursera算法课程中碰到了这个问题,并意识到我不知道该怎么做.但是,我仍然有一些想法.我想到的第一件事是使用优化的位集(如Java BitSet)来获取映射节点key -> color.因此,我们所需要的是为整个树分配一个位集并将其用作颜色信息源.如果树中没有重复元素 - 它应该可以工作.

很高兴看到其他人对这项任务的看法.

Answer 1

小智 15

只需修改BST树.对于黑色节点,请不要.而对于红色节点,交换其左孩子和右孩子.在这种情况下,根据节点的右子是否大于其左子节点,可以将节点称为红色或黑色.

当然可以：只需检查一个节点是否位于错误的位置。如果有零个节点，则无需检查，因为我们从不为空节点提供红色链接。 (2认同)

Answer 2

Ale*_*nze 10

使用节点中某个指针的最低有效位来存储颜色信息.节点指针应该在大多数平台上包含偶数地址.详情请见此处.

归档时间：	12 年，6 月前
查看次数：	2051 次
最近记录：	7 年，7 月前