recursion - 如何在 lisp 中使用父子指针制作 splay 树

Question

我将这个节点结构定义为

(defstruct node 
  parent
  left
  right
  data)

当我填写父节点时，有什么方法可以避免在计算父节点时无限递归吗？

例如:假设我有一个节点 (A :parent B :left 2 :right 3 :data nil) 和一个节点 (B :parent nil :left 4 :right A:数据无)。当你评估 A 的父级时，你会得到一个无限递归(A 的父级是 B -> B 的右边是 A -> A 的父级是 B -> ...)。有没有办法在保持所有 splay 树操作的 mlg(n) 性能的同时避免这种情况？

我很感激

Answer 1

无限递归可能作为打印的一部分发生。您可以通过以下方式避免这种情况:

• 不打印循环结构
• 在标准打印机中启用圆形检测:(setf *print-circle* t)