He estado investigando sobre la mejor estructura de datos para implementar un libro de órdenes limitadas. Algunas de las implementaciones más comunes incluyen arrays y árboles equilibrados. Este enlace tiene un buen conjunto de referencias.
La mayoría de los defensores de los árboles binarios equilibrados (como el Árbol Rojo-Negro) afirman que la complejidad temporal para añadir, cancelar y ejecutar órdenes al el libro de órdenes limitadas es O(1) .
"Para un libro escaso como el de la renta variable estadounidense, normalmente querrá organizar sus niveles de precios como 2 árboles rojo-negro (uno para el lado de la oferta, otro para el lado de la demanda), cada nivel de precios como una lista doblemente vinculada, y luego mantener una tabla hash separada para sus órdenes. Esto le permite tener O(1) acceso al precio y al tamaño de la BBO, O(1) para cancelar cualquier orden basada en su ID de orden, y también O(1) para añadir a la parte superior del libro".
¿No es la complejidad de iterar a través del árbol para encontrar el precio máximo (mínimo) para obtener la mejor oferta (demanda) O(log N)? Además, para añadir una orden a la parte superior del libro, tenemos que iterar el árbol hasta el nivel de precio apropiado y, a partir de ahí, añadirlo a la cabeza de la lista enlazada. Por lo tanto, ¿esta complejidad no es también O(log N)? Además, para cancelar una orden, ¿no tenemos que iterar hasta el nivel de precio apropiado y eliminar la orden de la lista enlazada?
¿Por qué algunas personas afirman que la complejidad para obtener la mejor oferta y pedir, añadir a la parte superior del libro y cancelar los pedidos es O(1)?
Gracias.
