广度优先搜索和深度优先搜索会检查闭合集是否包含某个棋面状态，所以我们可以用散列表来提高效率。但是，对于A*搜索来说，我们可能需要重新评估已经访问过的棋面状态。那么，会发生什么呢？回忆一下在深度优先搜索中，一个达到深度限制的棋面状态，尽管只离目标状态只有3步，但是也会被放入闭合集，并且不会再被处理。在A*搜索中，如果棋面状态的得分比之前更低，那么它们就需要重新处理。
A*搜索需要在开放集合中快速找到评价值最小的棋面状态。注意，深度优先搜索和广度优先搜索从开放集合中得到下一个棋面状态只需要常数时间，因为它们使用队列或者栈。如果开放集合是一个有序链表，那么插入棋面状态的性能将会是O(n)，我们不能使用二叉堆，因为我们事先不知道有多少棋面状态需要评估。因此我们使用平衡二叉树，插入棋面状态和得到最小开销的棋面状态的性能都是O(log n)。