[mbf1]

I added next and previous pointers to my red-black tree implementation for a freshman-level CS class back in 1997. It enabled me to claim O(1) rather than O(lg N) to "find next value" at an expense of a constant order of memory usage. Converting the whole tree to a doubly linked list in O(N) time is cute. It's also possible to re-construct a new balanced binary search tree in O(N) time using O(N) memory.

You'd start by counting the number of nodes in your circular array O(N), and making an array of pointers to each node O(N), then finding the middle node, which is the root node at count / 2. You'd then re-link the nodes for a sub-array and recurse on both sides using your in-order array of pointers, and replacing the smaller and larger node pointers with the pointers from the array. The total recursive algorithm visits each node in the new tree only once.