How to implement AO* algorithm? I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-heaps to implement the A* algorithm. In these cases, we do not need to construct the search tree explicitly.

But I can not find a simple data structure to simulate the searching process of the AO* algorithm. I would like to know if constructing the search tree explicitly is the only way to implement AO* algorithm? Can anybody provide me an efficient implementation?
Regarding this article every time you expand a node in the AO* algorithm you must go backwards to update all of its predecessors’ estimated cost.

When you use linear data structure to contain the nodes you must traverse the data elements sequentially and only one data element can be directly taken (stack, queue, priority queue …).

In AO* each time a node is taken for expansion based on its estimated cost the algorithm iterates over all of the nodes that are its predecessors(to update their estimated cost). That means that sometimes you should take element based on its estimated cost and sometimes based on its successor. There is no sequence order that can meet both of these conditions in the general case.
Probably there is a way to use "nested" linear data structures, but it should just imitate a tree structure, and it will be better to build the search tree instead.