在Solaris 的这个 AVL 树实现中，如果为 32 位库编译，结构 avl_node 的定义方式很明显。
但是对于 64 库，指向节点父节点的指针被打包到“avl_pcb”中。看起来只存储了 61 位 ponter。
- 为什么这行得通？
- 为什么不为 32 位做类似的事情呢？
user933161
问问题
483 次
1 回答
9
在 64 位机器上，指针通常对齐到字边界，字边界是 8 字节的倍数。结果，指针的最低三位将为零。因此，如果一个数据结构需要三位信息，它可以将它们打包到指针的最低三位中。那样：
- 要跟随指针，请清除指针值的最低三位，然后取消引用它。
- 要读取这三个位中的任何一个，请屏蔽指针中的其余位并直接读取它们。
这种方法非常标准，不会失去任何指向地址的能力，因为通常出于性能或硬件原因，您无论如何都不希望有非对齐的指针。
我不确定的是为什么他们不在 32 位的情况下这样做，因为使用三个指针，他们可以使用相同的技巧轻松隐藏必要的位，但每个指针有两个位。我的猜测是这是一个性能问题：如果你确实将位打包到指针的底部，由于清除位所需的计算，你会增加跟踪指针的成本。请注意，例如，在 64 位情况下，这些位被打包到父指针中，这仅用于不常见的操作，例如计算顺序后继或在插入或删除时进行旋转。这可以保持快速查找。在 32 位的情况下，要隐藏 3 位，实现需要使用两个指针的低位，其中一个必须是左指针或右指针。我的猜测是，减慢树搜索的性能损失不值得节省空间，因此他们决定只处理内存损失并将它们分开存储。不过，这只是推测，因为如果他们愿意，他们绝对可以将这些位存储在指针的底部。
附带说明：如果实现使用的是红/黑树而不是 AVL 树，则只需要两个信息位：判断节点是红色还是黑色，以及判断节点是否为红色或黑色。节点是左孩子或右孩子。在这种情况下，所需的两位总是可以打包到一个 32 位指针中。这就是红黑树受欢迎的原因之一。
希望这可以帮助！
于 2013-01-11T17:03:06.067 回答