I have bene researching on the best data structure to implement a limit order book. Some of the most common implementations include arrays and balanced trees. This link has a good set of references.
Most of the proponents of balanced binary trees (such as Red-Black Tree) claim that the time complexity to add, cancel and execute orders to the limit order book is O(1).
"For a sparse book like US equities, you'll usually want to organize your price levels as 2 red-black trees (one for bid side, one for ask side), each price level as a doubly-linked list, and then hold a separate hash table for your orders. This lets you have O(1) access to BBO price and size, O(1) to cancel any order based on its order ID, and also O(1) to append to the top of the book."
Isn't the complexity to iterate through the tree to find the max (min) price to get the best bid (ask) O(log N)? In addition to append an order to the top of the book, we have to iterate the tree to the appropriate price level and from there, add to the head of the linked-list. Hence, isn't this complexity also O(log N)? Furthermore, to cancel an order, don't we have to iterate to the appropriate price level and remove the order from the linked-list?
Why do some people claim that the complexity to get best-bid and ask , append to top of the book and cancel Orders be O(1)?